Using a recursion relation to find the number of elements in a partition

[Raziel2701]

Homework Statement

Let S(n,r) denote the number of elements of $$A_n$$ of rank r. Then S(n,r) satisfies the recursion $$S(n,r)=(n-r)S(n-1,r-1) + S(n-1,r)$$ Verify this formula for n=4 and r=0,1,2,3,4, using the values
S(3,0) = 1
S(3,1)=3
S(3,2)=1

Homework Equations

The Attempt at a Solution

So I had already done by hand what the different partitions of A_n are. The set I'm taking the partitions from is {1,2,3,4}. Now for all of the calculations using the formula I get the right number of elements, but for S(4,2) I get 7 according to the formula, when I get 3 when I calculate this by hand.

So let me show you:
The partitions of the set {1,2,3,4} of rank 2 are:

{{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}} Correct? So am I doing something wrong? There are three elements of A_n of rank 2.

 

[tiny-tim]

Hi Raziel2701!

The partitions of the set {1,2,3,4} of rank 2 are:

{{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}} Correct? So am I doing something wrong? There are three elements of A_n of rank 2.

Don't you have to include 4 more, of the type {{1},{2,3,4}} ?

 

[Raziel2701]

I have another question, and thanks for pointing out my error :). I have to draw the Hasse diagram for these partitions. Is it going to look like this? http://imgur.com/z4mjt.png

I think it's messy, which is why I think it's wrong, so if someone could point me in the right direction that'd be great.

Thanks.

 

[tiny-tim]

I have to draw the Hasse diagram for these partitions. Is it going to look like this? http://imgur.com/z4mjt.png

No, you've drawn each two-element set as containing every one-element set!