A101822 Expansion of 1/(1-x-2*x^2-3*x^3).

1, 1, 3, 8, 17, 42, 100, 235, 561, 1331, 3158, 7503, 17812, 42292, 100425, 238445, 566171, 1344336, 3192013, 7579198, 17996232, 42730667, 101460725, 240910755, 572024206, 1358227891, 3225008568, 7657536968, 18182237777, 43172337417

Offset: 0

Author

Gary W. Adamson, Dec 17 2004

Keywords

• nonn
• easy

Comments

a(n) is the number of compositions (ordered partitions) of n into parts 1, 2, and 3 where there is one kind of part 1, two kinds of part 2, and three kinds of part 3. - Joerg Arndt, Apr 19 2025

Links

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

Crossrefs

Cf. A000073, A100550. Row k=3 in A380886.

Programs

Magma

I:=[1,1,3]; [n le 3 select I[n] else Self(n-1) +2*Self(n-2) +3*Self(n-3): n in [1..41]]; // G. C. Greubel, Mar 27 2023

Mathematica

a[0]=a[1]=1; a[2]=3; a[n_]:= a[n]= a[n-1] + 2a[n-2] + 3a[n-3];
Table[ a[n], {n, 0, 29}] (* Or *)
a[n_]:= (MatrixPower[{{1,1,1}, {2,0,0}, {0,3/2,0}}, n].{{1}, {0}, {0}})[[1, 1]];
Table[ a[n], {n, 0, 29}] (* Robert G. Wilson v, Dec 20 2004 *)
LinearRecurrence[{1,2,3},{1,1,3},30] (* Harvey P. Dale, Feb 06 2019 *)

PARI

Vec(1/(1-x-2*x^2-3*x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

SageMath

@CachedFunction
def a(n): # a = A101822
    if (n<3): return (1,1,3)[n]
    else: return a(n-1) + 2*a(n-2) + 3*a(n-3)
[a(n) for n in range(41)] # G. C. Greubel, Mar 27 2023

Formula

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

a(n) is the top term in M^n * [1, 0, 0], where M = the 3X3 matrix ([1, 1, 1], [2, 0, 0], [0, 3/2, 0]).

Extensions

More terms from Robert G. Wilson v, Dec 20 2004