login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008301 Poupard's triangle: triangle of numbers arising in enumeration of binary trees. 10
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 (list; graph; refs; listen; history; text; internal format)
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: A112173 A058543 A156817 * A294104 A294061 A113820

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 19 17:22 EDT 2018. Contains 305594 sequences. (Running on oeis4.)