|
| |
|
|
A091964
|
|
Number of left factors of peakless Motzkin paths of length n (i.e. number of paths from (0,0) to the line x=n, consisting of steps u=(1,1), h=(1,0), d=(1,1), that never go below the x-axis and a u step is never followed by a d step).
|
|
3
| |
|
|
1, 2, 4, 9, 21, 50, 121, 296, 730, 1812, 4521, 11328, 28485, 71844, 181674, 460443, 1169283, 2974574, 7578937, 19337489, 49401526, 126350742, 323495259, 829033334, 2126454271, 5458711430, 14023219126, 36049991901, 92734505565
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| a(n) is the number of peakless Motzkin paths of length n in which the (1,0)-steps at level 0 come in 2 colors. Example: a(4)=21 because, denoting u=(1,1), h=(1,0), and d=(1,-1), we have 2^4 = 16 paths of shape hhhh, 2 paths of shape huhd, 2 paths of shape uhdh, and 1 path of shape uhhd. [Emeric Deutsch, May 3 2011]
Equals diagonal sums of triangle A124428. - Paul D. Hanna (pauldhanna(AT)juno.com), Oct 31 2006
|
|
|
REFERENCES
| Ivo L. Hofacker, Christian M. Reidys, and Peter F. Stadler. Symmetric circular matchings and RNA folding. Discr. Math., 312:100-112, 2012. (doi:10.1016/j.disc.2011.06.004). See Prop. 5, C_2^{1}(z).
A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.
|
|
|
FORMULA
| G.f. = 2/[1-3*z+z^2+sqrt(1-2*z-z^2-2*z^3+z^4)].
a(n) = Sum_{k=0..n} C(n-[k/2], [(k+1)/2]) * C(n-[(k+1)/2], [k/2]). - Paul D. Hanna (pauldhanna(AT)juno.com), Mar 24 2005
a(n) = Sum_{k=0..n} C([(n+k)/2],k)*C([(n+k+1)/2],k)). - Paul D. Hanna (pauldhanna(AT)juno.com), Oct 31 2006
G.f.: 1/(1-x-x/(1-x^2/(1-x/(1-x^2/(1-x/(1-x^2/(1-... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Jun 30 2009]
|
|
|
EXAMPLE
| a(2)=4 because we have hh, hu, uh and uu.
|
|
|
PROG
| (PARI) a(n)=sum(k=0, n, binomial(n-k\2, (k+1)\2)*binomial(n-(k+1)\2, k\2)) (Hanna)
(PARI) a(n)=sum(k=0, n, binomial((n+k)\2, k)*binomial((n+k+1)\2, k)) - Paul D. Hanna (pauldhanna(AT)juno.com), Oct 31 2006
|
|
|
CROSSREFS
| Cf. A004148, A104559, A124428.
Sequence in context: A024537 A171842 A027826 * A092423 A199410 A091600
Adjacent sequences: A091961 A091962 A091963 * A091965 A091966 A091967
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 13 2004
|
| |
|
|
