# Number of Partitions of equal length (of a set)

1. Sep 23, 2006

### mattmns

Not really homework, but something that our professor asked us the other day.

Here is the question (I think):
Let S be a set with #S=8. Find the number of partitions of S with equal length.
-------
That probably makes no sense, namely the equal length part, so let me elaborate.

Note: Let P be a partition of S. Also, an n-subset is a subset with cardinality n

He wants us to count the number of partitions P for, #P=8, #P=4, #P=2, #P=1. Hence, there will be 8 1-subsets for #P=8, 4 2-subsets for #P=4, 2 4-subsets for #P=2, and 1 8-subset for #P=1.

------------
For #P=8 there is only one way to partition the 8 elements into 1-subsets. (P = {{a1},{a2},{a3},...,{a8}})

For #P=1 there is only one way to partition the 8 elements into an 8-subset. (P = {{a1,a2,a3,...,a8}})

For #P=2, I believe there to be $\binom{8}{4}$ partitions.
Reasoning being that the order of the elements in each element in the partition does not matter, and we will be choosing the first element in the partition which has 4 elements in it, from a total of 8 elements.

For #P=4, I am not 100% sure, but this is what I think. The number will be: $$\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}$$.
My reasoning being the following. We will first choose the first element in the partition which has 2 elements in it, and we have 8 elements to choose from, then we will have 6 to choose from for the second 2 element set in our partition, etc, but we must divide by 4! since we counted the order of these 4 elements in our partition.

By the addition principle our total number of partitions of equal length will be: $$1+1+\binom{8}{4}+\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}$$

Does this look correct? Thanks.

Last edited: Sep 23, 2006
2. Sep 24, 2006

### 0rthodontist

"#P" actually means |P|?

It looks correct except that C(8, 4) also counts the order of the partitions just as C(8, 2) * C(6, 8) * C(4, 2) does.

3. Sep 24, 2006

### mattmns

Yes, I think. I am using "#P" as the cardinality of P.

I think I see what you are saying with the order of the C(8,4) part. So I would need to divide by 2 for C(8,4).

Thanks.