A mailman has 7 letters that are all the same. He can put them in three mailboxes in any order he wants. How many ways are there to put the letters in the mailboxes?
Something different about this was that the letters were all the same. I could not do the usual "for each letter I have 3 places to put it, and I have seven letters, so the answer must be $3^7$.
So I started to solve this, using a pattern. I asked myself, what if he had 1 letter, then 2 letters, then 3 letters, and so on. The result was this: (o=letter, x=empty)
# of letters | options
0 | 1 --> [x, x, x]
1 | 3 --> [o, x, x], [x, o, x], [x, x, o]
2 | 6 --> [oo, x, x], [x, oo, x], [x, x, oo]
[o, o, x], [o, x, o], [x, o, o]
3 | 10 --> [ooo, x, x], [x, ooo, x], [x, x, ooo]
[oo, o, x], [oo, x, o], [o, oo, x], [x, oo, o]
[o, x, oo], [x, o, oo], [o, o, o]
4 | 15
5 | 21
etc.
This is an easily recognizable pattern: the triangular numbers where you successively add 1, then 2, then 3, then 4: 0 --> 0+1 = 1 --> 1+2 = 3 --> 3+3 = 6 --> 6+4 = 10 --> 10+5 = 15, etc.
So then the answer to the mailman problem is that he can arrange his 7 letters in 36 ways. My question is how does one solve this using mathematical methods (i.e. not using a pattern chart)?
To clarify by 'mathematical methods', I refer to logical deduction and analysis. There must be an explanation behind the pattern, somehow!
This is classic stars and bars.
Take the seven letters and make them stars:
$$*******$$
Now, use two bars to separate the stars into three boxes. For example:
$$***|*|***$$
means that the first box gets three letters, the second box gets one, and the third box gets three. Another example:
$$|*******|$$
means that the second box gets all seven letters.
Ok, so how many different distributions are there? It is exactly the number of ways we can arrange these seven stars and two bars, i.e. The number of pairs of positions out of nine possible positions for the bars to take, which is
$${9 \choose 2} = 36$$