OFFSET
0,2
COMMENTS
Equals INVERT transform of (1, 1, 3, 8, 21, 55, 144, ...). - Gary W. Adamson, May 01 2009
The Ze2 sums, see A180662, of triangle A065941 equal the terms (doubled) of this sequence. - Johannes W. Meijer, Aug 16 2011
Equals the partial sums of A052529 starting (1, 1, 4, 13, 41, 129, ...). - Gary W. Adamson, Feb 15 2012
First trisection of Narayana's cows sequence A000930. - Oboifeng Dira, Aug 03 2016
From Peter Bala, Nov 03 2017: (Start)
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
Vincenzo Librandi, Table of n, a(n) for n = 0..500
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 480
Sergey Kitaev and Artem Pyatkin, On permutations avoiding partially ordered patterns defined by bipartite graphs, arXiv:2204.08936 [math.CO], 2022.
H. Stephan, Rekursive Folgen im Pascalschen Dreieck
Index entries for linear recurrences with constant coefficients, signature (4,-3,1).
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) = Sum_{k=0..n} binomial(n+2*k, 3*k). - Richard L. Ollerton, May 12 2004
G.f.: 1 / (1 - x - x / (1 - x)^2). - Michael Somos, Jan 12 2012
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);
A052544 := proc(n): add(binomial(n+2*k, 3*k), k=0...n) end: seq(A052544(n), n=0..25); # Johannes W. Meijer, Aug 16 2011
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 */
(PARI) Vec((1-x)^2/(1-4*x+3*x^2-x^3)+O(x^30)) \\ Charles R Greathouse IV, 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
More terms from James A. Sellers, Jun 06 2000
STATUS
approved