1
$\begingroup$

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 ?

$\endgroup$
  • 4
    $\begingroup$ There are 5 ways of placing the letters in the first letter box ONLY if we assume that each letter box must have at most 1 letter. In the solution provided by the book, each letterbox may have more than 1 letter. $\endgroup$ – Confused Soul Jan 25 at 15:25
  • $\begingroup$ You can place 1 letter,2 letters,3letters,4 letters or all 5 letters in the first box. So there are 5 ways. Can you tell where am I going wrong ? $\endgroup$ – Ali Jan 25 at 15:34
  • $\begingroup$ Suppose you want to place 1 letter in the first box. There are 5 different ways of choosing that letter. If you want to place 2 letters in the box, there are 10 ways of doing so... For each number of letters you want to place in the first box, we can choose different letters, so we do not have only 5 ways of doing so. Furthermore, for the next letterbox, there might be 4,3,2,1 or even 5 letters left if we do not want to put any in box 1. $\endgroup$ – Confused Soul Jan 25 at 15:38
  • $\begingroup$ Ohh... okay now I understand. Can you tell how to proceed in this way to get the answer or will it be too lengthy ? $\endgroup$ – Ali Jan 25 at 15:45
  • 1
    $\begingroup$ 1. Can the letters be repeated? Or they can be used only only time? 2. Can each of the letter box hold only one letter? Or each of them can hold multiple letters? $\endgroup$ – Ramiro Jan 25 at 20:09
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OK. But see this question " given 7 flags of different colours how many different signals can be generated if a signal requires the use of two flags one below the other." Here the answer is 42 which I understand but according to the same logic as your answer- 1st flag can be placed in 2 ways the 2nd flag also in 2 ways and so on so total number of ways 2^7. What did I do wrong ? $\endgroup$ – Ali Jan 26 at 15:16
  • $\begingroup$ 7 for the first flag, 6 for the next, order matters so we don't divide by 2. if you were allowed to have multiple flags in the same position there would be $2^7$ possibilities. $\endgroup$ – user645636 Jan 26 at 15:22
  • $\begingroup$ answers depend on context, is order important then factorials get involved somewhere, are repetition allowed, if not then there's always changing number of items to choose from. Another interpretation of your question could be just 1 letter per letter box, but then it gets 120. if only number of letters used and letter boxes match then you get 1280. etc. slight changes change everything. $\endgroup$ – user645636 Jan 26 at 15:41
  • 1
    $\begingroup$ @Ali I think it's time you take a moment to study the logic of how we calculate these combinations, perhaps using some visual or graphical aid, before returning to the problems $\endgroup$ – Confused Soul Jan 27 at 12:57
  • 1
    $\begingroup$ math.stackexchange.com/questions/3190591/… for some help. $\endgroup$ – user645636 Jan 27 at 13:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems like extreme overkill -- surely we can just say there are $4$ choices of box for the first letter, $4$ choice for the second letter, and so on? $\endgroup$ – Gregory J. Puleo Jan 25 at 16:42
  • 1
    $\begingroup$ Yes, perhaps I should clarify that the question asker wanted to know whether his line of thought could be used to reach an answer. I think I'll clarify in the answer and provide the simpler method too $\endgroup$ – Confused Soul Jan 25 at 16:43
  • $\begingroup$ it depends on if you take 0,1,2,3,4,5 letters in the first box, there are 32 ways to do that... $\endgroup$ – user645636 Jan 25 at 20:01
  • $\begingroup$ Yes, but then we don't know how many are in the others; we should consider each number of letters in box 1 independently, rather than doing the 32 in one go. $\endgroup$ – Confused Soul Jan 25 at 22:40
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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