I need to show

I understand how to get but the 3 is throwing me off a little bit, can anyone help?

Printable View

- Apr 16th 2008, 03:36 PMJrb599Stirling numbers
I need to show

I understand how to get but the 3 is throwing me off a little bit, can anyone help? - Apr 16th 2008, 04:34 PMmr fantastic
The comes from partitioning the n elements into 1 set of size 3 and n - 3 sets of size 1.

Then you have to add the number of ways of partitioning the n elements into 2 sets of size 2 and n - 4 sets of size 1. This is equal to (the number of ways of choosing 4 elements from the n elements) times (number of ways of choosing 2 elements from 4)/2:

.

You divide by 2 because otherwise you've double counted .... Think about it. - Apr 16th 2008, 04:49 PMPlato
First, these must be

*Stirling Numbers of the*.__second kind__

**S****(n,k)**is the number of ways to partition a set of n individuals into k non-empty cells.

Therefore, in this problem we must have .

So if then how many ways can one partition the set in two non-empty subsets?

It is clear that we can have one cell with three elements and one with one element: ways.

Or we can have two cells with two elements each: .

Can you continue? - Apr 17th 2008, 07:09 AMJrb599
- Apr 17th 2008, 08:43 PMmr fantastic
There's no problem with n = 2 or n = 3 ....

n = 2: S(2, 0) = 0, since there's no way to partition 2 elements into zero sets .... (note that in general, , where is the Kronecker delta).

n = 3: S(3, 1) = 1, since there's only one way to partition 3 elements into one set ....

**However .....**these values of n*cannot*be used in the formula (since the combinatorials are undefined for n < 4), which is what I think Plato was refering to.

One*might*try to argue a case that , and ......