|
%I #27 May 28 2016 20:01:27
%S 1,1,1,2,3,6,9,24,45,108,189,504,945,2268,3969,12096,25515,68040,
%T 130977,381024,773955,2000376,3750705,11430720,24111675,64297800,
%U 123773265,360067680,731387475,1890355320,3544416225,11522165760,25823603925
%N Number of permutations of n elements divided by the number of (binary) heaps on n+1 elements.
%C 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.
%C Is this the sequence mentioned on page 360 of Motzkin (1948)? - _N. J. A. Sloane_, Jul 04 2015
%H Alois P. Heinz, <a href="/A133385/b133385.txt">Table of n, a(n) for n = 0..1000</a>
%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Heap.html">Heap</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Binary_heap">Binary heap</a>
%F a(n) = A132862(n+1)/(n+1) = A000142(n)/A056971(n+1).
%e 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.
%p 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);
%t 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 Cf. A000142, A056971, A132862.
%Y Column k=2 of A273730.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Nov 22 2007
|
