%I #85 Jun 15 2023 07:59:22
%S 1,1,2,3,6,10,20,34,68,116,232,396,792,1352,2704,4616,9232,15760,
%T 31520,53808,107616,183712,367424,627232,1254464,2141504,4283008,
%U 7311552,14623104,24963200,49926400,85229696,170459392,290992384,581984768,993510144,1987020288,3392055808
%N Expansion of g.f. (1 + x - 2*x^2 - x^3)/(1 - 4*x^2 + 2*x^4).
%C Also (starting 3, 6, ...) the number of zig-zag paths from top to bottom of a rectangle of width 7 whose color is not that of the top right corner.
%C From _Johannes W. Meijer_, May 29 2010: (Start)
%C The a(n) represent the number of possible chess games, ignoring the fifty-move and the triple repetition rules, after n moves by White in the following position: White Ka1, Nh1, pawns a2, b6, c2, d6, f2, g3 and h2; Black Ka8, Bc8, pawns a3, b7, c3, d7, f3, g4 and h3.
%C Counts all paths of length n, n>=0, starting at the initial node on the path graph P_7, see the Maple program. (End)
%C Range of row n of the circular Pascal array of order 8. - _Shaun V. Ault_, Jun 05 2014.
%C In general, a(n,m) = (2^n/(m+1))*Sum_{r=1..m} (1-(-1)^r)*cos(Pi*r/(m+1))^n*(1+cos(Pi*r/(m+1))) gives the number of paths of length n starting at the initial node on the path graph P_m. Here we have m=7. - _Herbert Kociemba_, Sep 17 2020
%H Stefano Spezia, <a href="/A030436/b030436.txt">Table of n, a(n) for n = 0..3600</a>
%H Shaun V. Ault and Charles Kicey, <a href="http://arxiv.org/abs/1407.2197">Counting paths in corridors using circular Pascal arrays</a>, arXiv:1407.2197 [math.CO], 2014.
%H Shaun V. Ault and Charles Kicey, <a href="http://dx.doi.org/10.1016/j.disc.2014.05.020">Counting paths in corridors using circular Pascal arrays</a>, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
%H Johann Cigler, <a href="http://arxiv.org/abs/1501.04750">Some remarks and conjectures related to lattice paths in strips along the x-axis</a>, arXiv:1501.04750 [math.CO], 2015-2016.
%H Johann Cigler, <a href="https://arxiv.org/abs/2212.02118">Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials</a>, arXiv:2212.02118 [math.NT], 2022.
%H Nachum Dershowitz, <a href="https://arxiv.org/abs/2006.06516">Between Broadway and the Hudson</a>, arXiv:2006.06516 [math.CO], 2020.
%H Joseph Myers, <a href="http://www.polyomino.org.uk/publications/2008/bmo1-2009-q1.pdf">BMO 2008-2009 Round 1 Problem 1 - Generalisation</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,4,0,-2).
%F a(0)=a(1)=1, a(2)=2, a(3)=3, a(n)=4*a(n-2)-2*a(n-4). - _Harvey P. Dale_, May 11 2011
%F a(n) = (2+sqrt(2+sqrt(2)))/8*(sqrt(2+sqrt(2)))^n + (2-sqrt(2+sqrt(2)))/8*(-sqrt(2+sqrt(2)))^n + (2+sqrt(2-sqrt(2)))/8*(sqrt(2-sqrt(2)))^n + (2-sqrt(2-sqrt(2)))/8*(-sqrt(2-sqrt(2)))^n. - _Sergei N. Gladkovskii_, Aug 23 2012
%F a(n) = A030435(n)/2. a(2*n) = A006012(n). a(2*n + 1) = A007052(n). - _Michael Somos_, Mar 06 2003
%F a(n) = (2^n/8)*Sum_{r=1..7} (1-(-1)^r)cos(Pi*r/8)^n*(1+cos(Pi*r/8)). - _Herbert Kociemba_, Sep 17 2020
%F E.g.f.: (2*cosh(r*x) + 2*cosh(s*x) + r*sinh(r*x) + s*sinh(s*x))/4, where r = sqrt(2 - sqrt(2)) and s = sqrt(2 + sqrt(2)). - _Stefano Spezia_, Jun 14 2023
%e G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 20*x^6 + 34*x^7 + 68*x^8 + ...
%p with(GraphTheory): P:=7: G:=PathGraph(P): A:= AdjacencyMatrix(G): nmax:=31; for n from 0 to nmax do B(n):=A^n; a(n):=add(B(n)[1,k],k=1..P); od: seq(a(n),n=0..nmax); # _Johannes W. Meijer_, May 29 2010
%p X := j -> (-1)^(j/8) - (-1)^(1-j/8):
%p a := k -> add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7])/8:
%p seq(simplify(a(n)), n=0..30); # _Peter Luschny_, Sep 17 2020
%t CoefficientList[Series[(1+x-2x^2-x^3)/(1-4x^2+2x^4),{x,0,40}],x] (* or *) LinearRecurrence[{0,4,0,-2},{1,1,2,3},41] (* _Harvey P. Dale_, May 11 2011 *)
%t a[n_,m_]:=2^(n+1)/(m+1) Module[{x=(Pi r)/(m+1)},Sum[Cos[x]^n (1+Cos[x]),{r,1,m,2}]]
%t Table[a[n,7],{n,0,40}]//Round (* _Herbert Kociemba_, Sep 17 2020 *)
%o (PARI) Vec((1+x-2*x^2-x^3)/(1-4*x^2+2*x^4)+O(x^99)) \\ _Charles R Greathouse IV_, Sep 23 2012
%o (PARI) {a(n) = if( n<0, 0, polsym( x^4 - 4*x^2 + 2, n + n%2)[n + n%2 + 1] / (4 * (n%2 + 1)))}; /* _Michael Somos_, Feb 08 2015 */
%Y Cf. A006012, A007052, A030435.
%Y a(n) = A094718(7, n).
%Y Cf. A024175, A094803, A000045, A038754, A028495, A061551 and A178381.
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_, Dec 11 1999
%E Comment and link added and typo in cross-reference corrected by _Joseph Myers_, Dec 24 2008, May 30 2010