A273712 -id:A273712 - cp's OEIS frontend

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

Alois P. Heinz, May 28 2016

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

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

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.

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

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

A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).

Original entry on oeis.org

1, 1, 2, 80, 21964800, 74836825861835980800000, 2606654998899867556195703676289609067340669424836280320000000000

Offset: 0

Eric W. Weisstein

nonn

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

a(n) is also the number of knockout tournament seedings that satisfy the increasing competitive intensity property. - Alexander Karpov, Aug 18 2015

a(n) is the number of coalescence sequences, or labeled histories, for a binary, leaf-labeled, rooted tree topology with 2^n leaves (Rosenberg 2006, Theorem 3.3 for a completely symmetric tree with 2^n leaves, dividing by Theorem 3.2 for 2^n leaves). - Noah A Rosenberg, Feb 12 2019

a(n+1) is also the number of random walk labelings of the perfect binary tree of height n, that begin at the root. - Sela Fried, Aug 02 2023

If a bracket of 2^n teams is specified for a single-elimination tournament, a(n) is the number of sequences in which the games of the tournament can be played in a single arena. - Noah A Rosenberg, Jan 01 2025

			There is 1 heap on 2^0-1=0 elements, 1 heap on 2^1-1=1 element and there are 2 heaps on 2^2-1=3 elements and so on.

Alois P. Heinz, Table of n, a(n) for n = 0..9
Emily H. Dickey and Noah A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307.
Sela Fried and Toufik Mansour, Random walk labelings of perfect trees and other graphs, arXiv:2308.00315 [math.CO], 2023.
Alexander Karpov, A theory of knockout tournament seedings, Heidelberg University, AWI Discussion Paper Series, No. 600.
Matthew C. King and Noah A. Rosenberg, A mathematical connection between single-elimination sports tournaments and evolutionary trees, Math. Mag. 96 (2023), 484-497.
Egor Lappo and Noah A. Rosenberg, A lattice structure for ancestral configurations arising from the relationship between gene trees and species trees, Adv. Appl. Math. 343 (2024), 65-81.
Noah A. Rosenberg, The Mean and Variance of the Numbers of r-Pronged Nodes and r-Caterpillars in Yule-Generated Genealogical Trees, Ann. Combinator. 10 (2006), 129-146.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000225, A056971, A195581.

Column k=2 of A273712.

a:= n-> (2^n-1)!/mul((2^k-1)^(2^(n-k)), k=1..n):
seq(a(i), i=0..6);  # Alois P. Heinz, Nov 22 2007

s[1] := 1; s[l_] := s[l] := Binomial[2^l-2, 2^(l-1)-1]s[l-1]^2; Table[s[l], {l, 10}]

from math import prod, factorial
def A056972(n): return factorial((1<Chai Wah Wu, May 06 2024

a(n) = A056971(A000225(n)).
a(n) = A195581(2^n-1,n).
a(n) = binomial(2^n-2, 2^(n-1)-1)*a(n-1)^2. - Robert Israel, Aug 18 2015, from the Mathematica program
a(n) = (2^n-1)!/Product_{k=1..n} (2^k-1)^(2^(n-k)). - Robert Israel, Aug 18 2015, from the Maple program

A273723 Number of ternary heaps on n levels (i.e., of (3^n-1)/2 elements).

Original entry on oeis.org

1, 1, 6, 7484400, 35417271278873496315860673177600000000

Offset: 0

Alois P. Heinz, May 28 2016

nonn

a(n) is also the number of labeled histories for a fully symmetric trifurcating labeled topology with 3^n leaves. - Noah A Rosenberg, Feb 24 2025

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

Column k=3 of A273712.

Cf. A003462, A178008.

a(n) = A178008(A003462(n)).

A273725 Number of quaternary heaps on n levels (i.e., of (4^n-1)/3 elements).

Original entry on oeis.org

1, 1, 24, 3892643213082624

Offset: 0

Alois P. Heinz, May 28 2016

nonn

a(n) is also the number of labeled histories for a fully symmetric quadfurcating labeled topology with 4^n leaves. - Noah A Rosenberg, Feb 24 2025

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

Column k=4 of A273712.

Cf. A002450, A178009.

a(n) = A178009(A002450(n)).

A273729 Number of n-ary heaps on n levels (i.e., of A023037(n) elements).

Original entry on oeis.org

1, 1, 2, 7484400

Offset: 0

Alois P. Heinz, May 28 2016

nonn

a(5), a(6), a(7) have 1774, 31436, 625065 decimal digits, respectively.

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

Main diagonal of A273712.

Cf. A023037.

a(n) = A273712(n,n).

Showing 1-5 of 5 results.

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A056972 Number of (binary) heaps on n levels (i.e., of 2^n - 1 elements).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A273723 Number of ternary heaps on n levels (i.e., of (3^n-1)/2 elements).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A273725 Number of quaternary heaps on n levels (i.e., of (4^n-1)/3 elements).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A273729 Number of n-ary heaps on n levels (i.e., of A023037(n) elements).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula