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

Author

N. J. A. Sloane

Keywords

• nonn
• tabf
• easy
• nice

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

Examples

			[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], ...
		

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.

Crossrefs

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

Cf. A210108 (left half).

Programs

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

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

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

Extensions

More terms from Emeric Deutsch, May 03 2004