[Math] 6 periods and 5 subjects

combinatorics

Question : There are 6 periods in each working day of a school. In how many ways can one organize 5 subjects such that each subject is allowed at least one period? Is the answer 1800 or 3600 ? I am confused.

Initially this appeared as a simple question. By goggling a bit, I am stuck with two answers. Different sites gives different answers and am unable to decide which is right.

Approach 1 (Source)

we have 5 sub and 6 periods so their arrangement is 6P5 and now we have 1 period which we can fill with any of the 5 subjects so 5C1
6P5*5C1=3600

Approach 2 (Source)

subjects can be arranged in 6 periods in 6P5 ways.
Remaining 1 period can be arranged in 5P1 ways.
Two subjects are alike in each of the arrangement. So we need to divide by 2! to avoid overcounting.
Total number of arrangements = (6P5 x 5P1)/2! = 1800

Alternatively this can be derived using the following approach.
5 subjects can be selected in 5C5 ways.
Remaining 1 subject can be selected in 5C1 ways.
These 6 subjects can be arranged themselves in 6! ways.
Since two subjects are same, we need to divide by 2!
Total number of arrangements = (5C5 × 5C1 × 6!)/2! = 1800

Is any of these approach is right or is the answer different?

Best Answer

Approach 1 is incorrect. It arranges any five of the courses into one period each, then assigns the left over course to some period. It double counts each arrangement by having each of the two courses taught at the same time included in the original five. So the arrangement $12,3,4,5,6$ is counted as $1,3,4,5,6$ plus $2$ in first period and as $2,3,4,5,6$ plus $1$ in first period. Approach 2 is the same, but acknowledges the double counting in the division by $2!$

I cannot follow the argument in the paragraph starting "Alternatively"

Related Question