A008301 - OEIS

%I #63 Dec 14 2019 08:23:02

%S 1,1,2,1,4,8,10,8,4,34,68,94,104,94,68,34,496,992,1420,1712,1816,1712,

%T 1420,992,496,11056,22112,32176,40256,45496,47312,45496,40256,32176,

%U 22112,11056,349504,699008,1026400,1309568,1528384,1666688,1714000

%N Poupard's triangle: triangle of numbers arising in enumeration of binary trees.

%C The doubloon polynomials evaluated at q=1. [Note the error in (D1) of the Foata-Han article in the Ramanujan journal which should read d_{1,j}(q) = delta_{2,j}.] - _R. J. Mathar_, Jan 27 2011

%C T(n,k), 0 <= k <= 2n-2, is the number of increasing 0-2 trees on vertices [0,2n] in which the parent of 2n is k (Poupard). A little more generally, for fixed m in [k+1,2n], T(n,k) is the number of trees in which m is a leaf with parent k. (The case m=2n is Poupard's result.)  T(n,k) is the number of increasing 0-2 trees on vertices [0,2n] in which the minimal path from the root ends at k+1 (Poupard). - _David Callan_, Aug 23 2011

%H Reinhard Zumkeller, <a href="/A008301/b008301.txt">Rows n = 0..100 of triangle, flattened</a>

%H Neil J. Y. Fan, Liao He, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p45">The Complete cd-Index of Boolean Lattices</a>, Electron. J. Combin., 22 (2015), #P2.45.

%H D. Foata, G.-N. Han, <a href="http://dx.doi.org/10.1007/s11139-009-9194-9">The doubloon polynomial triangle</a>, Ram. J. 23 (2010), 107-126.

%H Dominique Foata and Guo-Niu Han, <a href="http://dx.doi.org/10.1093/qmath/hap043">Doubloons and new q-tangent numbers</a>, Quart. J. Math. 62 (2) (2011) 417-432.

%H D. Foata and G.-N. Han, <a href="http://www-irma.u-strasbg.fr/~foata/paper/pub120.html">Tree Calculus for Bivariable Difference Equations</a>, 2012. - From _N. J. A. Sloane_, Feb 02 2013

%H D. Foata and G.-N. Han, <a href="http://arxiv.org/abs/1304.2484">Tree Calculus for Bivariable Difference Equations</a>, arXiv:1304.2484 [math.CO], 2013.

%H R. L. Graham and Nan Zang, <a href="http://dx.doi.org/10.1016/j.jcta.2007.06.003">Enumerating split-pair arrangements</a>, J. Combin. Theory, Ser. A, 115 (2008), pp. 293-303.

%H C. Poupard, <a href="http://dx.doi.org/10.1016/S0195-6698(89)80009-5">Deux propriétés des arbres binaires ordonnés stricts</a>, European J. Combin., 10 (1989), 369-374.

%F Recurrence relations are given on p. 370 of the Poupard paper; however, in line -5 the summation index should be k and in line -4 the expression 2_h^{k-1} should be replaced by 2d_h^(k-1). - _Emeric Deutsch_, May 03 2004

%F If we write the triangle like this:

%F                  0,    1,   0

%F             0,   1,    2,   1,   0

%F        0,   4,   8,   10,   8,   4,   0

%F   0,  34,  68,  94,  104,  94,  68,  34,  0

%F then the first nonzero term is the sum of the previous row and the remaining terms in each row are obtained by the rule illustrated by 104 = 2*94 - 2*8 - 1*68. - _N. J. A. Sloane_, Jun 10 2005

%F Continuing Sloane's remark: If we also set the line "... 1 ..." on the top of the pyramid, then we obtain T(n,k) = A236934(n+1,k+1)/2^n for n >= 1 and 1 <= k <= 2n-1 (see the second Maple program). - _Peter Luschny_, May 12 2014

%e [1],

%e [1, 2, 1],

%e [4, 8, 10, 8, 4],

%e [34, 68, 94, 104, 94, 68, 34],

%e [496, 992, 1420, 1712, 1816, 1712, 1420, 992, 496],

%e [11056, 22112, 32176, 40256, 45496, 47312, 45496, 40256, 32176, 22112, 11056],

%e [349504, 699008, 1026400, 1309568, 1528384, 1666688, 1714000, 1666688, 1528384, 1309568, 1026400, 699008, 349504], ...

%p doubloon := proc(n,j,q) option remember; if n = 1 then if j=2 then 1; else 0; end if; elif j >= 2*n+1 or ( n>=1 and j<=1 ) then 0 ; elif j=2 and n>=1 then add(q^(k-1)*procname(n-1,k,q),k=1..2*n-2) ; elif n>=2 and 3<=j and j<=2*n then 2*procname(n,j-1,q)-procname(n,j-2,q)-(1-q)*add( q^(n+i+1-j)*procname(n-1,i,q),i=1..j-3) - (1+q^(n-1))*procname(n-1,j-2,q)+(1-q)*add(q^(i-j+1)*procname(n-1,i,q),i=j-1..2*n-1) ; else error; end if; expand(%) ; end proc:

%p A008301 := proc(n,k) doubloon(n+1,k+2,1) ; end proc:

%p seq(seq(A008301(n,k),k=0..2*n),n=0..12) ; # _R. J. Mathar_, Jan 27 2011

%p # Second program based on the Poupard numbers g_n(k) (A236934).

%p T := proc(n,k) option remember; local j;

%p   if n = 1 then 1

%p elif k = 1 then 0

%p elif k = 2 then 2*add(T(n-1, j), j=1..2*n-3)

%p elif k > n then T(n, 2*n-k)

%p else 2*T(n, k-1)-T(n, k-2)-4*T(n-1, k-2)

%p   fi end:

%p A008301 := (n,k) -> T(n+1,k+1)/2^n;

%p seq(print(seq(A008301(n,k), k=1..2*n-1)), n=1..6); # _Peter Luschny_, May 12 2014

%t doubloon[1, 2, q_] = 1; doubloon[1, j_, q_] = 0; doubloon[n_, j_, q_] /; j >= 2n+1 || n >= 1 && j <= 1 = 0; doubloon[n_ /; n >= 1, 2, q_] := doubloon[n, 2, q] = Sum[ q^(k-1)*doubloon[n-1, k, q], {k, 1, 2n-2}]; doubloon[n_, j_, q_] /; n >= 2 <= j && j <= 2n := doubloon[n, j, q] = 2*doubloon[n, j-1, q] - doubloon[n, j-2, q] - (1-q)*Sum[ q^(n+i+1-j)*doubloon[n-1, i, q], {i, 1, j-3}] - (1 + q^(n-1))*doubloon[n-1, j-2, q] + (1-q)* Sum[ q^(i-j+1)*doubloon[n-1, i, q], {i, j-1, 2n-1}]; A008301[n_,k_] := doubloon[n+1, k+2, 1]; Flatten[ Table[ A008301[n, k], {n, 0, 6}, {k, 0, 2n}]] (* _Jean-François Alcover_, Jan 23 2012, after _R. J. Mathar_ *)

%t T[n_, k_] := T[n, k] = Which[n==1, 1, k==1, 0, k==2, 2*Sum[T[n-1, j], {j, 1, 2*n-3}], k>n, T[n, 2*n-k], True, 2*T[n, k-1] - T[n, k-2] - 4*T[n-1, k - 2]]; A008301[n_, k_] := T[n+1, k+1]/2^n; Table[A008301[n, k], {n, 1, 6}, {k, 1, 2*n-1}] // Flatten (* _Jean-François Alcover_, Nov 28 2015, after _Peter Luschny_ *)

%o (Haskell)

%o a008301 n k = a008301_tabf !! n !! k

%o a008301_row n = a008301_tabf !! n

%o a008301_tabf = iterate f [1] where

%o    f zs = zs' ++ tail (reverse zs') where

%o      zs' = (sum zs) : h (0 : take (length zs `div` 2) zs) (sum zs) 0

%o      h []     _  _ = []

%o      h (x:xs) y' y = y'' : h xs y'' y' where y'' = 2*y' - 2*x - y

%o -- _Reinhard Zumkeller_, Mar 17 2012

%Y Cf. A107652. Leading diagonal and row sums = A002105.

%Y Cf. A210108 (left half).

%K nonn,tabf,easy,nice

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Emeric Deutsch_, May 03 2004