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. [broken link]
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.
a(5) = 8 (min-heaps): 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.
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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
EXTENSIONS
More terms from Sascha Kurz, Mar 24 2002
Offset and some terms corrected by Alois P. Heinz, Nov 21 2007
STATUS
approved