login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A028495 Expansion of (1-x^2)/(1-x-2*x^2+x^3). 23
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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)

The a(n) represent 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

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

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1056

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1057

Noam D. Elkies, New Directions in Enumerative Chess Problems., The Electronic Journal of Combinatorics, 11 (2), 2004-2005. - Johannes W. Meijer, May 29 2010

Index entries for linear recurrences with constant coefficients, signature (1, 2, -1).

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(a(n-2k), k=1..floor(n/2)). - 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

EXAMPLE

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

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

MATHEMATICA

LinearRecurrence[{1, 2, -1}, {1, 1, 2}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)

PROG

(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

CROSSREFS

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

Sequence in context: A014595 A079959 A282583 * A136752 A093126 A003237

Adjacent sequences:  A028492 A028493 A028494 * A028496 A028497 A028498

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from James A. Sellers, Jun 05 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 00:25 EDT 2017. Contains 283983 sequences.