A052529 Expansion of (1-x)^3/(1 - 4*x + 3*x^2 - x^3).

1, 1, 4, 13, 41, 129, 406, 1278, 4023, 12664, 39865, 125491, 395033, 1243524, 3914488, 12322413, 38789712, 122106097, 384377665, 1209982081, 3808901426, 11990037126, 37743426307, 118812495276, 374009739309, 1177344897715

Offset

0,3

Comments

a(n+1) is the number of distinct matrix products in (A+B+C+D)^n where commutator [A,B] = [A,C] = [B,C] = 0 but D does not commute with A, B, or C. - Paul D. Hanna and Max Alekseyev, Feb 01 2006

Starting (1, 4, 13, ...) = INVERT transform of the triangular series, (1, 3, 6, 10, ...). Example: a(5) = 129 = termwise products of (1, 1, 4, 13, 41) and (15, 10, 6, 3, 1) = (15 + 10 + 24 + 39 + 41). - Gary W. Adamson, Apr 10 2009

a(n) is the number of generalized compositions of n when there are i^2/2+i/2 different types of i, (i=1,2,...). - Milan Janjic, Sep 24 2010

Dedrickson (Section 4.2) gives a bijection between colored compositions of n, where each part k has one of binomial(k+1,2) colors, and 0,1,2,3 strings of length n-1 avoiding 10, 20 and 21. Cf. A095263. For a refinement of this sequence counting binomial(k+1,2)-colored compositions by the number of parts see A127893. - Peter Bala, Sep 17 2013

References

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 80.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3 , example 14.

C. R. Dedrickson III, Compositions, Bijections, and Enumerations Thesis, Jack N. Averitt College of Graduate Studies, Georgia Southern University, 2012.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 459

Milan Janjić, Pascal Matrices and Restricted Words, J. Int. Seq., Vol. 21 (2018), Article 18.5.2.

Index entries for linear recurrences with constant coefficients, signature (4,-3,1).

Formula

a(n) = Sum_{a=0..n} (Sum_{b=0..n} (Sum_{c=0..n} C(n-b-c,a)*C(n-a-c,b)*C(n-a-b,c))).

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

a(n) = 4*a(n-1) - 3*a(n-2) + a(n-3) for n>=4.

a(n) = Sum_{alpha = RootOf(-1+4*x-3*x^2+x^3)} (1/31)*(6 - 5*alpha - 3*alpha^2) * alpha^(-1-n).

For n>0, a(n) = Sum_{k=0..n-1} Sum_{i=0..k} Sum_{j=0..i} a(j). - Benoit Cloitre, Jan 26 2003

a(n) = Sum_{k=0..n} binomial(n+2*k-1, n-k). - Vladeta Jovovic, Mar 23 2003

If p[i]=i(i+1)/2 and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, May 02 2010

Recurrence equation: a(n) = Sum_{k = 1..n} 1/2*k*(k+1)*a(n-k) with a(0) = 1. - Peter Bala, Sep 19 2013

a(n) = Sum_{i=0..n} (n-i)*A052544(i) = A052544(n) - A052544(n-1) for n>=1. - Areebah Mahdia, Jul 07 2020

Maple

spec := [S, {S=Sequence(Prod(Z, Sequence(Z), Sequence(Z), Sequence(Z)))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
f:= gfun:-rectoproc({a(n+4)-4*a(n+3)+3*a(n+2)-a(n+1), a(0) = 1, a(1) = 1, a(2) = 4, a(3) = 13}, a(n), `remember`):
seq(f(n), n=0..40); # Robert Israel, Dec 19 2014

Mathematica

CoefficientList[Series[(-1+x)^3/(-1+4*x-3*x^2+x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 22 2012 *)
LinearRecurrence[{4, -3, 1}, {1, 1, 4, 13}, 30] (* Harvey P. Dale, Oct 04 2015 *)

Prog

(Magma) I:=[1, 1, 4, 13, 41, 129]; [n le 6 select I[n] else 4*Self(n-1) -3*Self(n-2)+Self(n-3): n in [1..40]]; // Vincenzo Librandi, Jun 22 2012
(PARI) my(x='x+O('x^30)); Vec((1-x)^3/(1-4*x+3*x^2-x^3)) \\ G. C. Greubel, May 12 2019
(Sage) ((1-x)^3/(1-4*x+3*x^2-x^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 12 2019

Crossrefs

Cf. A001906, A052530, A055991, A095263.

Trisection of A000930.

First differences of A052544.

Row sums of triangle A127893.

Sequence in context: A368344 A268989 A190214 * A049222 A239249 A141364

Adjacent sequences: A052526 A052527 A052528 * A052530 A052531 A052532

Keyword

nonn,easy

Author

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

Status

approved