A033191 Binomial transform of [ 1, 0, 1, 1, 3, 6, 15, 36, 91, 231, 595, ... ], which is essentially binomial(Fibonacci(k) + 1, 2).

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, 58598, 206516, 732825, 2613834, 9358677, 33602822, 120902914, 435668420, 1571649221, 5674201118, 20497829133, 74079051906, 267803779710, 968355724724, 3502058316337, 12666676646162, 45818284122149

Offset: 0

Author

Simon P. Norton

Keywords

• nonn
• easy
• changed

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

Examples

			1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + 1430*x^8 + ...
		

Links

• 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).

Crossrefs

Cf. A033192.

Cf. A081567, A147748 and A178381.

Cf. A211216.

Programs

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 *)

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 */

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