Expert: Daniel Mazur - 6/3/2009

Question
Hi Daniel

I'm back again with another math doubt from permutations.

The question is :

"There are six periods every day in a school. In how many ways can we arrange 5 subjects such that each subject is allowed at least one period?"

Now the answer is ^6P_5 x 5 or P(6,5) x 5 (hope you understand the notation).

How i interpret this answer is this:

Suppose we represent the five subjects by five empty square boxes and we can fill these boxes with the no. of period that that particular subject takes.

So the first box can be filled in 6 ways since there are 6 periods, and the second in 5 ways since one out of the 6 has been taken by the first subject or the first box and there are 5 remaining so on and so forth.
The fifth and the last box that stands for the fifth subject can be filled in 2 ways.

So now the total number of ways in which 6 periods can be arranged for 5 subjects is simply ^6P_5 which equals 6 x 5 x 4 x 3 x 2 x 1.
Now there is still one more period left and it can be filled by any of the five subjects. So it can be filled in 5 ways.
So now the total number of ways are ^6P_5 x 5 which is also the answer which has been given in the book.

Now my question is this:

What if we make six empty boxes instead of five so that they represent the six periods now.
Now the first box can be filled in 5 ways since any subject out of the five can take that period. And similarly we can fill 4 more period boxes so that 5 boxes have been filled.
There's one sixth box left as there were only five subjects and the boxes were six. But now this sixth box can be filled with any of the five subjects as any of the subjects can take that period.(a subject can take more than one period as it is given in the question that a subject should get "at least one period")

So now our total number of ways becomes (5 x 4 x 3 x 2 x 1) x 5. This is nothing but 5! X 5.
But this answer doesn't match with the previous one and i know I'm conceptually wrong somewhere in this second method of mine.
there are a lot of such questions, but in all of them we always arrange the bigger number of things into the smaller number of things. for Eg.. in the above question, in the first answer, which is also the correct one, we arranged 6 things taking five at a time.

What is wrong with the second method? I know what i have done in the second method is that I've calculated the number of permutations of 5 objects taking 6 at a time which obviously doesn't make much sense when put in the formula or otherwise but i just can't  understand what is wrong with the way i thought about the second method.  

Thanks,
Shikhin

Answer
Hello Shikhin,

without any maths I can tell you that the second method is wrong, because the problem statement does NOT say that the excessive period must always be the last one in the row. Suppose that we leave the sixth period free (a student will like that best). That one free period can occur at the beginning of the day, at the end or anywhere in the middle. This gives you an extra multiplicative factor (6?), which needs to be applied to your second method.

Cheers,
Daniel