Combinatorics & Partitions proof

r0r0trog · #1 $Old$ November 21st, 2009, 11:12 AM

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>

qmech · #2 $Old$ November 21st, 2009, 05:32 PM

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.

r0r0trog · #3 $Old$ November 22nd, 2009, 02:10 AM

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

hfcriske · #4 $Old$ November 22nd, 2009, 02:37 AM

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.

awkward · #5 $Old$ November 22nd, 2009, 07:04 AM

Quote:

Originally Posted by r0r0trog $View Post$

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:

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

Let's say the original set is $\{x_1, x_2, \dots , x_n\}$ . Say that a set partition has property i if one of the subsets in the partition is $\{x_i\}$ . 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.