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

1, 1, 2, 3, 6, 10, 19, 33, 61, 108, 197, 352, 638, 1145, 2069, 3721, 6714, 12087, 21794, 39254, 70755, 127469, 229725, 413908, 745889, 1343980, 2421850, 4363921, 7863641, 14169633, 25532994, 46008619, 82904974, 149389218, 269190547, 485064009, 874055885

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Form the graph with matrix A = [0,1,1; 1,0,0; 1,0,1] (P_3 with a loop at an extremity). Then A028495 counts closed walks of length n at the degree 3 vertex. - Paul Barry, Oct 02 2004

Equals INVERT transform of (1, 1, 0, 1, 0, 1, 0, 1, ...). - Gary W. Adamson, Apr 28 2009

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

a(n) is the number of ways White can force checkmate in exactly (n+1) moves, n>=0, ignoring the fifty-move and the triple repetition rules, in the following chess position: White Ka1, Ra8, Bc1, Nb8, pawns a6, a7, b2, c6, d2, f6 and h6; Black Kc8, pawns b3, c7, d3, f7 and h7. (After Noam D. Elkies, see link; diagram 5).

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

a(n) is the number of length n-1 binary words such that each maximal block of 1's has odd length. a(4) = 6 because we have: 000, 001, 010, 100, 101, 111. - Geoffrey Critzer, Nov 17 2012

a(n) is the number of compositions of n where increments can only appear at every second position, starting with the second and third part, see example. Also, a(n) is the number of compositions of n where there is no fall between every second pair of parts, starting with the first and second part; see example. - Joerg Arndt, May 21 2013

a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 0; 1, 0, 1; 0, 1, 0] or of the 3 X 3 matrix [1, 0, 1; 0, 0, 1; 1, 1, 0]. - R. J. Mathar, Feb 03 2014

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

a(n) is the number of compositions of n into parts from {1,2,4,6,8,10,...}. Example: a(4)= 6 because we have 4, 22, 211, 121, 112, and 1111. - Emeric Deutsch, Aug 17 2016

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=6. - Herbert Kociemba, Sep 15 2020

a(n-1) is the number of triangular dcc-polyominoes having area n (see Baril et al. at page 11). - Stefano Spezia, Oct 14 2023

a(n) is the number of permutations p of [n] with p(j)Alois P. Heinz, Mar 29 2024

Examples

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 19*x^6 + 33*x^7 + 61*x^8 + ...
From _Joerg Arndt_, May 21 2013: (Start)
There are a(6)=19 compositions of 6 where increments can only appear at every second position:
  01:  [ 1 1 1 1 1 1 ]
  02:  [ 1 1 1 1 2 ]
  03:  [ 1 1 2 1 1 ]
  04:  [ 1 1 2 2 ]
  05:  [ 1 1 3 1 ]
  06:  [ 1 1 4 ]
  07:  [ 2 1 1 1 1 ]
  08:  [ 2 1 2 1 ]
  09:  [ 2 1 3 ]
  10:  [ 2 2 1 1 ]
  11:  [ 2 2 2 ]
  12:  [ 3 1 1 1 ]
  13:  [ 3 1 2 ]
  14:  [ 3 2 1 ]
  15:  [ 3 3 ]
  16:  [ 4 1 1 ]
  17:  [ 4 2 ]
  18:  [ 5 1 ]
  19:  [ 6 ]
There are a(6)=19 compositions of 6 where there is no fall between every second pair of parts, starting with the first and second part:
  01:  [ 1 1 1 1 1 1 ]
  02:  [ 1 1 1 1 2 ]
  03:  [ 1 1 1 2 1 ]
  04:  [ 1 1 1 3 ]
  05:  [ 1 1 2 2 ]
  06:  [ 1 1 4 ]
  07:  [ 1 2 1 1 1 ]
  08:  [ 1 2 1 2 ]
  09:  [ 1 2 3 ]
  10:  [ 1 3 1 1 ]
  11:  [ 1 3 2 ]
  12:  [ 1 4 1 ]
  13:  [ 1 5 ]
  14:  [ 2 2 1 1 ]
  15:  [ 2 2 2 ]
  16:  [ 2 3 1 ]
  17:  [ 2 4 ]
  18:  [ 3 3 ]
  19:  [ 6 ]
(End)
19 = (1, 0, 1, 0, 1, 1) dot (1, 1, 2, 3, 6, 10) = (1 + 0 + 2 + 0 + 6 + 10). Cf. comment of Apr 28 2009. - _Gary W. Adamson_, Aug 10 2016
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• S. V. Ault and C. Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics (2014).
• Jean-Luc Baril, José L. Ramírez, and Fabio A. Velandia, Bijections between Directed-Column Convex Polyominoes and Restricted Compositions, September 29, 2023.
• Alexandru Chirvasitu, Tara Hudson, and Aparna Upadhyay, Recursive sequences attached to modular representations of finite groups, arXiv:2105.04732 [math.RT], 2021. See (1) p. 27.
• Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
• 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.
• Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, On a variant of Flory model, arXiv:2210.12411 [math.CO], 2022.
• Noam D. Elkies, New Directions in Enumerative Chess Problems, The Electronic Journal of Combinatorics, 11 (2), 2004-2005; arXiv:math/0508645 [math.CO], 2005. - _Johannes W. Meijer_, May 29 2010
• Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 14.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1056
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1057
• Mohammed L. Nadji, Moussa Ahmia, Daniel F. Checa, and José L. Ramírez, Arndt Compositions with Restricted Parts, Palindromes, and Colored Variants, J. Int. Seq. (2025) Vol. 28, Issue 3, Article 25.3.6. See pp. 9, 15.
• László Németh and Dragan Stevanović, Graph solution of system of recurrence equations, Research Gate, 2023. See Table 2 at p. 6.
• László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
• Index entries for linear recurrences with constant coefficients, signature (1,2,-1).

Crossrefs

Cf. A052534, A052547, A096976, A276053, A068911, A078038, A094790, A000045, A038754, A028495, A030436, A061551, A178381.

Cf. A006053, A052975, A060557, A094718.

Programs

Maple

spec := [S,{S=Sequence(Union(Prod(Sequence(Prod(Z,Z)),Z,Z),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
with(GraphTheory): P:=6: G:= PathGraph(P): A:=AdjacencyMatrix(G): nmax:=34; 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
a := (-1)^(3/7) - (-1)^(4/7):
b := (-1)^(5/7) - (-1)^(2/7):
c := (-1)^(1/7) - (-1)^(6/7):
f := n -> (a^n * (2 + a) + b^n * (2 + b) + c^n * (2 + c))/7:
seq(simplify(f(n)), n=0..36); # Peter Luschny, Sep 16 2020

Mathematica

LinearRecurrence[{1, 2, -1}, {1, 1, 2}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
CoefficientList[Series[(1-x^2)/(1-x-2x^2+x^3),{x,0,40}],x] (* Harvey P. Dale, Dec 23 2018 *)
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,6],{n,0,40}]//Round (* Herbert Kociemba, Sep 15 2020 *) (* Herbert Kociemba, Sep 14 2020 *)

PARI

{a(n) = if( n<0, n = -1-n; polcoeff( (1 - x^2) / (1 - 2*x - x^2 + x^3) + x * O(x^n), n), polcoeff( (1 - x^2) / (1 - x - 2*x^2 + x^3) + x * O(x^n), n))} /* Michael Somos, Apr 05 2012 */

PARI

a(n)=([0,1,0;0,0,1;-1,2,1]^n*[1;1;2])[1,1] \\ Charles R Greathouse IV, Aug 25 2016

Formula

Recurrence: {a(0)=1, a(1)=1, a(2)=2, a(n)-2*a(n+1)-a(n+2)+a(n+3)=0}.

a(n) = Sum_(1/7*(1+2*_alpha)*_alpha^(-1-n), _alpha=RootOf(_Z^3-2*_Z^2-_Z+1)).

a(n) = A094718(6, n). - N. J. A. Sloane, Jun 12 2004

a(n) = a(n-1) + Sum_{k=1..floor(n/2)} a(n-2*k). - Floor van Lamoen, Oct 29 2005

a(n) = 5*a(n-2) - 6*a(n-4) + a(n-6). - Floor van Lamoen, Nov 02 2005

a(n) = A006053(n+2) - A006053(n). - R. J. Mathar, Nov 16 2007

a(2*n) = A052975(n), a(2*n+1) = A060557(n). - Johannes W. Meijer, May 29 2010

G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x))))). - Michael Somos, Apr 05 2012

a(-1 - n) = A052534(n). - Michael Somos, Apr 05 2012

a(n) = (2^n/7)*Sum_{r=1..6} (1-(-1)^r)*cos(Pi*r/7)^n*(1+cos(Pi*r/7)). - Herbert Kociemba, Sep 15 2020

Extensions

More terms from James Sellers, Jun 05 2000