cp's OEIS Frontend

A133385 Number of permutations of n elements divided by the number of (binary) heaps on n+1 elements.

%I A133385 #41 Aug 19 2025 09:15:46
%S A133385 1,1,1,2,3,6,9,24,45,108,189,504,945,2268,3969,12096,25515,68040,
%T A133385 130977,381024,773955,2000376,3750705,11430720,24111675,64297800,
%U A133385 123773265,360067680,731387475,1890355320,3544416225,11522165760,25823603925,72913705200,148156598205
%N A133385 Number of permutations of n elements divided by the number of (binary) heaps on n+1 elements.
%C A133385 In a min-heap on (n+1) distinct elements only n elements can change places, since the first element is determined to be the minimum. a(n) gives the number of all possibilities divided by the number of legal possibilities to do this.
%C A133385 Is this the sequence mentioned on page 360 of Motzkin (1948)? - _N. J. A. Sloane_, Jul 04 2015
%H A133385 Alois P. Heinz, <a href="/A133385/b133385.txt">Table of n, a(n) for n = 0..2450</a>
%H A133385 T. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%H A133385 T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4 ">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360.
%H A133385 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Heap.html">Heap</a>
%H A133385 Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F A133385 a(n) = A132862(n+1)/(n+1) = A000142(n)/A056971(n+1).
%e A133385 a(4) = 3 because 3 = 24/8 and there are 4! = 24 permutations on 4 elements and 8 min-heaps on 5 elements, namely (0,1,2,3,4), (0,1,2,4,3), (0,1,3,2,4), (0,1,3,4,2), (0,1,4,2,3), (0,1,4,3,2), (0,2,1,3,4), and (0,2,1,4,3). In every (min-) heap, the element at position i has to be larger than the element at position floor(i/2) for all i=2..n. The minimum is always found at position 1.
%p A133385 h:= proc(n) option remember; `if`(n=0, 1, (b-> (f->
%p A133385       h(f)*n*h(n-1-f))(min(b-1, n-b/2)))(2^ilog2(n)))
%p A133385     end:
%p A133385 a:= n-> h(n+1)/(n+1):
%p A133385 seq(a(n), n=0..50);
%t A133385 aa[n_] := aa[n] = Module[{b, nl}, If[n<2, 1, b = 2^Floor[Log[2, n]]; nl = Min[b-1, n-b/2]; n*aa[nl]*aa[n-1-nl]]]; a[n_] := aa[n+1]/(n+1); Table[a[i], {i, 0, 50}] (* _Jean-François Alcover_, Mar 05 2014, after _Alois P. Heinz_ *)
%Y A133385 Cf. A000142, A056971, A132862.
%Y A133385 Column k=2 of A273730.
%K A133385 nonn
%O A133385 0,4
%A A133385 _Alois P. Heinz_, Nov 22 2007