Thread: Combinatorics & Partitions proof

I'm totally lost on this one... Any hints or solutions are welcome! Thanks in advance.

For n ≥ 0, let Bn be the number of partitions of a set of size n. For example, B1 = 1, B2 = 2, B3 = 5, B4 = 15. By convention, B0 = 1. Now, let Dn be the number of partitions of a set of size n into subsets of size at least two. Show that <attachment>

If by 'partition' you mean an unordered way to write a number n as a sum of positive integers, the first few partitions are:

P(1) = 1, as
1 can only be written as 1.

P(2) = 2, as
2 can be written as 2 or 1+1.

P(3) = 3, as
3 can be written as 3 or 2+1 or 1+1+1.

P(4) = 5, as
4 can be written as 4 or 3+1 or 2+2, 2+1+1, 1+1+1+1.

which don't match your problem description.

Please clarify your problem.

Well, Bi is the i:th Bell number.
Bell number - Wikipedia, the free encyclopedia

He's indeed referring to the Bell numbers, which are the number of partitions of a set (of n integers) into subsets, and not partitions of an integer.

Dn is simply the number of partitions of a set of integers, such that no partition has less than 2 elements (also known as singleton-free partitions, or 2-restricted Bell numbers, see integer sequence A000296).

While I can't prove the entire thing at the moment, I can say that Bi = Di + D(i+1), since if you take away all the singleton-free partitions of Bi, the remaining Bi - Di partitions will (obviously) all have at least one singleton. Group all these singletons together (partitionwise) and add the element i+1, now you have all the D(i+1) partitions.

The proof is very likely to have something to do with the sieve principle. Also, Dn are partition analogues of derangements, if that's any help.

Originally Posted by r0r0trog

I'm totally lost on this one... Any hints or solutions are welcome! Thanks in advance.

For n ≥ 0, let Bn be the number of partitions of a set of size n. For example, B1 = 1, B2 = 2, B3 = 5, B4 = 15. By convention, B0 = 1. Now, let Dn be the number of partitions of a set of size n into subsets of size at least two. Show that <attachment>

Hint:

is the number of set partitions that do not include any singleton subsets.

Let's say the original set is . Say that a set partition has property i if one of the subsets in the partition is . Now apply the Principle of Inclusion/Exclusion, also known as the Sieve Principle, to find the number of partitions which has none of the properties 1,2, ..., n.