A273730 -id:A273730 - cp's OEIS frontend

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

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

Alois P. Heinz, Nov 22 2007

nonn

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

			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.

Alois P. Heinz, Table of n, a(n) for n = 0..2450
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

Cf. A000142, A056971, A132862.

Column k=2 of A273730.

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);

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 *)

a(n) = A132862(n+1)/(n+1) = A000142(n)/A056971(n+1).

A273731 Number of permutations of n elements divided by the number of ternary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 8, 12, 16, 32, 48, 64, 160, 288, 448, 1024, 1728, 2560, 5632, 9216, 13312, 33280, 59904, 93184, 212992, 359424, 532480, 1171456, 1916928, 2768896, 6922240, 12460032, 19382272, 44302336, 74760192, 110755840, 243662848, 398721024, 575930368

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=3 of A273730.

Cf. A000142, A178008.

a(n) = A000142(n)/A178008(n+1).

A273732 Number of permutations of n elements divided by the number of quaternary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 4, 5, 10, 15, 20, 25, 50, 75, 100, 125, 250, 375, 500, 625, 1500, 2625, 4000, 5625, 12500, 20625, 30000, 40625, 87500, 140625, 200000, 265625, 562500, 890625, 1250000, 1640625, 3937500, 6890625, 10500000, 14765625, 32812500, 54140625

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=4 of A273730.

Cf. A000142, A178009.

a(n) = A000142(n)/A178009(n+1).

A273733 Number of permutations of n elements divided by the number of 5-ary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 12, 18, 24, 30, 36, 72, 108, 144, 180, 216, 432, 648, 864, 1080, 1296, 2592, 3888, 5184, 6480, 7776, 18144, 31104, 46656, 64800, 85536, 186624, 303264, 435456, 583200, 746496, 1586304, 2519424, 3545856, 4665600, 5878656

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=5 of A273730.

Cf. A000142, A178010.

a(n) = A000142(n)/A178010(n+1).

A273734 Number of permutations of n elements divided by the number of 6-ary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 14, 21, 28, 35, 42, 49, 98, 147, 196, 245, 294, 343, 686, 1029, 1372, 1715, 2058, 2401, 4802, 7203, 9604, 12005, 14406, 16807, 33614, 50421, 67228, 84035, 100842, 117649, 268912, 453789, 672280, 924385, 1210104, 1529437

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=6 of A273730.

Cf. A000142, A178011.

a(n) = A000142(n)/A178011(n+1).

A273735 Number of permutations of n elements divided by the number of 7-ary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 16, 24, 32, 40, 48, 56, 64, 128, 192, 256, 320, 384, 448, 512, 1024, 1536, 2048, 2560, 3072, 3584, 4096, 8192, 12288, 16384, 20480, 24576, 28672, 32768, 65536, 98304, 131072, 163840, 196608, 229376, 262144, 524288

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=7 of A273730.

Cf. A000142, A273694.

a(n) = A000142(n)/A273694(n+1).

A273736 Number of permutations of n elements divided by the number of 8-ary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 18, 27, 36, 45, 54, 63, 72, 81, 162, 243, 324, 405, 486, 567, 648, 729, 1458, 2187, 2916, 3645, 4374, 5103, 5832, 6561, 13122, 19683, 26244, 32805, 39366, 45927, 52488, 59049, 118098, 177147, 236196, 295245

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=8 of A273730.

Cf. A000142, A273695.

a(n) = A000142(n)/A273695(n+1).

A273737 Number of permutations of n elements divided by the number of 9-ary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000, 100000

Offset: 0

Alois P. Heinz, May 28 2016

nonn

The first term with more than one nonzero digit (and thus not a member of A037124) is a(91) = 2200000000.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=9 of A273730.

Cf. A000142, A037124, A273696.

a(n) = A000142(n)/A273696(n+1).

A273738 Number of permutations of n elements divided by the number of 10-ary heaps on n+1 elements.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 242, 363, 484, 605, 726, 847, 968, 1089, 1210, 1331, 2662, 3993, 5324, 6655, 7986, 9317, 10648, 11979, 13310, 14641, 29282, 43923, 58564, 73205, 87846

Offset: 0

Alois P. Heinz, May 28 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, D-ary heap

Column k=10 of A273730.

Cf. A000142, A273697.

a(n) = A000142(n)/A273697(n+1).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A273731 Number of permutations of n elements divided by the number of ternary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A273732 Number of permutations of n elements divided by the number of quaternary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A273733 Number of permutations of n elements divided by the number of 5-ary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A273734 Number of permutations of n elements divided by the number of 6-ary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A273735 Number of permutations of n elements divided by the number of 7-ary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A273736 Number of permutations of n elements divided by the number of 8-ary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula

A273737 Number of permutations of n elements divided by the number of 9-ary heaps on n+1 elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A273738 Number of permutations of n elements divided by the number of 10-ary heaps on n+1 elements.

Views

Author

Keywords

Links

Crossrefs

Formula