|
|
A025566
|
|
a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0, s(1) = 1, |s(i) - s(i-1)| <= 1 for i >= 2. Also a(n) = sum of numbers in row n+1 of the array T defined in A026105. Also a(n) = T(n,n), where T is the array defined in A025564.
|
|
9
|
|
|
1, 1, 1, 3, 8, 22, 61, 171, 483, 1373, 3923, 11257, 32418, 93644, 271219, 787333, 2290200, 6673662, 19478091, 56930961, 166613280, 488176938, 1431878079, 4203938697, 12353600427, 36331804089, 106932444885, 314946659951, 928213563878
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
a(n+1) is the number of Motzkin (2n)-paths whose last weak valley occurs immediately after step n. A weak valley in a Motzkin path (A001006) is an interior vertex whose following step has nonnegative slope and whose preceding step has nonpositive slope. For example, the weak valleys in the Motzkin path F.UF.FD.UD occur after the first, third and fifth steps as indicated by the dots (U=upstep of slope 1, D=downstep of slope -1, F=flatstep of slope 0) and, with n=2, a(3)=3 counts FFUD, UDUD, UFFD. - David Callan, Jun 07 2006
Starting with offset 2: (1, 3, 8, 22, 61, 171, 483, ...), = row sums of triangle A136537. - Gary W. Adamson, Jan 04 2008
|
|
LINKS
|
|
|
FORMULA
|
G.f.: x + 2*x*(x-1)/(1-3x-sqrt(1-2x-3x^2)); for n > 1, first differences of the "directed animals" sequence A005773: a(n) = A005773(n) - A005773(n-1). - Emeric Deutsch, Aug 16 2002
Starting (1, 3, 8, 22, 61, 171, ...) gives the inverse binomial transform of A001791 starting (1, 4, 15, 56, 210, 792, ...). - Gary W. Adamson, Sep 01 2007
D-finite with recurrence n*a(n) +(-3*n+2)*a(n-1) +(-n+2)*a(n-2) +3*(n-4)*a(n-3)=0. - R. J. Mathar, Sep 15 2020
|
|
MAPLE
|
seq( sum('binomial(i-2, k)*binomial(i-k, k)', 'k'=0..floor(i/2)), i=0..30 ); # Detlef Pauly (dettodet(AT)yahoo.de), Nov 09 2001
|
|
MATHEMATICA
|
CoefficientList[Series[x+(2x(x-1))/(1-3x-Sqrt[1-2x-3x^2]), {x, 0, 30}], x] (* Harvey P. Dale, Jun 12 2016 *)
|
|
PROG
|
(GAP) List([0..30], i->Sum([0..Int(i/2)], k->Binomial(i-2, k)*Binomial(i-k, k))); # Muniru A Asiru, Mar 09 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|