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

Comments

A sequence {a_i}_{i=1..N} forms a (binary) heap if it satisfies a_i<a_{2i} and a_i<a_{2i+1} for 1<=i<=(N-1)/2.

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

Links

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

Formula

See recurrence in Maple and Mma programs.

Example

There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on.

Maple

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

Mathematica

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

Prog

(Python)
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<<h)-1
    r = n-1-(b<<1)
    r1 = r-(r//(b+1))*(r-b-1)
    r2 = r-r1
    return comb(n-1, b+r1)*A056971(b+r1)*A056971(b+r2) # Chai Wah Wu, May 06 2024

Crossrefs

Cf. A053644, A056972, A132862.

Column k=2 of A273693.

Column k=0 of A306343 and of A306393.

Sequence in context: A073268 A073190 A066051 * A108125 A175490 A118854

Adjacent sequences: A056968 A056969 A056970 * A056972 A056973 A056974

Keyword

nonn,easy,changed

Author

Eric W. Weisstein

Extensions

More terms from Sascha Kurz, Mar 24 2002

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

Status

approved