cp's OEIS Frontend

A056971 Number of (binary) heaps on n elements.

%I A056971 #79 Aug 08 2025 06:19:04
%S A056971 1,1,1,2,3,8,20,80,210,896,3360,19200,79200,506880,2745600,21964800,
%T A056971 108108000,820019200,5227622400,48881664000,319258368000,
%U A056971 3143467008000,25540669440000,299677188096000,2261626278912000,25732281217843200,241240136417280000
%N A056971 Number of (binary) heaps on n elements.
%C A056971 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 A056971 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 A056971 Note that A132862(n)*a(n) = n!. - _Alois P. Heinz_, Nov 22 2007
%H A056971 Alois P. Heinz, <a href="/A056971/b056971.txt">Table of n, a(n) for n = 0..500</a>
%H A056971 Sean Cleary, M. Fischer, R. C. Griffiths, and 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 A056971 D. Levin, L. Pudwell, M. Riehl, and A. Sandberg, <a href="https://web.archive.org/web/20170829204529/https://www.etsu.edu/cas/math/pp2014/documents/talks/riehl.pdf">Pattern Avoidance on k-ary Heaps</a>, Slides of Talk, 2014.
%H A056971 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A056971 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A056971 See recurrence in Maple and Mma programs.
%e A056971 There is 1 heap if n is in {0,1,2}, 2 heaps for n=3, 3 heaps for n=4 and so on.
%e A056971 a(5) = 8 (min-heaps): 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254.
%p A056971 a[0] := 1: a[1] := 1:
%p A056971 for n from 2 to 50 do
%p A056971 h := ilog2(n+1)-1:
%p A056971 b := 2^h-1: r := n-1-2*b: r1 := r-floor(r/2^h)*(r-2^h): r2 := r-r1:
%p A056971 a[n] := binomial(n-1, b+r1)*a[b+r1]*a[b+r2]:end do:
%p A056971 q := seq(a[j], j=0..50);
%p A056971 # second Maple program:
%p A056971 a:= proc(n) option remember; `if`(n=0, 1, (g-> (f-> a(f)*
%p A056971       binomial(n-1, f)*a(n-1-f))(min(g-1, n-g/2)))(2^ilog2(n)))
%p A056971     end:
%p A056971 seq(a(n), n=0..28);  # _Alois P. Heinz_, Feb 14 2019
%t A056971 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 *)
%o A056971 (Python)
%o A056971 from functools import lru_cache
%o A056971 from math import comb
%o A056971 @lru_cache(maxsize=None)
%o A056971 def A056971(n):
%o A056971     if n<=1: return 1
%o A056971     h = (n+1).bit_length()-2
%o A056971     b = (1<<h)-1
%o A056971     r = n-1-(b<<1)
%o A056971     r1 = r-(r//(b+1))*(r-b-1)
%o A056971     r2 = r-r1
%o A056971     return comb(n-1,b+r1)*A056971(b+r1)*A056971(b+r2) # _Chai Wah Wu_, May 06 2024
%Y A056971 Cf. A053644, A056972, A132862, A373452 (allows repeated elements).
%Y A056971 Column k=2 of A273693.
%Y A056971 Column k=0 of A306343 and of A306393.
%Y A056971 Main diagonal of A373451.
%K A056971 nonn,easy
%O A056971 0,4
%A A056971 _Eric W. Weisstein_
%E A056971 More terms from _Sascha Kurz_, Mar 24 2002
%E A056971 Offset and some terms corrected by _Alois P. Heinz_, Nov 21 2007