- #1
mattmns
- 1,128
- 6
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 [itex]\binom{8}{4}[/itex] 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: [tex]\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}[/tex].
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: [tex]1+1+\binom{8}{4}+\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}[/tex]
Does this look correct? Thanks.
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 [itex]\binom{8}{4}[/itex] 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: [tex]\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}[/tex].
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: [tex]1+1+\binom{8}{4}+\frac{\binom{8}{2}\binom{6}{2}\binom{4}{2}\binom{2}{2}}{4!}[/tex]
Does this look correct? Thanks.
Last edited: