2
$\begingroup$

Here are two questions from permutations and combinations:

  1. There are 10 identical blankets. These are to be distributed among 4 (distinct) beggars. In how many ways can you do this so that each beggar has at least 1 blanket.

  2. There are 10 (distinct) tourists and 4 (distinct) hotels. In how many ways can the tourists stay in the hotel so that no hotel is without tourists?

My approach:

  1. Let the number of blankets received by each beggar be $x_1, x_2, x_3, x_4$ respectively. We will have $x_1+x_2+x_3+x_4=10$, with the constraint that each of $x_1, x_2, x_3, x_4$ are $\geq$ 1.

Consider the equation $x_1 + x_2 + x_3 + ... x_n = k$, where $\min(x_1)\leq x_1\leq \max(x_1)$, $\min(x_2)\leq x_2\leq \max(x_2)$, ... $\min(x_n)\leq x_n\leq \max(x_n)$.

We consider the expansion $$(x^{\min(x_1)} + x^{\min(x_1)+1} + ... x^{\max(x_1)} )\cdot(x^{\min(x_2)} + x^{\min(x_2)+1} + ... x^{\max(x_2)} )...(x^{\min(x_n)} + x^{\min(x_n)+1} + ... x^{\max(x_n)} )$$ The coefficient of $x^k$ in this expansion will be the number of integral solutions to our equation.

The reason behind this is as follows:

When we open up the entire expansion, each term we get is obtained by raising x to the power of sum of certain distinct combination of values of $x_1, x_2, x_3 ... x_n$. When the sum of these unique combinations adds up to k, we get a solution to our equation. Since the coefficient corresponds to the number of ways in which these combinations can add up to k, the coefficient of $x^k$ is our answer.

Let us now come back to our question. We have $x_1 + x_2 + x_3 + x_4 = 10$. Let us calculate the maximum number of blankets each person can get; for this, rest of the 3 people need to receive only one blanket, so the upper bound on the number of blankets a person can receive is 10-3=7. So we consider the coefficient of $x^10$ in $(x+ x^2 + x^3 +... x^7 ) ^4$

Notice, that we can introduce terms of power greater than 7 as well, like we can consider the expansion of $(x + x^2 + x^3 + x^4 ... + x^7 + x^8 + ... ) ^4$

This won't make a difference because terms of power greater than 7, cannot in any way add with powers from other brackets to bring about the power of 10. But assume, if $x<1$ (it doesn't really matter what x is, because we just need to find the coefficient of a certain power of x). This is an infinite geometric series which converges to $x^4 (1-x)^{-4}$

So we can find the coefficient of $x^{10}$ in this term, or just the coefficient of $x^6$ in $(1-x)^{-4}$ , which by binomial theorem results is $^9C_6$ (used result: coefficient of $x^r$ in $(1-x)^{-n}$ (n and r are positive integers) is $^{(n+r-1)}C_r$.

So we get $$ number \ of \ ways = \ ^9C_6 \ = \ 84$$

  1. I am using the inclusion-exclusion principle. We first calculate the total number of ways in which 10 distinct tourists can be accommodated in 4 distinct hotels, which is 4^10. But this includes cases of 1, 2, or 3 hotels being vacant, which we don't want. So we first subtract the number of cases in which 1 hotel is vacant, which is $^4C_1\cdot(3^{10})$, which basically means that choose any one of the 4 hotels to be excluded, then accommodate the tourists in the remaining 3.

Notice, however, that this subtraction also includes the cases in which two hotels are vacant, and actually two copies of each such case (say you chose to exclude hotel A, and accommodated rest of the tourists in C and D in a particular way, but your subtraction also includes the case in which you choose to exclude hotel B, and accommodate the tourists in hotels C and D in that same certain way).

So since we need to subtract cases of 2 hotels being vacant only once, and in reality we are subtracting twice, we add the term of leaving two hotels vacant, which is $^4C_2\cdot (2^{10} )$ to our answer.

Again, notice, that when we subtracted the cases where we had to accommodate the tourists in 3 hotels, we also included the case of accommodating the tourists in just one hotel, and three copies of it (consider choosing to exclude A, B, and C in different scenarios but just fitting up all tourists in D).
Likewise, when we added the term corresponding to accommodation of tourists in just 2 hotels, we again added three copies of the case of accommodating tourists in just one hotel (imagine excluding AB, BC, CA in different scenarios and fitting up tourists in just D). So effectively, we didn't deal with the case of accommodating tourists in just 1 hotel, so we subtract that at the end as the term $^4C_1\cdot(1^{10} )$.

So our final answer becomes $$ number \ of \ ways \ = \ 4^{10} - (^4C_3)\cdot3^{10} + (^4C_2)\cdot2^{10} - (^4C_1)\cdot1^{10} \ = \ 818520$$

Am I approaching this the right way? Some confirmation or guidance would be great!

$\endgroup$
  • $\begingroup$ Please see math.meta.stackexchange.com/questions/5020 $\endgroup$ – Lord Shark the Unknown Oct 29 '18 at 16:57
  • $\begingroup$ Welcome to MSE. It's great that you made such a detailed post describing what you have done, but it would be a lot easier to read if you used MathJax to format it. To a large extent, this is just enclosing formulas in $ signs. You can get subscripts with an underscore: $x_1$ formats as $x_1.$ Also, use $\max$ to get $\max$ instead of $max$ $\endgroup$ – saulspatz Oct 29 '18 at 17:01
  • $\begingroup$ Hi @saulspatz, I have made the edits now, I hope it looks cleaner now. Thank you for pointing out, and I shall keep in mind to write in MathJax henceforth. $\endgroup$ – Suyash Kumar Oct 29 '18 at 17:34
0
$\begingroup$

A shortcut can be to directly find the non negative integral solutions of this equation $x_1+x_2+x_3+x_4=6$ . Basis is that you give each of the persons one blanket and then your problem remains same as to find the non negative integral solutions of the above equation . I hope you know the formula. Your method , although long, is absolutely correct.

$\endgroup$
  • $\begingroup$ Roy, Hi! Thank you for your opinion. I did know that method, where we effectively substitute $t_1 = x_1 - 1$, and so on, so that the bounds we effectively get are $ t_1, t_2, t_3, t_4 \geq 0 $ where $t_1, t_2, t_3, t_4$ satisfy the equation $t_1 + t_2 + t_3 + t_4 = 6$, and then we can sort of directly use the formula. Also, I think, if we had some upper bound on how many blankets each beggar can have, you cannot just add terms to that expansion to make it an infinite series, it would result in extra solutions. Also, is the solution to the second problem correct? Thank you so much! $\endgroup$ – Suyash Kumar Oct 29 '18 at 18:37
  • $\begingroup$ Hi Suyash! If we had some upper bound then we definitely have to use the multinomial theorem as you have stated. Your second problem's approach seems correct to me. $\endgroup$ – Akash Roy Oct 31 '18 at 2:46
  • $\begingroup$ Thanks @Akash Roy! $\endgroup$ – Suyash Kumar Oct 31 '18 at 3:04
  • $\begingroup$ Plesse upvote my answer Suyash $\endgroup$ – Akash Roy Nov 22 '18 at 5:54
  • $\begingroup$ They won't let me @Akash Roy, seems due to less points. :/ $\endgroup$ – Suyash Kumar Nov 22 '18 at 6:00

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.