A360586 Expansion of e.g.f.: exp(x)*(exp(x)-1)*(exp(x)-x).

0, 1, 3, 10, 37, 136, 479, 1618, 5289, 16876, 52915, 163846, 502781, 1532896, 4651911, 14070394, 42456913, 127894996, 384799067, 1156756462, 3475250085, 10436235976, 31330727983, 94038321250, 282211432697, 846835624636, 2540926304259, 7623651327958

Offset

0,3

Comments

a(n) is the number of ordered set partitions of an n-set into 3 sets such that the first set has at least one element, the second set cannot have a single element, and the third set has no restrictions.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-40,12).

Formula

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

G.f.: x*(1 - 6*x + 14*x^2 - 11*x^3)/((1 - x)^2*(1 - 2*x)^2*(1 - 3*x)). - Andrew Howroyd, Nov 16 2025

a(n) ~ 3^n. - Charles R Greathouse IV, May 31 2026

Example

The 37 set partitions for n=4 are the following:
{1,2,3,4}, {}, {}  (1 of these);
{1,2,3}, {}, {4}   (4 of this type);
{1,2}, {}, {3,4}   (6 of this type);
{1,2}, {3,4}, {}   (6 of this type);
{1}, {2,3}, {4}    (12 of this type);
{1}, {2,3,4}, {}   (4 of this type);
{1}, {}, {2,3,4}   (4 of this type).

Mathematica

With[{nn=30}, CoefficientList[Series[Exp[x](Exp[x]-1)(Exp[x]-x), {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Apr 02 2023 *)

Prog

(PARI) a(n)=3^n-(n+2)*2^n/2+n \\ Charles R Greathouse IV, May 31 2026

Crossrefs

Sequence in context: A138807 A149043 A296000 * A242725 A151315 A164048

Adjacent sequences: A360583 A360584 A360585 * A360587 A360588 A360589

Keyword

nonn,easy,changed

Author

Enrique Navarrete, Feb 12 2023

Status

approved