2
$\begingroup$

I'm learning about combinatorics and wanted to see if I understand when to apply what methods when it comes to counting the number of ways to distribute x items. There are a lot of concepts I've learned, including permutation, combination, generating functions, inclusion-exclusion etc. and I sometimes get confused as to when they are applicable to a problem.

So, for example, I have 10 candy bars and I want to distribute them to 4 kids. Here are some variants...

1) The candy bars are identical, all 10 of them must be given out, and each kid gets 0 or more.

2) The candy bars are identical, it's allowed to give out fewer than 10 candies, and each kid gets 1 or more.

3) The candy bars are distinct, all of them must be given out, and each kid gets 1 or more.

4) The candy bars are distinct, exactly 4 of them will be given out, and each kid gets exactly 1.

5) The candy bars are distinct; this time, instead of giving them out to the kids, we'll simply put 4 of them inside a single basket.

For (1), we just have to set up an integer addition, right? Such as: $x_1+x_2+x_3+x_4=10,x_{all} \geq 0$

For (2), integer addition inequality, and each variable must be greater than 0: $x_1+x_2+x_3+x_4 \leq 10,x_{all} > 0$

BTW, Could we also solve (1) and (2) using regular generating functions?

For (3), do we use inclusion-exclusion here? Or generating functions or both? I guess if there were no constraint that each kid must 1 or more, then the answer would be just $14^{30}$? But with the constraint, I suppose we might set up an exponential generating function like so: $$(e^x-1)^4$$ and solve for the coefficient of $x^{10}/10!$ Is that right?

For (4) and (5), not sure which one is which...I think (5) is a combination such as C(10,4)? Then what is (4)?

I realize these are a lot of questions for a single post, but since I feel that all of them are related, you hopefully won't mind too much. Thanks for your help.

$\endgroup$
  • $\begingroup$ For 4), $(10)(9)(8)(7)$; for 2) there is a useful little trick, introducing an extra person; for 3) I would use Inclusion/Exclusion, but generating functions also work. $\endgroup$ – André Nicolas Apr 27 '16 at 21:35
1
$\begingroup$

The candy bars are identical, all $10$ of them must be given out, and each kid gets $0$ or more.

You are correct that the number of ways of distributing the candy bars to four children is the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 = 10$$ in the non-negative integers.

The candy bars are identical, it's allowed to give out fewer than $10$ candy bars, and each kid gets $1$ or more.

You are correct that the number of ways of distributing the candy bars is the number of solutions of the inequality $$x_1 + x_2 + x_3 + x_4 \leq 10 \tag{1}$$ in the positive integers.

If we let $x_5 = 10 - (x_1 + x_2 + x_3 + x_4)$, which could represent the number of candy bars the person distributing them keeps for himself, then inequality 1 can be transformed into the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 10 \tag{2}$$ where $x_1, x_2, x_3, x_4 \geq 1$ and $x_5 = 0$.

If we let $y_k = x_k - 1$, $1 \leq k \leq 4$, and let $y_5 = x_5$, then we can transform equation 2 into the equation
$$y_1 + y_2 + y_3 + y_4 + y_5 = 6 \tag{3}$$ Equation 3 is an equation in the non-negative integers.

The candy bars are distinct, all of them must be given out, and each kid gets $1$ or more.

There are four choices of recipient for each of the ten candy bars. Hence, the number of ways we could distribute the candy bars is $4^{10}$. However, this counts distributions in which fewer than four children receive a candy bar. To eliminate those cases, use the Inclusion-Exclusion Principle. The number of ways to exclude $k$ children from receiving a candy bar is $\binom{4}{k}$. The number of ways that to distribute the candy bars to the remaining children is $(4 - k)^{10}$. Hence, the number of ways of distributing the candy bars so that each child receives at least one is

$$4^{10} - \binom{4}{1}3^{10} + \binom{4}{2}2^{10} - \binom{4}{3}1^{10}$$

Next problem:

The candy bars are distinct, exactly $4$ of them will be given out, and each kid gets exactly $1$.

We select four of the ten candy bars. Next we line up the four children in some order, such as by age. Now we distribute the four selected candy bars. We have four options to give to the first child in line, after which three options remain for the second child in line, and so forth.

$$\binom{10}{4} \cdot 4!$$

Finally,

The candy bars are distinct; this time, instead of giving them out to the kids, we'll simply put $4$ of them inside a single basket.

You are correct that this can be done in $\binom{10}{4}$ ways since we are simply selecting four of the ten candy bars to place in the basket.

$\endgroup$
1
$\begingroup$

Label the kids, say 1, 2, 3 and 4.

(3) I would use inclusion / exclusion.

(4) 10 ways to pick 1 out of 10 candies for kid 1, 9 ways to pick 1 out of the rest 9 for kid 2, etc. The result would be $10 \times 9 \times 8 \times 7$

(5) The number of ways to choose 4 out of 10 items is $$\binom{10}{4} = \frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1}$$

P.S.

For (3) if there is no constraint that each kid must get at least 1 candy, the result would be $4^{10}$, because each candy can be given to any of the 4 kids.

$\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.