A030436 Expansion of g.f. (1 + x - 2*x^2 - x^3)/(1 - 4*x^2 + 2*x^4).

1, 1, 2, 3, 6, 10, 20, 34, 68, 116, 232, 396, 792, 1352, 2704, 4616, 9232, 15760, 31520, 53808, 107616, 183712, 367424, 627232, 1254464, 2141504, 4283008, 7311552, 14623104, 24963200, 49926400, 85229696, 170459392, 290992384, 581984768, 993510144, 1987020288, 3392055808

Offset: 0

Author

N. J. A. Sloane, Dec 11 1999

Keywords

• nonn
• easy

Comments

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.

From Johannes W. Meijer, May 29 2010: (Start)

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.

Counts all paths of length n, n>=0, starting at the initial node on the path graph P_7, see the Maple program. (End)

Range of row n of the circular Pascal array of order 8. - Shaun V. Ault, Jun 05 2014.

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

Examples

			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 + ...
		

Links

• Stefano Spezia, Table of n, a(n) for n = 0..3600
• Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
• Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
• Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
• Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
• Nachum Dershowitz, Between Broadway and the Hudson, arXiv:2006.06516 [math.CO], 2020.
• Joseph Myers, BMO 2008-2009 Round 1 Problem 1 - Generalisation
• Index entries for linear recurrences with constant coefficients, signature (0,4,0,-2).

Crossrefs

Cf. A006012, A007052, A030435.

a(n) = A094718(7, n).

Cf. A024175, A094803, A000045, A038754, A028495, A061551 and A178381.

Programs

Maple

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
X := j -> (-1)^(j/8) - (-1)^(1-j/8):
a := k -> add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7])/8:
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 17 2020

Mathematica

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 *)
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}]]
Table[a[n,7],{n,0,40}]//Round (* Herbert Kociemba, Sep 17 2020 *)

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

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

Formula

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

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

a(n) = A030435(n)/2. a(2*n) = A006012(n). a(2*n + 1) = A007052(n). - Michael Somos, Mar 06 2003

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

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

Extensions

Comment and link added and typo in cross-reference corrected by Joseph Myers, Dec 24 2008, May 30 2010