login
A145839
Number of 3-compositions of n.
5
1, 3, 15, 73, 354, 1716, 8318, 40320, 195444, 947380, 4592256, 22260144, 107902088, 523036176, 2535324816, 12289536016, 59571339552, 288761470848, 1399719859808, 6784893012864, 32888561860032, 159421452802624, 772767131681280, 3745851196992000
OFFSET
0,2
COMMENTS
A 3-composition of n is a matrix with three rows, such that each column has at least one nonzero element and whose elements sum up to n.
Matrix inverse of (A000217(A004736)*A154990). - Mats Granvik, Jan 19 2009
(1 +3*x +15*x^2 +73*x^3 + ...) = 1/(1 -3*x -6*x^2 -10*x^3 -15*x^4 - ...). - Gary W. Adamson, Jul 27 2009
For n>1, a(n) is the number of generalized compositions of n-1 when there are i^2/2 +3i/2 +1 different types of i, (i=1,2,...). - Milan Janjic, Sep 24 2010
REFERENCES
G. Louchard, Matrix compositions: a probabilistic approach, Proceedings of GASCom and Bijective Combinatorics 2008, Bibbiena, Italy, pp. 159-170.
LINKS
M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
E. Munarini, M. Poneti, and S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8.
FORMULA
a(n+3) = 6*a(n+2) - 6*a(n+1) + 2*a(n).
G.f.: (1-x)^3/(2*(1-x)^3 - 1).
a(n) = Sum_{k>=0} C(n+3*k-1,n) / 2^(k+1). - Vaclav Kotesovec, Dec 31 2013
a(n) = Sum_{j=0..n-1} binomial(n-j+2, 2)*a(j) with a(0) = 1. - G. C. Greubel, Mar 07 2021
MAPLE
a:= proc(n) option remember; `if`(n=0, 1,
add(a(n-j)*binomial(j+2, 2), j=1..n))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Sep 01 2015
MATHEMATICA
Table[Sum[Binomial[n+3*k-1, n]/2^(k+1), {k, 0, Infinity}], {n, 0, 20}] (* Vaclav Kotesovec, Dec 31 2013 *)
a[n_]:= a[n]= If[n==0, 1, Sum[Binomial[n-j+2, 2]*a[j], {j, 0, n-1}]]; Table[a[n], {n, 0, 20}] (* G. C. Greubel, Mar 07 2021 *)
PROG
(Sage)
@CachedFunction
def a(n):
if n==0: return 1
else: return sum( binomial(n-j+2, 2)*a(j) for j in (0..n-1))
[a(n) for n in (0..25)] # G. C. Greubel, Mar 07 2021
(Magma) I:=[3, 15, 73]; [1] cat [n le 3 select I[n] else 6*Self(n-1) - 6*Self(n-2) + 2*Self(n-3): n in [1..30]]; // G. C. Greubel, Mar 07 2021
CROSSREFS
Cf. A003480 (2-compositions), A145840 (4-compositions), A145841 (5-compositions).
Column k=3 of A261780.
Sequence in context: A155117 A137638 A156019 * A232289 A370480 A055837
KEYWORD
nonn,easy
AUTHOR
Simone Rinaldi (rinaldi(AT)unisi.it), Oct 21 2008
EXTENSIONS
Offset corrected by Alois P. Heinz, Aug 31 2015
STATUS
approved