|
|
A080938
|
|
Number of Catalan paths (nonnegative, starting and ending at 0, step +-1) of 2*n steps with all values less than or equal to 7.
|
|
9
|
|
|
1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, 57686, 201158, 704420, 2473785, 8704089, 30664890, 108126325, 381478030, 1346396146, 4753200932, 16783118309, 59266297613, 209302921830, 739203970773, 2610763825782, 9221050139566, 32568630376132
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) also gives the upper left entry of the n-th power of the 4 X 4 tridiagonal matrix M_4, given in A332602: M_4 = Matrix([1,1,0,0], [1,2,1,0], [0,1,2,1], [0,0,1,2]): a(n) = (M_4)^n[1,1]. Proof from the formula for (M_4)^n, given in a comment in A094256, derived from the Cayley-Hamilton theorem, which leads to the recurrence. The formula for a(n) in terms of A094256 is given below.
(End)
|
|
LINKS
|
|
|
FORMULA
|
G.f.: -(2*x - 1)*(2*x^2 - 4*x + 1) / ( (x - 1)*(x^3 - 9*x^2 + 6*x - 1) ). - Ralf Stephan, May 13 2003
a(n) = 7*a(n-1) - 15*a(n-2) + 10*a(n-3) - a(n-4). - Herbert Kociemba, Jun 13 2004
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))))). - Michael Somos, May 12 2012
a(n) = 5*b(n-2) - 21*b(n-3) + 19*b(n-4) - 2*b(n-5), for n >= 0, with b(n) = A094256(n), for n >= -5. See a comment in A094256 for this offset, and the above comment. - Wolfdieter Lang, Mar 28 2020
|
|
EXAMPLE
|
1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...
|
|
MATHEMATICA
|
CoefficientList[Series[(1 - 2 x) (2 x^2 - 4 x + 1) / ((x - 1) (x^3 - 9 x^2 + 6 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 30 2018 *)
|
|
PROG
|
(PARI) {a(n) = local(A); A = 1; for( i=1, 7, A = 1 / (1 - x*A)); polcoeff( A + x * O(x^n), n)} /* Michael Somos, May 12 2012 */
(Magma) I:=[1, 1, 2, 5]; [n le 4 select I[n] else 7*Self(n-1)-15*Self(n-2)+10*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Nov 30 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|