login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

In a 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

Alois P. Heinz, Table of n, a(n) for n = 0..1000

T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.

T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.

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 heaps on 5 elements, namely (1,2,3,4,5), (1,2,3,5,4), (1,2,4,3,5), (1,2,4,5,3), (1,2,5,3,4), (1,2,5,4,3), (1,3,2,4,5) and (1,3,2,5,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. The minimum is always found at position 1.

MAPLE

aa:= proc(n) option remember; local b, nl; if n<2 then 1 else b:= 2^ilog[2](n); nl:= min(b-1, n-b/2); n *aa(nl) *aa(n-1-nl): fi end: a:= n-> aa(n+1)/(n+1): seq(a(i), i=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

Cf. A000142, A056971, A132862.

Column k=2 of A273730.

Sequence in context: A323144 A056353 A111274 * A002076 A286435 A145761

Adjacent sequences:  A133382 A133383 A133384 * A133386 A133387 A133388

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Nov 22 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 11 01:51 EDT 2020. Contains 335600 sequences. (Running on oeis4.)