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

    0rthodontist

    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).

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