1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of Partitions of equal length (of a set)

  1. Sep 23, 2006 #1
    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.
    Last edited: Sep 23, 2006
  2. jcsd
  3. Sep 24, 2006 #2


    User Avatar
    Science Advisor

    "#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.
  4. Sep 24, 2006 #3
    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).

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook