|
Search: id:A132894
|
|
|
| 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). |
|
+0
4
|
|
| 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; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
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)).
|
|
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)].
|
|
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 this_sequence A117917 A027295 A057332
Adjacent sequences: A132891 A132892 A132893 this_sequence A132895 A132896 A132897
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 07 2007
|
|
|
Search completed in 0.002 seconds
|
