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

1, 1, 2, 1, 4, 8, 10, 8, 4, 34, 68, 94, 104, 94, 68, 34, 496, 992, 1420, 1712, 1816, 1712, 1420, 992, 496, 11056, 22112, 32176, 40256, 45496, 47312, 45496, 40256, 32176, 22112, 11056, 349504, 699008, 1026400, 1309568, 1528384, 1666688, 1714000

Offset

0,3

Comments

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

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

Links

Reinhard Zumkeller, Rows n = 0..100 of triangle, flattened

Neil J. Y. Fan, Liao He, The Complete cd-Index of Boolean Lattices, Electron. J. Combin., 22 (2015), #P2.45.

D. Foata, G.-N. Han, The doubloon polynomial triangle, Ram. J. 23 (2010), 107-126.

Dominique Foata and Guo-Niu Han, Doubloons and new q-tangent numbers, Quart. J. Math. 62 (2) (2011) 417-432.

D. Foata and G.-N. Han, Tree Calculus for Bivariable Difference Equations, 2012. - From N. J. A. Sloane, Feb 02 2013

D. Foata and G.-N. Han, Tree Calculus for Bivariable Difference Equations, arXiv:1304.2484 [math.CO], 2013.

R. L. Graham and Nan Zang, Enumerating split-pair arrangements, J. Combin. Theory, Ser. A, 115 (2008), pp. 293-303.

C. Poupard, Deux propriétés des arbres binaires ordonnés stricts, European J. Combin., 10 (1989), 369-374.

Formula

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

If we write the triangle like this:

0, 1, 0

0, 1, 2, 1, 0

0, 4, 8, 10, 8, 4, 0

0, 34, 68, 94, 104, 94, 68, 34, 0

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

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

Example

[1],
[1, 2, 1],
[4, 8, 10, 8, 4],
[34, 68, 94, 104, 94, 68, 34],
[496, 992, 1420, 1712, 1816, 1712, 1420, 992, 496],
[11056, 22112, 32176, 40256, 45496, 47312, 45496, 40256, 32176, 22112, 11056],
[349504, 699008, 1026400, 1309568, 1528384, 1666688, 1714000, 1666688, 1528384, 1309568, 1026400, 699008, 349504], ...

Maple

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:
A008301 := proc(n, k) doubloon(n+1, k+2, 1) ; end proc:
seq(seq(A008301(n, k), k=0..2*n), n=0..12) ; # R. J. Mathar, Jan 27 2011
# Second program based on the Poupard numbers g_n(k) (A236934).
T := proc(n, k) option remember; local j;
  if n = 1 then 1
elif k = 1 then 0
elif k = 2 then 2*add(T(n-1, j), j=1..2*n-3)
elif k > n then T(n, 2*n-k)
else 2*T(n, k-1)-T(n, k-2)-4*T(n-1, k-2)
  fi end:
A008301 := (n, k) -> T(n+1, k+1)/2^n;
seq(print(seq(A008301(n, k), k=1..2*n-1)), n=1..6); # Peter Luschny, May 12 2014

Mathematica

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

Prog

(Haskell)
a008301 n k = a008301_tabf !! n !! k
a008301_row n = a008301_tabf !! n
a008301_tabf = iterate f [1] where
   f zs = zs' ++ tail (reverse zs') where
     zs' = (sum zs) : h (0 : take (length zs `div` 2) zs) (sum zs) 0
     h []     _  _ = []
     h (x:xs) y' y = y'' : h xs y'' y' where y'' = 2*y' - 2*x - y
-- Reinhard Zumkeller, Mar 17 2012

Crossrefs

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

Cf. A210108 (left half).

Sequence in context: A058543 A353661 A156817 * A363386 A294104 A294061

Adjacent sequences: A008298 A008299 A008300 * A008302 A008303 A008304

Keyword

nonn,tabf,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Emeric Deutsch, May 03 2004

Status

approved