|
|
A028495
|
|
Expansion of (1-x^2)/(1-x-2*x^2+x^3).
|
|
26
|
|
|
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
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
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
|
|
LINKS
|
|
|
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)).
G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x))))). - 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
|
|
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 + ...
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
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:
|
|
MATHEMATICA
|
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}]]
|
|
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 */
|
|
CROSSREFS
|
Cf. A052534, A052547, A096976, A276053, A068911, A078038, A094790, A000045, A038754, A028495, A030436, A061551, A178381.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|