A273712 Number A(n,k) of k-ary heaps on n levels; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 6, 80, 1, 0, 1, 1, 24, 7484400, 21964800, 1, 0, 1, 1, 120, 3892643213082624, 35417271278873496315860673177600000000, 74836825861835980800000, 1, 0
Offset: 0
Examples
Square array A(n,k) begins: 1, 1, 1, 1, ... 1, 1, 1, 1, ... 0, 1, 2, 6, ... 0, 1, 80, 7484400, ... 0, 1, 21964800, 35417271278873496315860673177600000000, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..9, flattened
- Wikipedia, D-ary heap
Crossrefs
Programs
-
Maple
with(combinat): b:= proc(n, k) option remember; local h, i, x, y, z; if n<2 then 1 elif k<2 then k else h:= ilog[k]((k-1)*n+1); if k^h=(k-1)*n+1 then b((n-1)/k, k)^k* multinomial(n-1, ((n-1)/k)$k) else x, y:=(k^h-1)/(k-1), (k^(h-1)-1)/(k-1); for i from 0 do z:= (n-1)-(k-1-i)*y-i*x; if y<=z and z<=x then b(y, k)^(k-1-i)* multinomial(n-1, y$(k-1-i), x$i, z)* b(x, k)^i*b(z, k); break fi od fi fi end: A:= (n, k)-> `if`(n<2, 1, `if`(k<2, k, b((k^n-1)/(k-1), k))): seq(seq(A(n,d-n), n=0..d), d=0..7); -
Mathematica
multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, k_] := b[n, k] = Module[{h, i, x, y, z}, Which[n<2, 1, k<2, k, True, h = Log[k, (k-1)*n+1] // Floor; If[k^h == (k-1)*n+1, b[(n-1)/k, k]^k*multinomial[n-1, Array[(n-1)/k&, k]], {x, y} := {(k^h-1)/(k-1), (k^(h-1)-1)/(k-1)}; For[i = 0, True, i++, z = (n-1) - (k-1-i)*y - i*x; If[y <= z && z <= x, b[y, k]^(k-1-i) * multinomial[n-1, Join[Array[y&, k-1-i], Array[x&, i], {z}]]*b[x, k]^i * b[z, k]; Break[]]]]]]; A[n_, k_] := If[n<2, 1, If[k<2, k, b[(k^n-1) / (k-1), k]]]; Table[A[n, d-n], {d, 0, 7}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 24 2017, after Alois P. Heinz *)
Comments