|
|
A052544
|
|
Expansion of (1-x)^2/(1 - 4*x + 3*x^2 - x^3).
|
|
9
|
|
|
1, 2, 6, 19, 60, 189, 595, 1873, 5896, 18560, 58425, 183916, 578949, 1822473, 5736961, 18059374, 56849086, 178955183, 563332848, 1773314929, 5582216355, 17572253481, 55315679788, 174128175064, 548137914373, 1725482812088
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Equals INVERT transform of (1, 1, 3, 8, 21, 55, 144, ...). - Gary W. Adamson, May 01 2009
Let f(x) = x/(1 - x^3), the characteristic function of numbers of the form 3*n + 1. Then f(f(x)) = Sum_{n >= 0} a(n)*x^(3*n+1).
a(n) = the number of compositions of 3*n + 1 into parts of the form 3*m + 1. For example, a(2) = 6 and the six compositions of 7 into parts of the form 3*m + 1 are 7, 4 + 1 + 1 + 1, 1 + 4 + 1 + 1, 1 + 1 + 4 + 1, 1 + 1 + 1 + 4 and 1 + 1 + 1 + 1 + 1 + 1 + 1. Cf. A001519, which gives the number of compositions of an odd number into odd parts. (End)
a(n-1) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 4>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the first element is larger than the second and third elements, and the fourth element is larger than the second element. - Sergey Kitaev, Dec 09 2020
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1-x)^2/(1 -4*x +3*x^2 -x^3).
a(n) = 4*a(n-1) - 3*a(n-2) + a(n-3).
a(n) = Sum(-1/31*(-4-7*_alpha+2*_alpha^2)*_alpha^(-1-n), _alpha=RootOf(-1+4*_Z-3*_Z^2+_Z^3)).
a(n) = hypergeom([(n+1)/2, n/2+1, -n], [1/3, 2/3], -4/27). - Peter Luschny, Nov 03 2017
|
|
EXAMPLE
|
G.f. = 1 + 2*x + 6*x^2 + 19*x^3 + 60*x^4 + 189*x^5 + 595*x^6 + 1873*x^7 + ...
|
|
MAPLE
|
spec := [S, {S=Sequence(Union(Z, Prod(Z, Sequence(Z), Sequence(Z))))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..25);
|
|
MATHEMATICA
|
LinearRecurrence[{4, -3, 1}, {1, 2, 6}, 30] (* Harvey P. Dale, Jul 13 2011 *)
Table[Sum[Binomial[n + 2 k, 3 k], {k, 0, n}], {n, 0, 30}] (* or *)
CoefficientList[Series[(1-x)^2/(1-4x+3x^2-x^3), {x, 0, 30}], x] (* Michael De Vlieger, Aug 03 2016 *)
|
|
PROG
|
(PARI) {a(n) = sum(k=0, n, binomial(n + 2*k, 3*k))}; /* Michael Somos, Jan 12 2012 */
(Magma) I:=[1, 2, 6]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2) +Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jan 12 2012
(Sage) ((1-x)^2/(1-4*x+3*x^2-x^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 09 2019
(GAP) a:=[1, 2, 6];; for n in [4..30] do a[n]:=4*a[n-1]-3*a[n-2]+a[n-3]; od; a; # G. C. Greubel, May 09 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|