login
A133385
Number of permutations of n elements divided by the number of (binary) heaps on n+1 elements.
3
1, 1, 1, 2, 3, 6, 9, 24, 45, 108, 189, 504, 945, 2268, 3969, 12096, 25515, 68040, 130977, 381024, 773955, 2000376, 3750705, 11430720, 24111675, 64297800, 123773265, 360067680, 731387475, 1890355320, 3544416225, 11522165760, 25823603925, 72913705200, 148156598205
OFFSET
0,4
COMMENTS
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.
Is this the sequence mentioned on page 360 of Motzkin (1948)? - N. J. A. Sloane, Jul 04 2015
LINKS
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap
FORMULA
a(n) = A132862(n+1)/(n+1) = A000142(n)/A056971(n+1).
EXAMPLE
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.
MAPLE
h:= proc(n) option remember; `if`(n=0, 1, (b-> (f->
h(f)*n*h(n-1-f))(min(b-1, n-b/2)))(2^ilog2(n)))
end:
a:= n-> h(n+1)/(n+1):
seq(a(n), n=0..50);
MATHEMATICA
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 *)
CROSSREFS
Column k=2 of A273730.
Sequence in context: A323144 A056353 A111274 * A349148 A002076 A286435
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Nov 22 2007
STATUS
approved