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

%I #131 Mar 29 2024 19:06:57

%S 1,1,2,3,6,10,19,33,61,108,197,352,638,1145,2069,3721,6714,12087,

%T 21794,39254,70755,127469,229725,413908,745889,1343980,2421850,

%U 4363921,7863641,14169633,25532994,46008619,82904974,149389218,269190547,485064009,874055885

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

%C 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

%C Equals INVERT transform of (1, 1, 0, 1, 0, 1, 0, 1, ...). - _Gary W. Adamson_, Apr 28 2009

%C From _Johannes W. Meijer_, May 29 2010: (Start)

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

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

%C (End)

%C 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

%C 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

%C 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

%C Range of row n of the circular Pascal array of order 7. - _Shaun V. Ault_, Jun 05 2014

%C 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

%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=6. - _Herbert Kociemba_, Sep 15 2020

%C 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

%C a(n) is the number of permutations p of [n] with p(j)<p(j+2) and p(j)<p(j+5). a(6) = 19: 123456, 123465, 123546, 124356, 124365, 125364, 132456, 132465, 132546, 142536, 213456, 213465, 213546, 214356, 214365, 215364, 314256, 314265, 315264. - _Alois P. Heinz_, Mar 29 2024

%H Vincenzo Librandi, <a href="/A028495/b028495.txt">Table of n, a(n) for n = 0..1000</a>

%H S. V. Ault and C. 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 (2014).

%H Jean-Luc Baril, José L. Ramírez, and Fabio A. Velandia, <a href="http://jl.baril.u-bourgogne.fr/hexbij.pdf">Bijections between Directed-Column Convex Polyominoes and Restricted Compositions</a>, September 29, 2023.

%H Alexandru Chirvasitu, Tara Hudson, and Aparna Upadhyay, <a href="https://arxiv.org/abs/2105.04732">Recursive sequences attached to modular representations of finite groups</a>, arXiv:2105.04732 [math.RT], 2021. See (1) p. 27.

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

%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 Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, <a href="https://arxiv.org/abs/2210.12411">On a variant of Flory model</a>, arXiv:2210.12411 [math.CO], 2022.

%H Noam D. Elkies, <a href="http://arxiv.org/abs/math/0508645">New Directions in Enumerative Chess Problems</a>, The Electronic Journal of Combinatorics, 11 (2), 2004-2005; arXiv:math/0508645 [math.CO], 2005. - _Johannes W. Meijer_, May 29 2010

%H Jia Huang, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Huang/huang8.html">Partially Palindromic Compositions</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 14.

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1056">Encyclopedia of Combinatorial Structures 1056</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1057">Encyclopedia of Combinatorial Structures 1057</a>

%H László Németh and Dragan Stevanović, <a href="https://www.researchgate.net/publication/370765824_Graph_solution_of_system_of_recurrence_equations">Graph solution of system of recurrence equations</a>, Research Gate, 2023. See Table 2 at p. 6.

%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1).

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

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

%F a(n) = A094718(6, n). - _N. J. A. Sloane_, Jun 12 2004

%F a(n) = a(n-1) + Sum_{k=1..floor(n/2)} a(n-2*k). - _Floor van Lamoen_, Oct 29 2005

%F a(n) = 5*a(n-2) - 6*a(n-4) + a(n-6). - _Floor van Lamoen_, Nov 02 2005

%F a(n) = A006053(n+2) - A006053(n). - _R. J. Mathar_, Nov 16 2007

%F a(2*n) = A052975(n), a(2*n+1) = A060557(n). - _Johannes W. Meijer_, May 29 2010

%F G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x))))). - _Michael Somos_, Apr 05 2012

%F a(-1 - n) = A052534(n). - _Michael Somos_, Apr 05 2012

%F 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

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

%e From _Joerg Arndt_, May 21 2013: (Start)

%e There are a(6)=19 compositions of 6 where increments can only appear at every second position:

%e 01: [ 1 1 1 1 1 1 ]

%e 02: [ 1 1 1 1 2 ]

%e 03: [ 1 1 2 1 1 ]

%e 04: [ 1 1 2 2 ]

%e 05: [ 1 1 3 1 ]

%e 06: [ 1 1 4 ]

%e 07: [ 2 1 1 1 1 ]

%e 08: [ 2 1 2 1 ]

%e 09: [ 2 1 3 ]

%e 10: [ 2 2 1 1 ]

%e 11: [ 2 2 2 ]

%e 12: [ 3 1 1 1 ]

%e 13: [ 3 1 2 ]

%e 14: [ 3 2 1 ]

%e 15: [ 3 3 ]

%e 16: [ 4 1 1 ]

%e 17: [ 4 2 ]

%e 18: [ 5 1 ]

%e 19: [ 6 ]

%e 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:

%e 01: [ 1 1 1 1 1 1 ]

%e 02: [ 1 1 1 1 2 ]

%e 03: [ 1 1 1 2 1 ]

%e 04: [ 1 1 1 3 ]

%e 05: [ 1 1 2 2 ]

%e 06: [ 1 1 4 ]

%e 07: [ 1 2 1 1 1 ]

%e 08: [ 1 2 1 2 ]

%e 09: [ 1 2 3 ]

%e 10: [ 1 3 1 1 ]

%e 11: [ 1 3 2 ]

%e 12: [ 1 4 1 ]

%e 13: [ 1 5 ]

%e 14: [ 2 2 1 1 ]

%e 15: [ 2 2 2 ]

%e 16: [ 2 3 1 ]

%e 17: [ 2 4 ]

%e 18: [ 3 3 ]

%e 19: [ 6 ]

%e (End)

%e 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

%p spec := [S,{S=Sequence(Union(Prod(Sequence(Prod(Z,Z)),Z,Z),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);

%p 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

%p a := (-1)^(3/7) - (-1)^(4/7):

%p b := (-1)^(5/7) - (-1)^(2/7):

%p c := (-1)^(1/7) - (-1)^(6/7):

%p f := n -> (a^n * (2 + a) + b^n * (2 + b) + c^n * (2 + c))/7:

%p seq(simplify(f(n)), n=0..36); # _Peter Luschny_, Sep 16 2020

%t LinearRecurrence[{1, 2, -1}, {1, 1, 2}, 60] (* _Vladimir Joseph Stephan Orlovsky_, Feb 11 2012 *)

%t CoefficientList[Series[(1-x^2)/(1-x-2x^2+x^3),{x,0,40}],x] (* _Harvey P. Dale_, Dec 23 2018 *)

%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,6],{n,0,40}]//Round (* _Herbert Kociemba_, Sep 15 2020 *) (* _Herbert Kociemba_, Sep 14 2020 *)

%o (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 */

%o (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

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

%Y Cf. A006053, A052975, A060557, A094718.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _James A. Sellers_, Jun 05 2000