Permutations and school timetable

If there are 6 periods in each working day of a school. In how many different ways can one arrange 5 subjects such that each subject is allowed at least one period? I tried this way- One of the six periods can be arranged in 5 ways and the remaining 5 periods in 5 factorial ways. Totally 600 ways

• Does each period need to be assigned a subject (in which case one subject will be assigned to two different periods, and the others to one period each)? – Barry Cipra Nov 18 '14 at 16:19
• Must the subject with two periods have a double (connected) period? Might the students be give a free period? – Henry Nov 18 '14 at 16:20
• Each period is to be assigned a subject and the periods need not be connected as raised by Mr. Henry – Achari S Ganesha Nov 18 '14 at 16:22

Lets think how we might pick this time table we can first assign a slot for each of our five subjects then finally pick the subject for the remaining slot.

Subject A has a choice of 6 slots
Subject B has a choice of 5 slots
Subject C has a choice of 4 slots
Subject D has a choice of 3 slots
Subject E has a choice of 2 slots

So far we have created $6! = 720$ distinct permutations and there is a choice of 5 subjects for the remaining slot creating $5 \cdot 720 = 3600$ possible permutations but we note that these are not all distinct because we could swap the repeated subject with itself in the other slot the total number of distinct timetables is therefore $\dfrac{3600}{2} = 1800.$

We assume that, sadly, there are no "spares." So some subject is taught twice, and the others once each.

Choose the subject that gets extra attention. This can be done in $5$ ways. For each such choice, the periods that this favoured subject gets can be chosen in $\binom{6}{2}$ ways, and for each choice the other subjects can be arranged in the remaining slots in $4!$ ways.

That gives a total of $5\cdot\binom{6}{2}\cdot 4!$ ways.

Remark: For visualization, I like to think as follos. Imagine that the subjects are A (Art), B (Botany), C, D, and E. A timetable can be thought of as a word of length $6$ over this alphabet, in which one letter (subject) occurs twice and the remaining letters occur once each. Our task is to count the number of such words. The letter that occurs twice can be chosen in $5$ ways. The $2$ positions it occupies in the word can be chosen in $\binom{6}{2}$ ways, and then the $4$ remaining letters can be put in the vacant positions in $4!$ ways.

There can be 5 cases as the mentioned case below S1,S2, S3, S4, S5, S1 which can be arranged in 6!/2! ways. Required no of ways will be 5× 6!/2! =1800