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

Links

Alois P. Heinz, Antidiagonals n = 0..9, flattened

Wikipedia, D-ary heap

Example

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

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

Crossrefs

Columns k=0-4 give: A019590(n+1), A000012, A056972, A273723, A273725.

Main diagonal gives A273729.

Cf. A273693.

Sequence in context: A226690 A318557 A245683 * A129634 A266825 A066438

Adjacent sequences: A273709 A273710 A273711 * A273713 A273714 A273715

Keyword

nonn,tabl

Author

Alois P. Heinz, May 28 2016

Status

approved