In how many ways can 5 letters be posted in 4 letter boxes?

Question

The answer to the question according to my textbook is $4^5$ ways but can't it also be like $5$ ways of placing the letters in 1st letter box, $4$ ways of doing the same in 2nd letter box (because you already placed a letter in 1st letter box so there are $4$ letters left) and so on till the $4^{th}$ letter box. So total number of ways $5 \times 4 \times 3 \times 2=120$. Where did I go wrong ?

Answer 1

---

The simplest idea is what the textbook uses, and is not to consider the mailboxes one by one, but to consider the letters one by one. For the first letter, we have 4 choices on where to place it. The second one's placement is independent of the first, we also have 4 choices. And so on for all the 5 different letters yielding $4^5$.

Now, what if we wanted to go down your train of thought, and to consider how we fill the mailboxes? Well, the resulting solution is far more complicated, but still valid, as I will show you.

So, for the first mail box we have the choice of putting either 0,1,2,3,4,5 letters, and in what way. Then, we move on to the second mail and have to ask ourselves the same question about the remaining letters.

Let us generalize to $l$ letters and $m$ mailboxes. Let us denote $f(l,m)$ as the number of ways to place $l$ letters in $m$ mailboxes. First, we must choose how many, as well as which letters to place in the first mailbox. How is this done? We know that $l \choose k$ is the way to choose $k$ letters from $l$ letters. Once we choose $k$ letters to place in the mailbox, we then have to place the remaining $l-k$ letters in $m-1$ remaining mailboxes, which requires finding the value $f(l-k,m-1$).

Knowing we need to do this for all possible values of $k$ from $0$ to $l$, then we obtain the following recurrence:

$$f(l,m)= {\sum_{k=0}^l } {{l}\choose {k} }\times f(l-k,m-1)$$ Since this is a recursive formula, the we specify a base case $f(0,m)=1$, meaning there is 1 way to put no letters in any number of mailboxes, and $f(l,1)$ meaning if we have $l$ letters and one mail box left, we are forced to put them all in that box.

Solving this for $f(5,4)$ will give you the answer you wish. We are done. But, if you are curious, why is it different from the textbook answer?

Well, we can try to use generating function to prove this answer, however complicated, is indeed equal to the answer of the textbook.

Let $F_m(l)$ now denote $f(l,m)$. Our recurrence is

$$F_m(l)= {\sum_{k=0}^l } {{l}\choose {k} }\times F_{m-1}(l-k)$$

If we imagine $F_m$ and $F_{m-1}$ as sequences, we recognize that this expression above is the binomial convolution of the sequences $F_{m-1}$ and $1,1,1,1,1...$

So, we let $g_m(x)$ denote the exponential generating function of $F_m$, and we know that $e^x$ represents the $1's$ sequence. The above recurrence, when expressed in generating functions, is thus: $$g_m(x)=e^x \times g_{m-1}(x)$$

Solving that, we get $$g_m(x)=e^x \times e^x \times e^x... =e^{mx}$$

$e^{mx}$ is the generating function of the sequence $m^0, m^1,m^2.....$

So, the sequence represented by $g_m(x)=e^{mx}$ is $F_m(l)=m^l$. Hence $$f(l,m)=m^l$$ and the solution of $f(5,4)=4^5$

If you did not understand these complications; it's fine. Generally the recurrence is an accepted answer. The moral here is to be careful how you start counting, and to switch perspectives (letters or mailboxes) when complications arise. Also, always make sure that you cover ALL possible scenarios (different ways of putting the same number of letters in a box), and never count a scenario more than once.

Answer 2

In Rosen, Kenneth, et. al., Handbook of Discrete and Combinatorial Mathematics, section 2.3.3, you can read that if $k$ distinct objects are to be placed into $n$ bins, with arbitrarily many objects to each bin, the number of different ways to do this is $n^k$. Literally, "apply the rule of product to the number of possible bin choices for each" object. In our question, bins are the 4 letter boxes and the objects are the 5 envelopes, so, $4^5$ is a sound answer to the problem, according to its simple wording.

Answer 3

Simple formulation:

5 letters but 4 letter boxes

first letter, can be placed in any of the 4 boxes

second letter, can be placed in any of the 4 boxes

third letter, can be placed in any of the 4 boxes

fourth letter, can be placed in any of the 4 boxes

fifth letter, can be placed in any of the 4 boxes

4 options for each letter, 5 letters, $4^5$ possibilities.

EDIT

and no we can't do 5 for the first, etc. there are 32 choices for letter combinations that could be put there.