How to distribute 10 distinct envelopes into 3 (identical) mailboxes? As in the title, I would like to distribute 10 distinct envelopes into 3 mailboxes. Let us also assume that some mailboxes can remain empty.
If they were identical envelopes, I know that we can use the stars and bars method, which would let us arrive at the answer of $\binom {12} {2}$.
However, here is where a friend and I started an extended discussion as we tweaked the question slightly.
What if, the envelopes were distinct and not identical?

My logic
Similar to the stars and bars method, 3 mailboxes is equivalent to 2 bars, so the question is equivalent to arranging 12 objects (10 distinct, 2 identical) in a line. Thus, my answer is $\frac {12!} {2!}$.
My friend's logic
My friend says that each envelope has 3 mailboxes to go into and since we have 10 envelopes, so the answer should be $3^{10}$.

Clearly, both of our answers are very different and I would obviously like to know who is correct and more importantly, why. We are currently at a standstill because neither of us can find the flaw in the other's logic. Any intuitive explanations will be greatly appreciated!
 A: Stars and bars works fine when you have to distribute 10 identical envelopes into 3 distinct mailboxes, but not when the envelopes are distinct. Your argument gives the right answer ($12!/2!$) to the following question:

How many ways are there to arrange 10 distinct envelopes and two identical bars in a line?

If you regard the two bars as the dividers between three mailboxes, then under your approach the envelopes to the left of the first bar are sent to the first mailbox, the envelopes between the first and second bar are sent to the second mailbox, and the envelopes to the right of the second bar are sent to the third mailbox. The flaw in your approach is that you are overcounting what are equivalent assignments: once you've placed the bars, rearranging the items between the bars will lead to the same distribution of envelopes into the three mailboxes.
For grins, let's modify your reasoning to arrive at the correct answer ($3^{10}$):
For each of the possible ways to place the two identical bars, you are currently counting $10!$ permutations. This leads to a total of
${12\choose 2}10!$, which equals $12!/2!$. To repair this, replace $10!$ with a number that recognizes the overcounting going on. Specifically, suppose you place the bars at positions $a<b$. Then there are $a-1$, $b-1-a$, and $12-b$ envelopes going into the respective mailboxes. To fix the overcount, divide $10!$ by the number of ways to permute the envelopes between the bars. This leads to the total
$$
\sum_{1\le a<b\le 12}\frac{10!}{(a-1)!(b-1-a)!(12-b)!},
$$
which equals $3^{10}$, by tedious calculation, or by the following
Claim:
$$\sum_{1\le a<b\le N+2}\frac{N!}{(a-1)!(b-1-a)!(N+2-b)!}=3^N.$$
Proof:
Write the sum in the form
$$\sum_{a=1}^{N+1}\frac {N!}{(a-1)!}\sum_{b=a+1}^{N+2}\frac1{(b-1-a)!(N+2-b)!}
\stackrel{(*)}=\sum_{a=1}^{N+1}\frac {N!}{(a-1)!}\sum_{c=0}^{N+1-a}\frac1{c!(N+1-a-c)!}
$$
where in ($*$) we apply the change of index $c:=b-a-1$. The inner sum on the RHS equals $2^{N+1-a}/(N+1-a)!$, by the identity
$${k\choose 0}+{k\choose 1}+\cdots+{k\choose k}=2^k,$$ which can be proved using the binomial theorem. To finish the proof, use the binomial theorem again to find the identity
$$
3^N=(1+2)^N=\sum_{i=0}^N{N\choose i}1^i2^{N-i}=\sum_{a=1}^{N+1}{N\choose a-1}2^{N+1-a}.$$
