A168583 The number of ways of partitioning the multiset {1,1,2,3,...,n-1} into exactly three nonempty parts.

1, 4, 16, 58, 196, 634, 1996, 6178, 18916, 57514, 174076, 525298, 1582036, 4758394, 14299756, 42948418, 128943556, 387027274, 1161475036, 3485211538, 10457207476, 31374768154, 94130595916, 282404370658, 847238277796, 2541765165034, 7625396158396

Offset: 3

Author

Martin Griffiths, Nov 30 2009

Keywords

• nonn
• easy

Comments

The number of ways of partitioning the multiset {1, 1, 2, 3, ..., n-1} into exactly two, four and five nonempty parts are given in A083329, A168584 and A168585, respectively.

Examples

			The partitions of {1,1,2,3} into exactly three nonempty parts are {{1},{1},{2,3}}, {{1},{2},{1,3}}, {{1},{3},{1,2}} and {{2},{3},{1,1}}.
		

Links

• M. Griffiths, I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5.
• Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

Crossrefs

Cf. A083329, A126644, A168584, A168585.

Programs

Magma

[3^(n-2) - 3*2^(n-3) + 1: n in [3..35]]; // Vincenzo Librandi, Dec 12 2015

Maple

A168583:=n->3^(n-2)-3*2^(n-3)+1: seq(A168583(n), n=3..40); # Wesley Ivan Hurt, Dec 12 2015

Mathematica

f1[n_] := 3^(n - 2) - 3 2^(n - 3) + 1; Table[f1[n], {n, 3, 25}]

Formula

For a>=3, a(n) = 3^(n-2) - 3*2^(n-3) + 1.

E.g.f.: 3*e^(3x) - 3*e^(2x) + e^x (shifted).

O.g.f.: x^3*(1-2x+3x^2)/((1-x)*(1-2x)*(1-3x)).

a(n) = A126644(n-3). - R. J. Mathar, Dec 11 2009