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

%I #41 Feb 11 2024 12:44:08

%S 1,1,2,5,14,42,132,429,1430,4861,16778,58598,206516,732825,2613834,

%T 9358677,33602822,120902914,435668420,1571649221,5674201118,

%U 20497829133,74079051906,267803779710,968355724724,3502058316337,12666676646162,45818284122149

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

%C 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

%C 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

%C 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

%H Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I</a>, arXiv:1201.6243v1 [math.CO], 2012 (Corollary 3, case k=8, pages 10-11). [_Bruno Berselli_, May 12 2012]

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (8,-21,20,-5).

%F G.f.: (1-7x+15x^2-10x^3+x^4)/(1-8x+21x^2-20x^3+5x^4). - _Ralf Stephan_, May 13 2003

%F From _Herbert Kociemba_, Jun 14 2004: (Start)

%F a(n) = (1/5)*Sum_{r=1..9} sin(r*Pi/10)^2*(2*cos(r*Pi/10))^(2n), n >= 1;

%F a(n) = 8*a(n-1) - 21*a(n-2) + 20*a(n-3) - 5*a(n-4), n >= 5. (End)

%F G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x )))))))). - _Michael Somos_, May 12 2012

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

%p 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

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

%o (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 */

%Y Cf. A033192.

%Y Cf. A081567, A147748 and A178381.

%Y Cf. A211216.

%K nonn,easy

%O 0,3

%A Simon P. Norton