OFFSET
0,2
COMMENTS
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
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
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
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
From Paul Barry, Nov 03 2010: (Start)
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)).
The second expression shows the link to the Motzkin numbers. (End)
From Emeric Deutsch, Oct 31 2010: (Start)
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'}.
(End)
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
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Jean-Luc Baril, Rigoberto Flórez, and José L. Ramírez, Counting symmetric and asymmetric peaks in motzkin paths with air pockets, Univ. Bourgogne (France, 2023).
C. P. de Andrade, J. P. de Oliveira Santos, E. V. P. da Silva and K. C. P. Silva, Polynomial Generalizations and Combinatorial Interpretations for Sequences Including the Fibonacci and Pell Numbers, Open Journal of Discrete Mathematics, 2013, 3, 25-32 doi:10.4236/ojdm.2013.31006. - From N. J. A. Sloane, Feb 20 2013
E. S. Egge, Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations, arXiv:math/0307050 [math.CO], 2003, sec. 8.
Rigoberto Flórez and José L. Ramírez, Some enumerations on non-decreasing Motzkin paths, Australasian J. of Combinatorics (2018) Vol. 72(1), 138-154.
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 15.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 464
S. Morier-Genoud, V. Ovsienko, and S. Tabachnikov, Introducing supersymmetric frieze patterns and linear difference operators, Math. Z. 281 (2015) 1061.
Alexey Ustinov, Supercontinuants, arXiv:1503.04497 [math.NT], 2015.
R. Witula, D. Slota and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq., 9 (2006), Article 06.4.3.
Index entries for linear recurrences with constant coefficients, signature (2,1,-1).
FORMULA
G.f.: (1 - x^2)/(1 - 2*x - x^2 + x^3).
a(n) = 2*a(n-1) + a(n-2) - a(n-3), with a(0)=1, a(1)=2, a(2)=4.
a(n) = Sum_{alpha = RootOf(1-2*x-x^2+x^3)} (1/7)*(2 + alpha)*alpha^(-1-n).
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
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
a(n) = A028495(-1-n) for all n in Z. - Michael Somos, Dec 12 2023
EXAMPLE
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
MAPLE
spec := [S, {S=Sequence(Union(Z, Prod(Z, Sequence(Prod(Z, Z)))))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
MATHEMATICA
LinearRecurrence[{2, 1, -1}, {1, 2, 4}, 40] (* Roman Witula, Aug 07 2012 *)
CoefficientList[Series[(1-x^2)/(1-2x-x^2+x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 17 2015 *)
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 *)
PROG
(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 */
(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
(PARI) my(x='x+O('x^40)); Vec((1-x^2)/(1-2*x-x^2+x^3)) \\ G. C. Greubel, May 09 2019
(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 */
(SageMath) ((1-x^2)/(1-2*x-x^2+x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 09 2019
(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
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved