|
Search: id:A116424
|
|
|
| A116424 |
|
Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDUU's, 0<=k<=[(n-1)/2]. |
|
+0
2
|
|
| 1, 1, 2, 4, 1, 9, 5, 22, 19, 1, 57, 66, 9, 154, 221, 53, 1, 429, 729, 258, 14, 1223, 2391, 1131, 116, 1, 3550, 7829, 4652, 745, 20, 10455, 25638, 18357, 4115, 220, 1, 31160, 84033, 70404, 20598, 1790, 27, 93802, 275765, 264563, 96286, 12104, 379, 1, 284789
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
T(n,k) also gives the number of Dyck paths of semilength n with k UUDU's. Column 0 is sequence A105633.
|
|
REFERENCES
|
T. Mansour, Statistics on Dyck paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
|
|
FORMULA
|
T(n,k) = Sum((-1)^(i+k) * binomial(i,k) * binomial(n-i,i) * binomial(2*n-3*i, n - 2*i -1)/(n-i), i=k..[(n-1)/2]), n >=1. G.f. G = G(t,z) satisfies G = 1 + z^2(1-t)G + z(1-z+tz)G^2.
|
|
EXAMPLE
|
Triangle begins:
1;
1;
2;
4,1;
9,5;
22,19,1;
57,66,9;
154,221,53,1;
429,729,258,14;
1223,2391,1131,116,1;
3550,7829,4652,745,20;
...
T(4,1) = 5 because there exist five Dyck paths of semilength 4 with one occurrence of UDUU : UDUUUDDD, UDUUDUDD, UDUUDDUD, UUDUUDDD, UDUDUUDD.
|
|
MATHEMATICA
|
Series[((1 + (t - 1)z^2) - Sqrt[(1 + (t - 1)z^2)^2 - 4*z*(1 - z + z*t)])/(2* z*(1 - z + z*t)), {z, 0, 20}, {t, 0, 20}]
|
|
CROSSREFS
|
Adjacent sequences: A116421 A116422 A116423 this_sequence A116425 A116426 A116427
Sequence in context: A097607 A132893 A091958 this_sequence A135306 A102405 A114506
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006
|
|
|
Search completed in 0.002 seconds
|
