OFFSET
0,3
COMMENTS
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 10 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 1. - Herbert Kociemba, Jun 14 2004
The sequence 1,2,5,14,... has g.f. 1/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x)))) = (1-6x+10x^2-4x^3)/(1-8x+21x^2-20x^3+5x^4), and is the second binomial transform A001519 aerated. - Paul Barry, Dec 17 2009
Counts all paths of length (2*n), n>=0, starting and ending at the initial node on the path graph P_9, see the Maple program. - Johannes W. Meijer, May 29 2010
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..1793
Paul Drube, Raised k-Dyck paths, arXiv:2206.01194 [math.CO], 2022. See Appendix pp. 14-15.
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=8, pages 10-11). [Bruno Berselli, May 12 2012]
Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See p. 9.
Index entries for linear recurrences with constant coefficients, signature (8,-21,20,-5).
FORMULA
G.f.: (1-7x+15x^2-10x^3+x^4)/(1-8x+21x^2-20x^3+5x^4). - Ralf Stephan, May 13 2003
From Herbert Kociemba, Jun 14 2004: (Start)
a(n) = (1/5)*Sum_{r=1..9} sin(r*Pi/10)^2*(2*cos(r*Pi/10))^(2n), n >= 1;
a(n) = 8*a(n-1) - 21*a(n-2) + 20*a(n-3) - 5*a(n-4), n >= 5. (End)
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x )))))))). - Michael Somos, May 12 2012
EXAMPLE
1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + 1430*x^8 + ...
MAPLE
with(GraphTheory): G:=PathGraph(9): A:= AdjacencyMatrix(G): nmax:=24; n2:=nmax*2: for n from 0 to n2 do B(n):=A^n; a(n):=B(n)[1, 1]; od: seq(a(2*n), n=0..nmax); # Johannes W. Meijer, May 29 2010
MATHEMATICA
CoefficientList[Series[(1-7x+15x^2-10x^3+x^4)/(1-8x+21x^2-20x^3+5x^4), {x, 0, 30}], x] (* or *) Join[{1}, LinearRecurrence[{8, -21, 20, -5}, {1, 2, 5, 14}, 30]] (* Harvey P. Dale, Apr 26 2011 *)
PROG
(PARI) {a(n) = local(A); A = 1; for( i=1, 8, A = 1 / (1 - x*A)); polcoeff( A + x * O(x^n), n)} /* Michael Somos, May 12 2012 */
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Simon P. Norton
STATUS
approved
