Doubt regarding two permutations and combinations problems

combinatoricsinclusion-exclusion

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!

Best Answer

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.

Related Question