cp's OEIS Frontend

A132862 Number of permutations divided by the number of (binary) heaps on n elements.

%I A132862 #81 Aug 19 2025 09:12:34
%S A132862 1,1,2,3,8,15,36,63,192,405,1080,2079,6048,12285,31752,59535,193536,
%T A132862 433755,1224720,2488563,7620480,16253055,44008272,86266215,274337280,
%U A132862 602791875,1671742800,3341878155,10081895040,21210236775,56710659600,109876902975,368709304320
%N A132862 Number of permutations divided by the number of (binary) heaps on n elements.
%C A132862 a(n) is an integer multiple of n for all n>=1.
%C A132862 a(n) gives the number of complete binary trees on the n numbers from 1 to n (under the same definition of complete used for heaps) with the property that, at each node of the tree, each left descendant is less than each right descendant. For instance, for n=5, there are 15 such trees, determined by a choice of any value at the root and any of the three smallest remaining values as its left child. a(n) can be computed from an unlabeled complete tree on n nodes as the product of the numbers of descendants of each node (including the node itself). - _David Eppstein_, Mar 18 2016
%C A132862 a(n-1) gives 2 to the power of the minimal value of the s-shape statistic of rooted binary trees with n leaves. - _Mareike Fischer_, Aug 08 2025
%H A132862 Alois P. Heinz, <a href="/A132862/b132862.txt">Table of n, a(n) for n = 0..2442</a>
%H A132862 Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger, Isabella Larcher, and Mehdi Naima, <a href="https://arxiv.org/abs/2005.12997">Compaction for two models of logarithmic-depth trees: Analysis and Experiments</a>, arXiv:2005.12997 [math.CO], 2020.
%H A132862 Sean Cleary, Mareike Fischer, and Katherine St. John, <a href="https://arxiv.org/abs/2502.12854">The GFB Tree and Tree Imbalance Indices</a>, arXiv:2502.12854 [q-bio.PE], 2025. See pp. 14, 16.
%H A132862 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A132862 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A132862 a(n) = n * a(f) * a(n-1-f) with f = min(b-1,n-b/2) and b = 2^floor(log_2(n)) for n>0, a(0) = 1.
%F A132862 a(n) = A000142(n)/A056971(n).
%F A132862 From _Mareike Fischer_, Aug 08 2025: (Start)
%F A132862 a(n-1) = Product_{i=2..n} (i-1)^q(n,i), with
%F A132862   q(n,i) = floor(n/i)   if i=2^(k(i)) and ((n mod i)=0 or (n mod i) >= 2^(k(i)-1)),
%F A132862          = floor(n/i)-1 if i=2^(k(i)) and (0 < (n mod i) < 2^(k(i)-1)),
%F A132862          = 1 if (i != 2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) = 0 ),
%F A132862          = 0 if (i != 2^(k(i)) and ( (n-i) mod 2^(k(i)-1)) > 0 ) and
%F A132862   k(n) = ceiling(log_2(n)) = A029837(n).
%F A132862 Or also, a(n-1) = Product_{i=0..k(n)-1} (2^(k(n)-i)-1)^(2^i) if d(n)=2^(k(n)-1). Else, a(n-1) = (Product_{i=0..k(n)-2} (2^(k(n)-i-1)-1)^(2^i)) * Product_{i=1..k(n)-1} ( ((2^(i+1)-1)/(2^i-1))^floor(d(n)/(2^i)) * ( ( 2^i + (d(n)-2^i*floor(d(n)/(2^i)))-1 ) / (2^i-1) )^(ceiling(d(n)/(2^i))-floor(d(n)/(2^i)))) if d(n) < 2^(k(n)-1), with k(n)=ceiling(log_2(n))= A029837(n) and d(n)=n-2^(k(n)-1). (End)
%e A132862 a(4) = 8 because 8 = 24/3 and there are 24 permutations on 4 elements, 3 of which are heaps, namely (1,2,3,4), (1,2,4,3) and (1,3,2,4). In every (min-) heap, the element at position i has to be larger than an element at position floor(i/2) for all i=2..n.
%p A132862 a:= proc(n) option remember; `if`(n=0, 1, (b-> (f->
%p A132862       a(f)*n*a(n-1-f))(min(b-1, n-b/2)))(2^ilog2(n)))
%p A132862     end:
%p A132862 seq(a(n), n=0..50);
%t A132862 a[n_] := a[n] = Module[{b, nl}, If[n<2, 1, b = 2^Floor[Log[2, n]]; nl = Min[b-1, n-b/2]; n*a[nl]*a[n-1-nl]]]; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Mar 05 2014, after _Alois P. Heinz_ *)
%Y A132862 Cf. A000142, A029837, A053644, A056971, A133385, A386912.
%K A132862 nonn
%O A132862 0,3
%A A132862 _Alois P. Heinz_, Nov 18 2007