|
Search: id:A133385
|
|
|
| A133385 |
|
Number of permutations of n elements divided by the number of heaps on n+1 elements. |
|
+0
1
|
|
| 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; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
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.
|
|
LINKS
|
Alois P. Heinz, Table of n, a(n) for n = 0..100
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics
|
|
FORMULA
|
a(n) = A132862(n+1)/(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<=1 then RETURN (1) fi; b:=2^trunc(simplify(log[2](n))); nl := min (b-1, n-b/2); RETURN (n*aa(nl)*aa(n-1-nl)); end; a:=n->aa(n+1)/(n+1); seq(a(i), i=0..50);
|
|
CROSSREFS
|
Cf. A000142, A056971, A132862.
Sequence in context: A095064 A056353 A111274 this_sequence A002076 A071714 A077753
Adjacent sequences: A133382 A133383 A133384 this_sequence A133386 A133387 A133388
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Alois P. Heinz (heinz(AT)hs-heilbronn.de), Nov 22 2007
|
|
|
Search completed in 0.002 seconds
|
