|
| |
|
|
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
|
|
|
REFERENCES
|
D. Foata and G.-N. Han, Tree Calculus for Bivariable Difference Equations, 2012, http://www-irma.u-strasbg.fr/~foata/paper/pub120DeltaMatrices.pdf. - From N. J. A. Sloane, Feb 02 2013
R. L. Graham and Nan Zang, Enumerating split-pair arrangements, J. Combin. Theory, Ser. A, 115 (2008), pp. 293-303.
C. Poupard, Deux proprietes des arbres binaires ordonnes stricts, European J. Combin., 10 (1989), 369-374.
|
|
|
LINKS
|
_Reinhard Zumkeller_, Rows n = 0..100 of triangle, flattened
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
|
|
|
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
|
|
|
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
|
|
|
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}]] (* From Jean-François Alcover, Jan 23 2012, after R. J. Mathar *)
|
|
|
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 * A113820 A133267 A145864
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
|
| |
|
|
