35 lines
1,019 B
Text
35 lines
1,019 B
Text
var BN=Import("zklBigNum");
|
|
|
|
const nMax=100, nBranches=4;
|
|
|
|
var rooted =(nMax+1).pump(List.createLong(nMax+1).write,BN.fp(0)),
|
|
unrooted=(nMax+1).pump(List.createLong(nMax+1).write,BN.fp(0));
|
|
rooted[0]=BN(1); rooted[1]=BN(1); unrooted[0]=BN(1); unrooted[1]=BN(1);
|
|
|
|
fcn tree(br,n,l,inSum,cnt){
|
|
var c=(nBranches).pump(List().write,0); // happens only once
|
|
|
|
sum := inSum;
|
|
foreach b in ([br + 1 .. nBranches]){
|
|
sum += n;
|
|
if (sum > nMax or (l * 2 >= sum and b >= nBranches)) return();
|
|
if (b == br + 1) c[br] = rooted[n] * cnt; // -->BigInt
|
|
else{
|
|
c[br].mul(rooted[n] + b - br - 1);
|
|
c[br].div(b - br);
|
|
}
|
|
if (l * 2 < sum) unrooted[sum].add(c[br]);
|
|
if (b < nBranches) rooted[sum].add(c[br]);
|
|
foreach m in ([n-1 .. 1,-1]) { tree(b, m, l, sum, c[br]); }
|
|
}
|
|
}
|
|
|
|
fcn bicenter(s){
|
|
if (s.isEven) unrooted[s].add(rooted[s / 2] * (rooted[s / 2] + 1) / 2);
|
|
}
|
|
|
|
foreach n in ([1 .. nMax]){
|
|
tree(0, n, n, 1, BN(1));
|
|
bicenter(n);
|
|
println(n, ": ", unrooted[n]);
|
|
}
|