A273693 -id:A273693 - cp's OEIS frontend

A056971 Number of (binary) heaps on n elements.

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, 3143467008000, 25540669440000, 299677188096000, 2261626278912000, 25732281217843200, 241240136417280000

Offset: 0

Eric W. Weisstein

A sequence {a_i}{i=1..N} forms a (binary) heap if it satisfies a_i<a{2i} and a_i

Proof of recurrence: a_1 must take the greatest of the n values. Deleting a_1 gives 2 heaps of size b+r1, b+r2. - Sascha Kurz, Mar 24 2002

Note that A132862(n)*a(n) = n!. - Alois P. Heinz, Nov 22 2007

			There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on.
a(5) = 8 (min-heaps): 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.

Alois P. Heinz, Table of n, a(n) for n = 0..500
Sean Cleary, M. Fischer, R. C. Griffiths, and R. Sainudiin, Some distributions on finite rooted binary trees, UCDMS Research Report NO. UCDMS2015/2, School of Mathematics and Statistics, University of Canterbury, Christchurch, NZ, 2015.
D. Levin, L. Pudwell, M. Riehl, and A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A053644, A056972, A132862, A373452 (allows repeated elements).
Column k=2 of A273693.
Column k=0 of A306343 and of A306393.
Main diagonal of A373451.

a[0] := 1: a[1] := 1:
for n from 2 to 50 do
h := ilog2(n+1)-1:
b := 2^h-1: r := n-1-2*b: r1 := r-floor(r/2^h)*(r-2^h): r2 := r-r1:
a[n] := binomial(n-1, b+r1)*a[b+r1]*a[b+r2]:end do:
q := seq(a[j], j=0..50);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> a(f)*
      binomial(n-1, f)*a(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
    end:
seq(a(n), n=0..28);  # Alois P. Heinz, Feb 14 2019

a[0] = 1; a[1] = 1; For[n = 2, n <= 50, n++, h = Floor[Log[2, n + 1]] - 1; b = 2^h - 1; r = n - 1 - 2*b; r1 = r - Floor[r/2^h]*(r - 2^h); r2 = r - r1; a[n] = Binomial[n - 1, b + r1]*a[b + r1]*a[b + r2]]; Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Oct 22 2012, translated from Maple program *)

from functools import lru_cache
from math import comb
@lru_cache(maxsize=None)
def A056971(n):
    if n<=1: return 1
    h = (n+1).bit_length()-2
    b = (1<A056971(b+r1)*A056971(b+r2) # Chai Wah Wu, May 06 2024

See recurrence in Maple and Mma programs.

More terms from Sascha Kurz, Mar 24 2002

Offset and some terms corrected by Alois P. Heinz, Nov 21 2007

A273730 Square array read by antidiagonals: A(n,k) = number of permutations of n elements divided by the number of k-ary heaps on n+1 elements, n>=0, k>=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 6, 1, 1, 1, 2, 24, 1, 1, 1, 1, 3, 120, 1, 1, 1, 1, 2, 6, 720, 1, 1, 1, 1, 1, 3, 9, 5040, 1, 1, 1, 1, 1, 2, 4, 24, 40320, 1, 1, 1, 1, 1, 1, 3, 8, 45, 362880, 1, 1, 1, 1, 1, 1, 2, 4, 12, 108, 3628800, 1, 1, 1, 1, 1, 1, 1, 3, 5, 16, 189, 39916800

Offset: 0

Alois P. Heinz, May 28 2016

			Square array A(n,k) begins:
:     1,  1,  1, 1, 1, 1, 1, 1, ...
:     1,  1,  1, 1, 1, 1, 1, 1, ...
:     2,  1,  1, 1, 1, 1, 1, 1, ...
:     6,  2,  1, 1, 1, 1, 1, 1, ...
:    24,  3,  2, 1, 1, 1, 1, 1, ...
:   120,  6,  3, 2, 1, 1, 1, 1, ...
:   720,  9,  4, 3, 2, 1, 1, 1, ...
:  5040, 24,  8, 4, 3, 2, 1, 1, ...
: 40320, 45, 12, 5, 4, 3, 2, 1, ...

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

Columns k=1-10 give: A000142, A133385, A273731, A273732, A273733, A273734, A273735, A273736, A273737, A273738.

Cf. A273693.

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)-> n!/b(n+1, k):
seq(seq(A(n, 1+d-n), n=0..d), d=0..14);

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 = Floor @ Log[k, (k - 1)*n + 1]; 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] // Return]]]]]; A[n_, k_] :=  n!/b[n+1, k]; Table[A[n, 1+d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Mar 13 2017, translated from Maple *)

A(n,k) = A000142(n)/A273693(n+1,k).

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

Original entry on oeis.org

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

Alois P. Heinz, May 28 2016

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

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

Columns k=0-4 give: A019590(n+1), A000012, A056972, A273723, A273725.
Main diagonal gives A273729.
Cf. A273693.

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

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

A178008 Number of permutations of 1..n with no element e[i>=2]

Original entry on oeis.org

1, 1, 1, 2, 6, 12, 40, 180, 630, 3360, 22680, 113400, 831600, 7484400, 38918880, 302702400, 2918916000, 20432412000, 205837632000, 2500927228800, 21598916976000, 263986763040000, 3837961401120000, 33774060329856000, 431557437548160000, 6658314750743040000

Offset: 0

R. H. Hardin, May 17 2010

nonn

a(n) is also the number of labeled histories for the trifurcating labeled topology that possesses the largest number of labeled histories, among all labeled topologies with 2n+1 leaves. - Noah A Rosenberg, Feb 24 2025

Alois P. Heinz, Table of n, a(n) for n = 0..502
E. H. Dickey, N. A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Wikipedia, D-ary heap

Simple 2-way heap A056971.

Column k=3 of A273693.

a(0), a(21)-a(25) from Alois P. Heinz, May 27 2016

A178009 Number of permutations of 1..n with no element e[i>=2]

Original entry on oeis.org

1, 1, 1, 2, 6, 24, 60, 240, 1260, 8064, 36288, 241920, 1995840, 19160064, 124540416, 1162377216, 13076743680, 167382319104, 1422749712384, 17072996548608, 243290200817664, 3892643213082624, 34060628114472960, 428190753439088640, 6463004184721244160

Offset: 0

R. H. Hardin, May 17 2010

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..491
Wikipedia, D-ary heap

Simple 2-way heap A056971.

Column k=4 of A273693.

a(0), a(20)-a(24) from Alois P. Heinz, May 27 2016

A178010 Number of permutations of 1..n with no element e[i>=2]

Original entry on oeis.org

1, 1, 1, 2, 6, 24, 120, 360, 1680, 10080, 72576, 604800, 3326400, 26611200, 259459200, 2905943040, 36324288000, 290594304000, 3293402112000, 44460928512000, 675806113382400, 11263435223040000, 118266069841920000, 1734569024348160000, 29921315670005760000

Offset: 0

R. H. Hardin, May 17 2010

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..484
Wikipedia, D-ary heap

Simple 2-way heap A056971.

Column k=5 of A273693.

a(0), a(21)-a(24) from Alois P. Heinz, May 27 2016

A178011 Number of permutations of 1..n with no element e[i>=2]

Original entry on oeis.org

1, 1, 1, 2, 6, 24, 120, 720, 2520, 13440, 90720, 725760, 6652800, 68428800, 444787200, 4151347200, 46702656000, 597793996800, 8468748288000, 130660687872000, 1241276534784000, 16550353797120000, 260668072304640000, 4587758072561664000, 87932029724098560000

Offset: 0

R. H. Hardin, May 17 2010

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..479
Wikipedia, D-ary heap

Simple 2-way heap A056971.

Column k=6 of A273693.

a(0), a(21)-a(24) from Alois P. Heinz, May 27 2016

A273694 Number of 7-ary heaps on n elements.

Original entry on oeis.org

1, 1, 1, 2, 6, 24, 120, 720, 5040, 20160, 120960, 907200, 7983360, 79833600, 889574400, 10897286400, 81729648000, 871782912000, 11115232128000, 160059342643200, 2534272925184000, 43444678717440000, 798295971432960000, 8781255685762560000, 134645920515025920000

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..476
Wikipedia, D-ary heap

Column k=7 of A273693.

A273695 Number of 8-ary heaps on n elements.

Original entry on oeis.org

1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 181440, 1209600, 9979200, 95800320, 1037836800, 12454041600, 163459296000, 2324754432000, 19760412672000, 237124952064000, 3379030566912000, 54064489070592000, 946128558735360000, 17841281393295360000

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..474
Wikipedia, D-ary heap

Column k=8 of A273693.

A273696 Number of 9-ary heaps on n elements.

Original entry on oeis.org

1, 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 1814400, 13305600, 119750400, 1245404160, 14529715200, 186810624000, 2615348736000, 39520825344000, 640237370572800, 6082255020441600, 81096733605888000, 1277273554292736000, 22480014555552153600

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..472
Wikipedia, D-ary heap

Column k=9 of A273693.

Showing 1-10 of 11 results. Next

cp's OEIS Frontend

A056971 Number of (binary) heaps on n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A273730 Square array read by antidiagonals: A(n,k) = number of permutations of n elements divided by the number of k-ary heaps on n+1 elements, n>=0, k>=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A178008 Number of permutations of 1..n with no element e[i>=2]

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A178009 Number of permutations of 1..n with no element e[i>=2]

Views

Author

Keywords

Links

Crossrefs

Extensions

A178010 Number of permutations of 1..n with no element e[i>=2]

Views

Author

Keywords

Links

Crossrefs

Extensions

A178011 Number of permutations of 1..n with no element e[i>=2]

Views

Author

Keywords

Links

Crossrefs

Extensions

A273694 Number of 7-ary heaps on n elements.

Views

Author

Keywords

Links

Crossrefs

A273695 Number of 8-ary heaps on n elements.

Views

Author

Keywords

Links

Crossrefs

A273696 Number of 9-ary heaps on n elements.

Views

Author