51 lines
1.3 KiB
Text
51 lines
1.3 KiB
Text
local bigint = require "pluto:bigint"
|
|
local fmt = require "fmt"
|
|
require "table2"
|
|
|
|
local branches = 4
|
|
local nmax = 250
|
|
local zero = bigint.new(0)
|
|
local one = bigint.new(1)
|
|
local rooted = table.rep(nmax, zero)
|
|
local unrooted = table.rep(nmax, zero)
|
|
local c = table.rep(branches, zero)
|
|
|
|
local function tree(br, n, l, sum, cnt)
|
|
local b = br + 1
|
|
while b <= branches do
|
|
sum += n
|
|
if sum > nmax then return end
|
|
if l * 2 >= sum and b >= branches then return end
|
|
if b == br + 1 then
|
|
c[br + 1] = rooted[n] * cnt
|
|
else
|
|
local tmp = rooted[n] + bigint.new(b - br - 1)
|
|
c[br + 1] *= tmp
|
|
c[br + 1] /= bigint.new(b - br)
|
|
end
|
|
if l*2 < sum then unrooted[sum] += c[br + 1] end
|
|
if b < branches then rooted[sum] += c[br + 1] end
|
|
local m = n - 1
|
|
while m > 0 do
|
|
tree(b, m, l, sum, c[br + 1])
|
|
m -= 1
|
|
end
|
|
b += 1
|
|
end
|
|
end
|
|
|
|
local function bicenter(s)
|
|
if s % 2 == 0 then
|
|
local tmp = (rooted[s // 2] + one) * rooted[s // 2]
|
|
tmp /= 2
|
|
unrooted[s] += tmp
|
|
end
|
|
end
|
|
|
|
rooted[1] = one
|
|
unrooted[1] = one
|
|
for n = 1, nmax do
|
|
tree(0, n, n, 1, one)
|
|
bicenter(n)
|
|
fmt.print("%3d: %s", n, unrooted[n])
|
|
end
|