Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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?

share|cite|improve this answer
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: So if I send one letter then I only send a letter to Ross; if I send two letters, then I send letters to Ross and Fool; and only if I send three letters, then I send letters to Ross, Fool and Srivatsan... But I never only send a letter to Srivatsan. Makes sense :P – TMM Sep 15 '11 at 20:16
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.