A056972 -id:A056972 - 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

A195581 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 2, 4, 0, 0, 0, 16, 8, 0, 0, 0, 40, 64, 16, 0, 0, 0, 80, 400, 208, 32, 0, 0, 0, 80, 2240, 2048, 608, 64, 0, 0, 0, 0, 11360, 18816, 8352, 1664, 128, 0, 0, 0, 0, 55040, 168768, 104448, 30016, 4352, 256, 0, 0, 0, 0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512

Offset: 0

Alois P. Heinz, Sep 20 2011

Empty external nodes are counted in determining the height of a search tree.

			T(3,3) = 4, because 4 permutations of {1,2,3} result in a binary search tree of height 3:
  (1,2,3):   1       (1,3,2):   1     (3,1,2):   3   (3,2,1):   3
            / \                / \              / \            / \
           o   2              o   3            1   o          2   o
              / \                / \          / \            / \
             o   3              2   o        o   2          1   o
                / \            / \              / \        / \
               o   o          o   o            o   o      o   o
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 0, 2;
  0, 0, 2,  4;
  0, 0, 0, 16,      8;
  0, 0, 0, 40,     64,      16;
  0, 0, 0, 80,    400,     208,      32;
  0, 0, 0, 80,   2240,    2048,     608,     64;
  0, 0, 0,  0,  11360,   18816,    8352,   1664,   128;
  0, 0, 0,  0,  55040,  168768,  104448,  30016,  4352,   256;
  0, 0, 0,  0, 253440, 1508032, 1277568, 479040, 99200, 11008, 512;
  ...

Alois P. Heinz, Rows n = 0..140, flattened
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums give A000142. Column sums give A227822.
Main diagonal gives A011782, lower diagonal gives A076616.
T(n,A000523(n)+1) = A076615(n).
T(2^n-1,n) = A056972(n).
T(2n,n) = A265846(n).
Cf. A195582, A195583, A244108 (the same read by columns), A316944, A317012.

b:= proc(n, k) option remember; `if`(n<2, `if`(k b(n, k)-b(n, k-1):
seq(seq(T(n, k), k=0..n), n=0..10);

b[n_, k_] := b[n, k] = If[n == 0, 1, If[n == 1, If[k > 0, 1, 0], Sum[Binomial[n-1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}] ] ]; t [n_, k_] := b[n, k] - If[k > 0, b[n, k-1], 0]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Dec 17 2013, translated from Maple *)

Sum_{k=0..n} k * T(n,k) = A316944(n).

Sum_{k=n..2^n-1} k * T(k,n) = A317012(n).

A244108 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Original entry on oeis.org

1, 1, 2, 2, 4, 16, 40, 80, 80, 8, 64, 400, 2240, 11360, 55040, 253440, 1056000, 3801600, 10982400, 21964800, 21964800, 16, 208, 2048, 18816, 168768, 1508032, 13501312, 121362560, 1099169280, 10049994240, 92644597760, 857213660160, 7907423180800, 72155129446400

Offset: 0

Alois P. Heinz, Dec 21 2015

Empty external nodes are counted in determining the height of a search tree.

			Triangle T(n,k) begins:
: 1;
:    1;
:       2;
:       2,  4;
:          16,      8;
:          40,     64,      16;
:          80,    400,     208,      32;
:          80,   2240,    2048,     608,     64;
:               11360,   18816,    8352,   1664,   128;
:               55040,  168768,  104448,  30016,  4352,   256;
:              253440, 1508032, 1277568, 479040, 99200, 11008, 512;

Alois P. Heinz, Columns k = 0..9, flattened
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Row sums give A000142.
Column sums give A227822.
Main diagonal gives A011782, lower diagonal gives A076616.
T(n,A000523(n)+1) = A076615(n).
T(2^n-1,n) = A056972(n).
T(2n,n) = A265846(n).
Cf. A195581 (the same read by rows), A195582, A195583, A316944, A317012.

b:= proc(n, k) option remember; `if`(n<2, `if`(k b(n, k)-b(n, k-1):
seq(seq(T(n, k), n=k..2^k-1), k=0..5);

b[n_, k_] := b[n, k] = If[n<2, If[kJean-François Alcover, Feb 19 2017, translated from Maple *)

Sum_{k=0..n} k * T(n,k) = A316944(n).

Sum_{k=n..2^n-1} k * T(k,n) = A317012(n).

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

A379758 Number of sequences in which the games of a fully symmetric single-elimination tournament with 2^n teams can be played if arbitrarily many arenas are available.

Original entry on oeis.org

1, 3, 365, 1323338487, 1119556146543237253601352961, 3414445659328795239581367793706562556567987857578516541118092297328702035

Offset: 1

Noah A Rosenberg, Jan 01 2025

nonn

a(n) is also the number of tie-permitting labeled histories for a fully symmetric labeled topology with 2^n leaves.

			For n=2 and a tournament with structure ((A,B),(C,D)), game (A,B) can be played before, after, or simultaneously with game (C,D), producing a(2)=3.

Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307. See Table 5.
Matthew C. King and Noah A. Rosenberg, A mathematical connection between single-elimination sports tournaments and evolutionary trees, Math. Mag. 96 (2023), 484-497.

Cf. A056972 (game sequences with only one arena).

Row sums of A380166.

a(n) = Sum_{k=n..2^n-1} A380166(n,k).

A380166 Triangle read by rows: T(n,k) is the number of sequences in which the games of a fully symmetric single-elimination tournament with 2^n teams can be played if arbitrarily many arenas are available and the number of distinct times at which games are played is k, 1 <= k <= 2^n-1.

Original entry on oeis.org

1, 0, 1, 2, 0, 0, 1, 22, 102, 160, 80, 0, 0, 0, 1, 672, 45914, 973300, 9396760, 49410424, 155188488, 304369008, 376231680, 284951040, 120806400, 21964800, 0, 0, 0, 0, 1, 458324, 2493351562, 1695612148252, 328854102958150, 26894789756402464, 1153061834890296576, 29635726970329429536

Offset: 1

Noah A Rosenberg, Jan 13 2025

T(n,k) is also the number of tie-permitting labeled histories for a fully symmetric labeled topology with 2^n leaves and exactly k times at which events take place.

			Triangle begins:
  1;
  0, 1, 2;
  0, 0, 1, 22, 102,   160,     80;
  0, 0, 0,  1, 672, 45914, 973300, 9396760, 49410424, 155188488, 304369008, 376231680, 284951040, 120806400, 21964800;
  ...
For n = 2 and a tournament with 2^2 = 4 teams and structure ((A,B),(C,D)), game (A,B) can be played before or after game (C,D); the championship game occurs later, producing T(2,3) = 2. Alternatively, game (A,B) can be played simultaneously with (C,D), with the championship game occurring later, producing T(2,2) = 1.

M. C. King and N. A. Rosenberg, A mathematical connection between single-elimination sports tournaments and evolutionary trees, Math. Mag. 96 (2023), 484-497.

Row lengths give A000325(n).
Right border gives A056972(n).
Row sums give A379758(n).

T(1,1) = 1 and for n > 1 and n <= k <= 2^n - 1, T(n,k) = Sum_{c=max(n-1,k-2^(n-1))..min(2^(n-1)-1,k-1)} Sum_{d=max(n-1,k-c-1)..min(2^(n-1)-1,k-1)} ((k-1)! / ((k-1-d)! * (k-1-c)! * (c+d-(k-1))!)) * T(n-1,c) * T(n-1,d).

A363197 a(n) is the number of ways the labels 1 to 2^n-1 can be assigned to a perfect binary tree with n levels such that there is an ordering between children and parents and also an ordering between the left and the right child.

Original entry on oeis.org

1, 1, 10, 343200, 73082837755699200000, 79548797573848497198355214730517854838277265162240000000000

Offset: 1

Thomas Scheuerle, May 21 2023

nonn

We choose one order relation like left > right, parent < child and keep this relation the same while counting all variants which will fit this relation.

Number of permutations {1,2,...,2^n-1} which generate a binary search tree with minimum possible height such that each parent receives the left child first.

			The 10 variants for a(3) are:
    1          1          1
   / \        / \        / \
  5   2      4   2      4   2
 / \ / \    / \ / \    / \ / \
7  6 4  3  7  5 6  3  7  6 5  3
.
    1          1          1
   / \        / \        / \
  4   2      3   2      3   2
 / \ / \    / \ / \    / \ / \
6  5 7  3  5  4 7  6  7  4 6  5
.
    1          1          1
   / \        / \        / \
  3   2      3   2      3   2
 / \ / \    / \ / \    / \ / \
7  5 6  4  7  6 5  4  6  4 7  5
.
    1
   / \
  3   2
 / \ / \
6  5 7  4
.

Cf. A056972, A076615.

RecurrenceTable[{a[n + 1] == Binomial[2^(n + 1) - 2, 2^n - 1]*2^((n^2 - 3*n)/2)*a[n]^2, a[1] == 1}, a, {n, 1, 6}] (* Amiram Eldar, May 21 2023 *)

a(n) = if(n==0,1,binomial(2^n-2, 2^(n-1)-1)*2^((4 - 5*n + n^2)/2)*a(n-1)^2)

a(n) = binomial(2^n - 2, 2^(n-1) - 1)*2^((4 - 5*n + n^2)/2)*a(n-1)^2.

a(n) = A076615(2^n - 1) / 2^(n*(n - 1)/2).

Showing 1-7 of 7 results.

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

A195581 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244108 Number T(n,k) of permutations of {1,2,...,n} that result in a binary search tree of height k; triangle T(n,k), k>=0, k<=n<=2^k-1, read by columns.

Views

Author

Keywords

Comments

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

A379758 Number of sequences in which the games of a fully symmetric single-elimination tournament with 2^n teams can be played if arbitrarily many arenas are available.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A380166 Triangle read by rows: T(n,k) is the number of sequences in which the games of a fully symmetric single-elimination tournament with 2^n teams can be played if arbitrarily many arenas are available and the number of distinct times at which games are played is k, 1 <= k <= 2^n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A363197 a(n) is the number of ways the labels 1 to 2^n-1 can be assigned to a perfect binary tree with n levels such that there is an ordering between children and parents and also an ordering between the left and the right child.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula