|
| |
|
|
A135307
|
|
Number of Dyck paths of semilength n that do not contain the string UDDU.
|
|
2
| |
|
|
1, 1, 2, 4, 9, 23, 63, 178, 514, 1515, 4545, 13827, 42540, 132124, 413741, 1304891, 4141198, 13214815, 42375461, 136478383, 441285890, 1431925180, 4661485203, 15219836738, 49827678840, 163535624722, 537962562453, 1773437280323
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Top left terms of powers of the production matrix M generates sequence A102403. - Gary W. Adamson, Jan 30 2012
|
|
|
REFERENCES
| A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
|
|
|
FORMULA
| The Sapounakis et al. reference gives an explicit formula.
a(n) is the sum of top row terms in M^(n-1), where M = the following infinite square production matrix:
1, 1, 0, 0, 0, 0,...
0, 1, 1, 0, 0, 0,...
1, 0, 1, 1, 0, 0,...
1, 1, 0, 1, 1, 0,...
1, 1, 1, 0, 1, 1,...
- Gary W. Adamson, Jan 30 2012
|
|
|
EXAMPLE
| a(6) = 63 since the top row of M^5 = (17, 17, 13, 10, 5, 1), sum of terms = 63.
|
|
|
MAPLE
| A135306 := proc(n, k) if n =0 then 1 ; else add((-1)^(j-k)*binomial(n-k, j-k)*binomial(2*n-3*j, n-j+1), j=k..floor((n-1)/2)) ; %*binomial(n, k)/n ; fi ; end: A135307 := proc(n) A135306(n, 0) ; end: for n from 0 to 30 do printf("%a, ", A135307(n)) ; od: - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Dec 08 2007
|
|
|
CROSSREFS
| Leading column of A135306.
Cf. A102403
Sequence in context: A127384 A058585 A001573 * A000083 A092668 A164039
Adjacent sequences: A135304 A135305 A135306 * A135308 A135309 A135310
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Dec 07 2007
|
|
|
EXTENSIONS
| More terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Dec 08 2007
|
| |
|
|
