A273693 Number A(n,k) of k-ary heaps on n elements; square array A(n,k), n>=0, k>=0, read by antidiagonals.

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, 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, 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

Offset: 0

Author

Alois P. Heinz, May 28 2016

Keywords

• nonn
• tabl

Examples

			A(4,2) = 3: 1234, 1243, 1324.
A(5,2) = 8: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.
A(5,3) = 12: 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425, 13524, 14235, 14325.
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.
(The examples use min-heaps.)
Square array A(n,k) begins:
  1, 1,   1,   1,    1,    1,    1,    1, ...
  1, 1,   1,   1,    1,    1,    1,    1, ...
  0, 1,   1,   1,    1,    1,    1,    1, ...
  0, 1,   2,   2,    2,    2,    2,    2, ...
  0, 1,   3,   6,    6,    6,    6,    6, ...
  0, 1,   8,  12,   24,   24,   24,   24, ...
  0, 1,  20,  40,   60,  120,  120,  120, ...
  0, 1,  80, 180,  240,  360,  720,  720, ...
  0, 1, 210, 630, 1260, 1680, 2520, 5040, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• Wikipedia, D-ary heap

Crossrefs

Columns k=0-10 give: A019590(n+1), A000012, A056971, A178008, A178009, A178010, A178011, A273694, A273695, A273696, A273697.

Main diagonal gives: A000142(n-1) for n>0.

Cf. A273712.

Programs

Maple

with(combinat):
A:= 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 A((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 A(y, k)^(k-1-i)*
                 multinomial(n-1, y$(k-1-i), x$i, z)*
                 A(x, k)^i*A(z, k); break fi
            od
      fi fi
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

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 *)