A105632 Triangle, read by rows, where the g.f. A(x,y) satisfies the equation: A(x,y) = 1/(1-x*y) + x*A(x,y) + x^2*A(x,y)^2.

1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 7, 4, 1, 1, 21, 19, 10, 5, 1, 1, 51, 51, 31, 13, 6, 1, 1, 127, 141, 91, 45, 16, 7, 1, 1, 323, 393, 276, 141, 61, 19, 8, 1, 1, 835, 1107, 834, 461, 201, 79, 22, 9, 1, 1, 2188, 3139, 2535, 1485, 701, 271, 99, 25, 10, 1, 1, 5798, 8953, 7711, 4803, 2381, 1001, 351, 121, 28, 11, 1, 1

Offset

0,4

Comments

Column 0 is A001006 (Motzkin numbers). Column 1 is A002426 (Central trinomial coefficients). Row sums form A105633 (also equal to A057580?).

T(n,k) is the number of UUDU-avoiding Dyck paths of semilength n+1 with k UDUs, where U = (1,1) is an upstep and D = (1,-1) is a downstep. For example, T(3,1) = 3 counts UDUUUDDD, UDUUDDUD, UUDDUDUD. - David Callan, Nov 25 2021

Links

Table of n, a(n) for n=0..77.

Formula

G.f. for column k (k>0): Sum_{j=0..k-1} C(k-1, j)*A000108(j)*x^(2*j)/(1-2*x-3*x^2)^(j+1/2), where A000108(j) = binomial(2*j, j)/(j+1) is the j-th Catalan number.

G.f.: A(x, y) = (1-x - sqrt((1-x)^2 - 4*x^2/(1-x*y)))/(2*x^2).

Example

Triangle begins:
    1;
    1,    1;
    2,    1,   1;
    4,    3,   1,   1;
    9,    7,   4,   1,   1;
   21,   19,  10,   5,   1,  1;
   51,   51,  31,  13,   6,  1,  1;
  127,  141,  91,  45,  16,  7,  1, 1;
  323,  393, 276, 141,  61, 19,  8, 1, 1;
  835, 1107, 834, 461, 201, 79, 22, 9, 1, 1; ...
Let G = (1-2*x-3*x^2), then the column g.f.s are:
k=1: 1/sqrt(G)
k=2: (G + (1)*1*x^2)/sqrt(G^3)
k=3: (G^2 + (1)*2*x^2*G + (2)*1*x^4)/sqrt(G^5)
k=4: (G^3 + (1)*3*x^2*G^2 + (2)*3*x^4*G + (5)*1*x^6)/sqrt(G^7)
k=5: (G^4 + (1)*4*x^2*G^3 + (2)*6*x^4*G^2 + (5)*4*x^6*G + (14)*1*x^8)/sqrt(G^9)
and involve Catalan numbers and binomial coefficients.
MATRIX INVERSE.
The matrix inverse starts
     1;
    -1,   1;
    -1,  -1,   1;
     0,  -2,  -1,  1;
     2,  -1,  -3, -1,  1;
     6,   2,  -2, -4, -1,  1;
    13,  10,   2, -3, -5, -1,  1;
    18,  32,  14,  2, -4, -6, -1,  1;
   -12,  76,  56, 18,  2, -5, -7, -1,  1;
  -206, 108, 162, 86, 22,  2, -6, -8, -1, 1;
- R. J. Mathar, Apr 08 2013

Maple

A105632 := proc(n, k)
    (1-x-sqrt((1-x)^2-4*x^2/(1-x*y)))/2/x^2 ;
    coeftayl(%, x=0, n) ;
    coeftayl(%, y=0, k) ;
end proc: # R. J. Mathar, Apr 08 2013

Mathematica

T[n_, k_] := SeriesCoefficient[(1 - x - Sqrt[(1 - x)^2 - 4*x^2/(1 - x*y)])/(2*x^2), {x, 0, n}] // SeriesCoefficient[#, {y, 0, k}]&;
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 10 2023 *)

Prog

(PARI) {T(n, k)=local(A=1+x+x*y+x*O(x^n)+y*O(y^k)); for(i=1, n, A=1/(1-x*y)+x*A+x^2*A^2); polcoeff(polcoeff(A, n, x), k, y)}
(PARI) {T(n, k)=local(X=x+x*O(x^n), Y=y+y*O(y^k)); polcoeff(polcoeff( 2/(1-X+sqrt((1-X)^2-4*X^2/(1-X*Y)))/(1-X*Y), n, x), k, y)}

Crossrefs

Cf. A105633 (row sums), A001006 (column 0), A002426 (column 1).

Sequence in context: A217781 A339428 A204849 * A091491 A117418 A101494

Adjacent sequences: A105629 A105630 A105631 * A105633 A105634 A105635

Keyword

nonn,tabl

Author

Paul D. Hanna, Apr 17 2005

Status

approved