|
| |
|
|
A132894
|
|
Number of (1,0) steps in all paths of length n with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e. in all length-n left factors of Motzkin paths).
|
|
3
| |
|
|
0, 1, 4, 15, 52, 175, 576, 1869, 6000, 19107, 60460, 190333, 596652, 1863745, 5804176, 18028755, 55873872, 172818243, 533589660, 1644921789, 5063762220, 15568666029, 47811348816, 146675181975, 449538774048, 1376564658525
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Number of peaks (i.e. UDs) in all paths of length n+1 with steps U=(1,1), D=(1,-1) and H=(1,0), starting at (0,0), staying weakly above the x-axis (i.e. in all length n+1 left factors of Motzkin paths). Example: a(2)=4 because in the 13 (=A005773(4)) length-3 left factors of Motzkin paths, namely HHH, HHU, H(UD), HUH, HUU, (UD)H, (UD)U, UHD, UHH, UHU, U(UD), UUH and UUU, we have altogether 4 peaks (shown between parentheses). a(n)=Sum(k*A107230(n,k),k=0..n). a(n)=Sum(k*A132893(n+1,k), k=0..floor((n+1)/2)).
This could be called the Motzkin transform of A077043 because the substitution x -> x*A001006(x) in the independent variable of the g.f. of A077043 yields the g.f. of this sequence here. [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 10 2008]
|
|
|
FORMULA
| a(n)=Sum(k*binom(n,k)*binom(n-k, floor((n-k)/2)), k=0..n). G.f.=z/[(1-3z)sqrt(1-2z-3z^2)].
a(n)=Sum(k*binom(n,k)*binom(2*k,k)*(-1)^(n-k), k=0..n). [From Wadim Zudilin (wzudilin(AT)gmail.com), Oct 11 2010]
|
|
|
EXAMPLE
| a(2)=4 because in the 5 (=A005773(3)) length-2 left factors of Motzkin paths, namely HH, HU, UD, UH and UU, we have altogether 4 H steps.
|
|
|
MAPLE
| a := proc (n) options operator, arrow: sum(k*binomial(n, k)*binomial(n-k, floor((1/2)*n-(1/2)*k)), k=0..n) end proc: seq(a(n), n=0..25);
|
|
|
CROSSREFS
| Cf. A005773, A107230, A132893.
Sequence in context: A117202 A137213 A027853 * A117917 A192431 A161125
Adjacent sequences: A132891 A132892 A132893 * A132895 A132896 A132897
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 07 2007
|
| |
|
|
