# In how many ways can one or more of $101$ letters be posted in $101$ letter boxes?

In how many ways can one or more of $101$ letters be posted in $101$ letter boxes?

$\quad\quad\quad\quad\quad1)10100 \quad\quad 2) 101^{100} \quad\quad 3) 100^{101} \quad\quad 4) 101(101^{101} - 1)/100$

I am not sure where I am going wrong in interpreting this problem but the obvious thing that came to my mind is to assume letters and letter boxes all distinct and apply mutual inclusion-exclusion but from the answer options that doesn't seems not be the correct approach for this one.where exactly I am going wrong?

-
Does it not say whether letters and letter boxes are distinct? – TMM Sep 15 '11 at 19:55
My immediate interpretation of the problem would lead to $102^{101}-1$, since each of the letters can go in either one of the 101 letterboxes or not be posted at all, and then we just have to exclude the case where none of the letters were posted. But that's not even close to any of the options. – Henning Makholm Sep 15 '11 at 19:56
@Thijs Laarhoven:Nopes,nothing explicitly. – Quixotic Sep 15 '11 at 19:57
If the correct answer is indeed (4), then the question is just ill-formulated. – TMM Sep 15 '11 at 20:11
@Thijs Laarhoven:I don't know the answer yet,but I agree this is not much of good formulation. – Quixotic Sep 15 '11 at 20:17

Hint: It appears you are considering all the letters and all the boxes to be distinct, but you post letters in a given order. I can't get any of the answers to work any other way. Then one letter can be posted to one of $101$ boxes in $101$ ways, two letters can be posted in $101^2$ ways (each letter is independent of the other), and so on. Summing the geometric series gives what?
So with this reasoning, you cannot only post letter $2$. If you post letter $i$, then also all letters $1, \ldots, i-1$ must get posted. Strange. – TMM Sep 15 '11 at 20:08
Summing up the geometric series gives that option $4$,but in that model shouldn't $102^{101} - 1$ seems more correct,consistent to the model problem number of ways of putting some or more of $101$ distinct objects to $101$ distinct pockets?! – Quixotic Sep 15 '11 at 20:08
@Foo I like to think of this answer as the number of nonempty strings (in the computer science sense) of length at most $101$ over an alphabet of size $101$. So it's like you decide how many letters you want to post, buy so many from the post office, and then decide in what order you want to post them. I agree that this is strange. :-) – Srivatsan Sep 15 '11 at 20:13
@Sri I think your description is a good one. It that was intended, it should have been made clear. It's sort of like playing Jeopardy: the answer is $101(101^{101}-1)/100,$ what is the question? – Ross Millikan Sep 15 '11 at 20:35