|
|
A212368
|
|
Number of Dyck n-paths all of whose ascents and descents have lengths equal to 1 (mod 9).
|
|
2
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 57, 73, 99, 142, 211, 317, 473, 694, 997, 1402, 1937, 2648, 3614, 4967, 6917, 9782, 14023, 20284, 29438, 42647, 61457, 87963, 125093, 177074, 250157, 353692, 501658, 714768, 1023296, 1470843
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,11
|
|
LINKS
|
|
|
FORMULA
|
G.f. satisfies: A(x) = 1+A(x)*(x-x^9*(1-A(x))).
a(n) = a(n-1) + Sum_{k=1..n-9} a(k)*a(n-9-k) if n>0; a(0) = 1.
|
|
EXAMPLE
|
a(0) = 1: the empty path.
a(1) = 1: UD.
a(10) = 2: UDUDUDUDUDUDUDUDUDUD, UUUUUUUUUUDDDDDDDDDD.
a(11) = 4: UDUDUDUDUDUDUDUDUDUDUD, UDUUUUUUUUUUDDDDDDDDDD, UUUUUUUUUUDDDDDDDDDDUD, UUUUUUUUUUDUDDDDDDDDDD.
|
|
MAPLE
|
a:= proc(n) option remember;
`if`(n=0, 1, a(n-1) +add(a(k)*a(n-9-k), k=1..n-9))
end:
seq(a(n), n=0..60);
# second Maple program:
a:= n-> coeff(series(RootOf(A=1+A*(x-x^9*(1-A)), A), x, n+1), x, n):
seq(a(n), n=0..60);
|
|
MATHEMATICA
|
With[{k = 9}, CoefficientList[Series[(1 - x + x^k - Sqrt[(1 - x + x^k)^2 - 4*x^k]) / (2*x^k), {x, 0, 40}], x]] (* Vaclav Kotesovec, Sep 02 2014 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|