Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to solve some problems based on this formula,but am facing some issues in determine whether or not consider ordering as important.

For Example:

In how many ways 15 different books can be divided five heaps of equal number of books ?

So here according to the answer the ordering of groups is not considered important,hence the answer given is $\frac {15!} {5!(3!)^5}$

and the same thing goes for this one :

In how many ways 3 piles can be formed out of 18 different books, which will be $\frac {18!} {3!(6!)^3}$

But for the following problem "There are three copies, each of four different books. In how many ways they can be arranged on a self ?"

This this is similar to divide 12 books into 4 sets of 3 books each, the answer given here considers the ordering important,why this change ?

Why in the first two the ordering not and on the third one it is important ? I guess (if the solution is correct) it is something related to copies but am not confident enough.

A good example of a problem where ordering should be considered important is say "In how many ways can 18 different books be divided equally among three students ?"

The solution should be $\frac {18!} {(6!)^3}$

But I am not much confident while in these problems so I will be grateful if somebody helps me to understand when to consider ordering important and when not to.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

There are different notions of "ordered" and "unordered" that can arise in relation to set partitions.

  • An unordered set of unordered sets,
  • An unordered set of ordered sets,
  • An ordered set of unordered sets,
  • An ordered set of ordered sets,

all of which are counted differently.

In how many ways 15 different books can be divided five heaps of equal number of books ?

An example of what is counted here is:

{{1,3,8},{2,14,15},{4,5,7},{6,12,13},{9,10,11}}

is an unordered set of unordered sets. This is what the answer to the first question suggests it's counting. [Although, the question itself does not resolve the question of order within the heaps.]

There are three copies, each of four different books. In how many ways they can be arranged on a self ?

An example of what is counted here is:

1 2 3 1 4 1 3 3 2 2 4 4

which we can interpret as a set partition counting problem -- place the i-th element in the s(i)-th set, where s(i) denotes the element in the i-th position. So the above example gives rise to:

({1,4,6},{2,9,10},{3,7,8},{5,11,12})

which is an ordered set of unordered sets.


To highlight the difference between these two situations, for the first question:

{{1,3,8},{2,14,15},{4,5,7},{6,12,13},{9,10,11}}
{{2,14,15},{1,3,8},{4,5,7},{6,12,13},{9,10,11}}

should be considered the same (this is the same as swapping the positions of the first two heaps), whereas in the second question:

({1,4,6},{2,9,10},{3,7,8},{5,11,12})
({2,9,10},{1,4,6},{3,7,8},{5,11,12})

should be considered different (this is the same as swapping all the books labelled 1 with all the books labelled 2).

share|improve this answer

In the first one, the problem only states that you need to group them, as in, let's say, put the books in a bag, so there could be no order.

The second one is very similar. It would be different if it had stated it wanted a stack of books, which would have been something with an order, where you can say: book A is in the bottom, book B is right on top of A, etc.

The third, however, asks for an arrangement of books, which would be like putting them all on a shelf. Since you can't distinguish between 2 copies of the same book, swapping them around won't change the order of the books, so that is why you need to divide by the number of copies of the same book, so you don't count the very same arrangement twice.

Overall, I think that in these kind of problems, grouping stuff together means that order is not important (picture putting books in several big bags) and arranging things implies that there is order (imagine putting books in a shelf).

In your last question, ordering is not important, as you are not asking in which order the books can be given, but which different groups of books can be given to each student. Say we give books A B C D E F to student 1. He would end up with the same books if we had given him B C A E F D, so order is not important.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.