login
A135308
Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k DUUU's.
1
1, 1, 2, 5, 13, 1, 35, 7, 96, 36, 267, 159, 3, 750, 645, 35, 2123, 2475, 264, 6046, 9136, 1602, 12, 17303, 32773, 8515, 195, 49721, 115017, 41349, 1925, 143365, 396730, 188010, 14740, 55, 414584, 1349440, 813072, 96200, 1144, 1201917, 4537368
OFFSET
0,3
COMMENTS
Row n has floor((n+2)/3) terms (n>=1). Row sums yield the Catalan numbers (A000108). Column 0 yields A005773. - Emeric Deutsch, Dec 13 2007
LINKS
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
FORMULA
T(n,k) = (1/n)*C(n,k)*Sum[(-1)^(j-k+1)*3^(n-j)*C(n-k,j-k)*C(2j-2-3k,j-1), j=3k+1..n) (n>=1). G.f.: F=F(t,z) satisfies tzF^3 + [3(1-t)z-1]F^2 - [3(1-t)z-1]F + (1-t)z = 0. - Emeric Deutsch, Dec 13 2007
EXAMPLE
Triangle begins:
1
1
2
5
13 1
35 7
96 36
267 159 3
...
T(5,1)=7 because we have UDUUUUDDDD, UDUUUDUDD, UDUUUDDUDD, UDUUUDDDUD, UDUDUUUDDD, UUDUUUDDDD and UUDDUUUDDD.
MAPLE
T:=proc(n, k) options operator, arrow: binomial(n, k)*(sum((-1)^(j-k+1)*3^(n-j)*binomial(n-k, j-k)*binomial(2*j-2-3*k, j-1), j=3*k+1..n))/n end proc: 1; for n to 15 do seq(T(n, k), k=0..floor((n-1)*1/3)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 13 2007
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
`if`(x=0, 1, expand(b(x-1, y+1, [1, 3, 4, 1][t])
* `if`(t=4, z, 1) +b(x-1, y-1, [2, 2, 2, 2][t]))))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..20); # Alois P. Heinz, Jun 10 2014
MATHEMATICA
T[n_, k_] := (1/n)*Binomial[n, k]*Sum[(-1)^(j-k+1)*3^(n-j)*Binomial[n-k, j-k]*Binomial[2j-2-3k, j-1], {j, 3k+1, n}]; T[0, 0] = 1; Table[T[n, k], {n, 0, 15}, {k, 0, If[n == 0, 0, Quotient[n-1, 3]]}] // Flatten (* Jean-François Alcover, Nov 27 2014, after Emeric Deutsch *)
CROSSREFS
Sequence in context: A137918 A372875 A114502 * A114492 A135305 A114463
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Dec 07 2007
EXTENSIONS
Edited and extended by Emeric Deutsch, Dec 13 2007
STATUS
approved