%I #25 Oct 18 2018 16:26:21
%S 1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,1,2,1,0,1,1,1,2,3,1,0,1,1,1,2,6,8,
%T 1,0,1,1,1,2,6,12,20,1,0,1,1,1,2,6,24,40,80,1,0,1,1,1,2,6,24,60,180,
%U 210,1,0,1,1,1,2,6,24,120,240,630,896,1,0,1,1,1,2,6,24,120,360,1260,3360,3360,1,0
%N Number A(n,k) of k-ary heaps on n elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%H Alois P. Heinz, <a href="/A273693/b273693.txt">Antidiagonals n = 0..140, flattened</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/D-ary_heap">D-ary heap</a>
%e A(4,2) = 3: 1234, 1243, 1324.
%e A(5,2) = 8: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.
%e A(5,3) = 12: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13524, 14235, 14325.
%e A(6,3) = 40: 123456, 123465, 123546, 123564, 123645, 123654, 124356, 124365, 124536, 124563, 124635, 124653, 125346, 125364, 125436, 125463, 125634, 125643, 126345, 126354, 126435, 126453, 126534, 126543, 132456, 132465, 132546, 132564, 132645, 132654, 134256, 134265, 135246, 135264, 136245, 136254, 142356, 142365, 143256, 143265.
%e (The examples use min-heaps.)
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 2, 2, 2, 2, 2, ...
%e 0, 1, 3, 6, 6, 6, 6, 6, ...
%e 0, 1, 8, 12, 24, 24, 24, 24, ...
%e 0, 1, 20, 40, 60, 120, 120, 120, ...
%e 0, 1, 80, 180, 240, 360, 720, 720, ...
%e 0, 1, 210, 630, 1260, 1680, 2520, 5040, ...
%p with(combinat):
%p A:= proc(n, k) option remember; local h, i, x, y, z;
%p if n<2 then 1 elif k<2 then k
%p else h:= ilog[k]((k-1)*n+1);
%p if k^h=(k-1)*n+1 then A((n-1)/k, k)^k*
%p multinomial(n-1, ((n-1)/k)$k)
%p else x, y:=(k^h-1)/(k-1), (k^(h-1)-1)/(k-1);
%p for i from 0 do z:= (n-1)-(k-1-i)*y-i*x;
%p if y<=z and z<=x then A(y, k)^(k-1-i)*
%p multinomial(n-1, y$(k-1-i), x$i, z)*
%p A(x, k)^i*A(z, k); break fi
%p od
%p fi fi
%p end:
%p seq(seq(A(n, d-n), n=0..d), d=0..14);
%t multinomial[n_, k_] := n!/Times @@ (k!); A[n_, k_] := A[n, k] = Module[{h, i, x, y, z}, Which[n<2, 1, k<2, k, True, h = Floor @ Log[k, (k-1)*n+1]; If[k^h == (k-1)*n+1, A[(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, A[y, k]^(k-1-i)*multinomial[n-1, Join[Array[y&, k-1-i], Array[x&, i], {z}]]*A[x, k]^i*A[z, k] // Return]] ]]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* _Jean-François Alcover_, Mar 13 2017, translated from Maple *)
%Y Columns k=0-10 give: A019590(n+1), A000012, A056971, A178008, A178009, A178010, A178011, A273694, A273695, A273696, A273697.
%Y Main diagonal gives: A000142(n-1) for n>0.
%Y Cf. A273712.
%K nonn,tabl
%O 0,19
%A _Alois P. Heinz_, May 28 2016