|
| |
|
|
A052534
|
|
Expansion of (1-x)*(1+x)/(1-2*x-x^2+x^3).
|
|
11
|
|
|
|
1, 2, 4, 9, 20, 45, 101, 227, 510, 1146, 2575, 5786, 13001, 29213, 65641, 147494, 331416, 744685, 1673292, 3759853, 8448313, 18983187, 42654834, 95844542, 215360731, 483911170, 1087338529, 2443227497, 5489882353, 12335653674
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
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)
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
|
|
|
|
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
|
|
|
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
|
| |
|
|
