Hi Francesco,

I think that you want to compute the number of partitions without singletons of a set of n elements. The number of partitions of a set of n elements is given by the Bell number B_n. The first Bell numbers are

B_1=1, B_2=2, B_3=5, B_4=15, B_5=52, B_6=203, etc.

For example, for n=4 there are 15 ways to decompose the set S={a,b,c,d} into nonempty subsets:

S = {a}U{b}U{c}U{d},

S = {a}U{b}U{c,d},

S = {a}U{c}U{b,d},

S = {b}U{c}U{a,d},

... ...

S = {a,b,c,d}.

But among these 15 partitions of S={a,b,c,d}, only 4 have no singletons, i.e.,

S = {a,b}U{c,d},

S = {a,c}U{b,d},

S = {a,d}U{b,c},

S = {a,b,c,d}.

A "set partition" is different from an "integer partition", which Christian was talking about.

Let A_n be the number of partitions without singletons of a set of n elements. The first A_n are (see OEIS A000296, https://oeis.org/A000296)

A_1=0, A_2=1, A_3=1, A_4=4, A_5=11, A_6=41, etc.

Note that B_{n-1}-A_{n-1} represents the number of partitions with at least one singleton of a set of n-1 elements. By grouping all singletons of a partition of [1 .. n-1] in a single subset and adding the element n, we find a 1:1 correspondence with the set of partitions without singletons of [1 .. n], hence the formula

A_n = B_{n-1}-A_{n-1}, [1]

holding for any n>=3.

Using [1] iteratively, one finds the following simple formula for A_n, n>=2,

A_n = \sum_{i=1,...,n-1} (-1)^{n-1-i} B_i.

Other formulas and properties can be found in OEIS A000296. For formulas and properties of Bell numbers, see OEIS A000110 or Wikipedia.