login
Expansion of (1-x)*(1+x)/(1-2*x-x^2+x^3).
11

%I #91 Dec 15 2023 19:17:29

%S 1,2,4,9,20,45,101,227,510,1146,2575,5786,13001,29213,65641,147494,

%T 331416,744685,1673292,3759853,8448313,18983187,42654834,95844542,

%U 215360731,483911170,1087338529,2443227497,5489882353,12335653674

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

%C Pairwise sums of A006356. Cf. A033303, A077850. - _Ralf Stephan_, Jul 06 2003

%C Number of (3412, P)-avoiding involutions in S_{n+1}, where P={1342, 1423, 2314, 3142, 2431, 4132, 3241, 4213, 21543, 32154, 43215, 15432, 53241, 52431, 42315, 15342, 54321}. - _Ralf Stephan_, Jul 06 2003

%C Number of 31- and 22-avoiding words of length n on alphabet {1,2,3} which do not end in 3 (e.g., at n=3, we have 111, 112, 121, 132, 211, 212, 232, 321 and 332). See A028859, A001519. - _Jon Perry_, Aug 04 2003

%C Form the graph with matrix A=[1, 1, 1; 1, 0, 0; 1, 0, 1]. Then the sequence 1,1,2,4,... with g.f. (1-x-x^2)/(1-2x-x^2+x^3) counts closed walks of length n at the degree 3 vertex. - _Paul Barry_, Oct 02 2004

%C a(n) is the number of Motzkin (n+1)-sequences whose flatsteps all occur at level <=1 and whose height is <=2. For example, a(5)=45 counts all 51 Motzkin 6-paths except FUUFDD, UFUFDD, UUFDDF, UUFDFD, UUFFDD, UUUDDD (the first five violate the flatstep restriction and the last violates the height restriction). - _David Callan_, Dec 09 2004

%C From _Paul Barry_, Nov 03 2010: (Start)

%C The g.f. of 1,1,2,4,9,... can be expressed as 1/(1-x/(1-x/(1-x^2)) and as 1/(1-x-x^2/(1-x-x^2)).

%C The second expression shows the link to the Motzkin numbers. (End)

%C From _Emeric Deutsch_, Oct 31 2010: (Start)

%C a(n) is the number of compositions of n into odd summands when we have two kinds of 1's. Proof: the g.f. of the set S={1,1',3,5,7,...} is g=2x+x^3/(1-x^2) and the g.f. of finite sequences of elements of S is 1/(1-g). Example: a(4)=20 because we have 1+3, 1'+3, 3+1, 3+1', and 2^4=16 of sums x+y+z+u, where x,y,z,u are taken from {1,1'}.

%C (End)

%C a(n-1) is the top left entry of the n-th power of any of the six 3 X 3 matrices [1, 1, 0; 1, 1, 1; 0, 1, 0] or [1, 1, 1; 0, 1, 1; 1, 1, 0] or [1, 0, 1; 1, 1, 1; 1, 1, 0] or [1, 1, 1; 1, 0, 1; 0, 1, 1] or [1, 0, 1; 0, 0, 1; 1, 1, 1] or [1, 1, 0; 1, 0, 1; 1, 1, 1]. - _R. J. Mathar_, Feb 03 2014

%H G. C. Greubel, <a href="/A052534/b052534.txt">Table of n, a(n) for n = 0..1000</a>

%H Jean-Luc Baril, Rigoberto Flórez, and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/symasympyramid.pdf">Counting symmetric and asymmetric peaks in motzkin paths with air pockets</a>, Univ. Bourgogne (France, 2023).

%H C. P. de Andrade, J. P. de Oliveira Santos, E. V. P. da Silva and K. C. P. Silva, <a href="http://dx.doi.org/10.4236/ojdm.2013.31006">Polynomial Generalizations and Combinatorial Interpretations for Sequences Including the Fibonacci and Pell Numbers</a>, Open Journal of Discrete Mathematics, 2013, 3, 25-32 doi:10.4236/ojdm.2013.31006. - From _N. J. A. Sloane_, Feb 20 2013

%H E. S. Egge, <a href="https://arxiv.org/abs/math/0307050">Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations</a>, arXiv:math/0307050 [math.CO], 2003, sec. 8.

%H Rigoberto Flórez and José L. Ramírez, <a href="http://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p138.pdf">Some enumerations on non-decreasing Motzkin paths</a>, Australasian J. of Combinatorics (2018) Vol. 72(1), 138-154.

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

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

%H S. Morier-Genoud, V. Ovsienko, and S. Tabachnikov, <a href="https://doi.org/10.1007/s00209-015-1520-x">Introducing supersymmetric frieze patterns and linear difference operators</a>, Math. Z. 281 (2015) 1061.

%H Alexey Ustinov, <a href="http://arxiv.org/abs/1503.04497">Supercontinuants</a>, arXiv:1503.04497 [math.NT], 2015.

%H R. Witula, D. Slota and A. Warzynski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Slota/slota57.html">Quasi-Fibonacci Numbers of the Seventh Order</a>, J. Integer Seq., 9 (2006), Article 06.4.3.

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

%F G.f.: (1 - x^2)/(1 - 2*x - x^2 + x^3).

%F a(n) = 2*a(n-1) + a(n-2) - a(n-3), with a(0)=1, a(1)=2, a(2)=4.

%F a(n) = Sum_{alpha = RootOf(1-2*x-x^2+x^3)} (1/7)*(2 + alpha)*alpha^(-1-n).

%F a(n) = central term in the (n+1)-th power of the 3 X 3 matrix (shown in the example of A066170): [1 1 1 / 1 1 0 / 1 0 0]. E.g. a(6) = 101 since the central term in M^7 = 101. - _Gary W. Adamson_, Feb 01 2004

%F a(n) = A006054(n+2) - A006054(n). - _Vladimir Kruchinin_, Sep 09 2010

%F a(n) = A077998(n+2) - 2*A006054(n+2), which implies 7*a(n-2) = (2 + c(4) - 2*c(2))*(1 + c(1))^n + (2 + c(1) - 2*c(4))*(1 + c(2))^n + (2 + c(2) - 2*c(1))*(1 + c(4))^n, where c(j)=2*Cos(2Pi*j/7), a(-2)=a(-1)=1 since A077998 and A006054 are equal to the respective quasi-Fibonacci numbers. [Witula, Slota and Warzynski] - _Roman Witula_, Aug 07 2012

%F a(n+1) = A033303(n+1) - A033303(n). - _Roman Witula_, Sep 14 2012

%F a(n) = A006054(n+2)-A006054(n). - _R. J. Mathar_, Nov 23 2020

%F a(n) = A028495(-1-n) for all n in Z. - _Michael Somos_, Dec 12 2023

%e G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 20*x^4 + 45*x^5 + 101*x^6 + 227*x^7 + 510*x^8 + ... - _Michael Somos_, Dec 12 2023

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

%t LinearRecurrence[{2,1,-1},{1,2,4},40] (* _Roman Witula_, Aug 07 2012 *)

%t CoefficientList[Series[(1-x^2)/(1-2x-x^2+x^3), {x, 0, 40}], x] (* _Vincenzo Librandi_, Mar 17 2015 *)

%t a[ n_] := {0, 1, 0} . MatrixPower[{{1, 1, 1}, {1, 1, 0}, {1, 0, 0}}, n+1] . {0, 1, 0}; (* _Michael Somos_, Dec 12 2023 *)

%o (Maxima) h(n):=if n=0 then 1 else sum(sum(binomial(k,j)*binomial(j,n-3*k+2*j)*2^(3*k-n-j)*(-1)^(k-j),j,0,k),k,1,n); a(n):=if n<2 then h(n) else h(n)-h(n-2); /* _Vladimir Kruchinin_, Sep 09 2010 */

%o (Magma) [n le 3 select 2^(n-1) else 2*Self(n-1)+Self(n-2)-Self(n-3): n in [1..40]]; // _Vincenzo Librandi_, Mar 17 2015

%o (PARI) my(x='x+O('x^40)); Vec((1-x^2)/(1-2*x-x^2+x^3)) \\ _G. C. Greubel_, May 09 2019

%o (PARI) {a(n) = [0, 1, 0] * [1, 1, 1; 1, 1, 0; 1, 0, 0]^(n+1) * [0, 1, 0]~}; /* _Michael Somos_, Dec 12 2023 */

%o (SageMath) ((1-x^2)/(1-2*x-x^2+x^3)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, May 09 2019

%o (GAP) a:=[1,2,4];; for n in [4..40] do a[n]:=2*a[n-1]+a[n-2]-a[n-3]; od; a; # _G. C. Greubel_, May 09 2019

%Y Cf. A028495, A066170.

%K nonn,easy

%O 0,2

%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000