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
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.
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
Comments