A190139 a(n) = 2*a(n-1) + a(n-2) + a(n-3) + a(n-4), a(-2)=0, a(-1)=0, a(0)=1, a(1)=1.

1, 1, 3, 8, 21, 54, 140, 363, 941, 2439, 6322, 16387, 42476, 110100, 285385, 739733, 1917427, 4970072, 12882689, 33392610, 86555408, 224356187, 581543081, 1507390367, 3907235410, 10127760455, 26251689768, 68045765768, 176378217169, 457181650329, 1185038973363

Offset: 0

Author

Vladimir Kruchinin, May 05 2011

Keywords

• nonn

Comments

Number of compositions of n where there is one sort of part 1, two sorts of part 2, three sorts of part 3, and four sorts of every other part. - Joerg Arndt, Mar 15 2014

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Vincenzo Librandi)
• Index entries for linear recurrences with constant coefficients, signature (2,1,1,1)

Programs

Magma

I:=[1,1,3,8]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)+Self(n-3)+Self(n-4): n in [1..40]]; // Vincenzo Librandi, Sep 20 2011

Mathematica

RecurrenceTable[{a[n] == 2 a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4], a[-2] == a[-1] == 0, a[0] == a[1] == 1}, a, {n, 0, 30}] (* Michael De Vlieger, Oct 28 2015 *)
LinearRecurrence[{2, 1, 1, 1}, {1, 1, 3, 8}, 31] (* Michael De Vlieger, Oct 28 2015 *)
nxt[{a_,b_,c_,d_}]:={b,c,d,2d+c+b+a}; NestList[nxt,{0,0,1,1},50][[All,1]] (* Harvey P. Dale, Mar 04 2022 *)

Maxima

a(n):=sum(sum((sum(binomial(k,j)*sum(binomial(j,i-j)*binomial(k-j,t-3*(k-j)-i),i,j,t-k+j),j,0,k))*binomial(-t+n+k-1,k-1),t,k,n),k,1,n);

PARI

x='x+O('x^30); Vec((1-x)/(1-2*x-x^2-x^3-x^4)) \\ G. C. Greubel, Dec 29 2017

Formula

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

a(n) = Sum_{k=1..n} (Sum_{t=k..n} (Sum_{j=0..k} C(k,j) * Sum_{i=j..t-k+j} C(j,i-j)*C(k-j,t-3*(k-j)-i)*C(-t+n+k-1,k-1))), n>0, a(0)=1.

a(n) = A103142(n) - A103142(n-1). - R. J. Mathar, Sep 17 2011

Extensions

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021