login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A273693 Number A(n,k) of k-ary heaps on n elements; square array A(n,k), n>=0, k>=0, read by antidiagonals. 12
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,19

LINKS

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

Wikipedia, D-ary heap

EXAMPLE

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

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

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.

Sequence in context: A003137 A006842 A299038 * A219967 A060505 A316101

Adjacent sequences:  A273690 A273691 A273692 * A273694 A273695 A273696

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, May 28 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 20 20:40 EST 2019. Contains 329347 sequences. (Running on oeis4.)