|
%I #61 Oct 18 2019 16:39:05
%S 1,1,1,2,3,8,20,80,210,896,3360,19200,79200,506880,2745600,21964800,
%T 108108000,820019200,5227622400,48881664000,319258368000,
%U 3143467008000,25540669440000,299677188096000,2261626278912000,25732281217843200,241240136417280000
%N Number of (binary) heaps on n elements.
%C 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.
%C 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
%C Note that A132862(n)*a(n) = n!. - _Alois P. Heinz_, Nov 22 2007
%H Alois P. Heinz, <a href="/A056971/b056971.txt">Table of n, a(n) for n = 0..500</a>
%H Sean Cleary, M Fischer, RC Griffiths, R Sainudiin, <a href="http://lamastex.org/preprints/20151231_SomeDistsFRBTrees.pdf">Some distributions on finite rooted binary trees</a>, UCDMS Research Report NO. UCDMS2015/2, School of Mathematics and Statistics, University of Canterbury, Christchurch, NZ, 2015.
%H D. Levin, L. Pudwell, M. Riehl, A. Sandberg, <a href="http://www.etsu.edu/cas/math/pp2014/documents/talks/riehl.pdf">Pattern Avoidance on k-ary Heaps</a>, Slides of Talk, 2014.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Heap.html">Heap</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F See recurrence in Maple and Mma programs.
%e There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on.
%p a[0] := 1: a[1] := 1:
%p for n from 2 to 50 do
%p h := ilog2(n+1)-1:
%p b := 2^h-1: r := n-1-2*b: r1 := r-floor(r/2^h)*(r-2^h): r2 := r-r1:
%p a[n] := binomial(n-1, b+r1)*a[b+r1]*a[b+r2]:end do:
%p q := seq(a[j], j=0..50);
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> a(f)*
%p binomial(n-1, f)*a(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
%p end:
%p seq(a(n), n=0..28); # _Alois P. Heinz_, Feb 14 2019
%t 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 *)
%Y Cf. A053644, A056972, A132862.
%Y Column k=2 of A273693.
%Y Column k=0 of A306343 and of A306393.
%K nonn,easy
%O 0,4
%A _Eric W. Weisstein_
%E More terms from _Sascha Kurz_, Mar 24 2002
%E Offset and some terms corrected by _Alois P. Heinz_, Nov 21 2007
|
