In the lecture notes of one of my previous classes, it was used that if we have an equation of the form $$\tag{1} x_1+x_2+\dots+x_n=m $$ then the total number of solutions, when each $x_i$ is a non-negative integer, can be written $$\tag{2} C(m+n-1, m)=\frac{(m+n-1) !}{(n-1) ! \cdot m !} $$ so that, for example, $$\tag{3} x_1+x_2+x_3=14,\qquad x_{1,2,3}\in\mathbb{N}\cup\{0\} $$ has $C(14+3-1,14)=120$ solutions. However, what if each $x_i$ is restricted to a different subset of the positive integers? For example, if we in eq. $(3)$ need $x_1>1$, $x_2>0 $, and $x_3>3$, is there a formula to determine the total number of solutions?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ You have 14 identical cookies. How many ways are there to distribute all the cookies to Alice, Bob, and Carol, so that Alice receives more than 1 cookie, Bob receives more than 0 cookies, and Carol receives more than 3 cookies? One you give everyone their required number of cookies, the remaining cookies can be distributed using the usual $x_1+x_2+x_3=m$ scheme, where all variables are nonnegative integers, and $m$ is the number of cookies remaining. $\endgroup$– Mike EarnestCommented Feb 24, 2022 at 19:38
-
3$\begingroup$ Ah, yes. So I just get a new equation $\tilde{x_1}+\tilde{x_2}+\tilde{x_3}=7$ and can use eq. $(2)$. $\endgroup$– HydrogenCommented Feb 24, 2022 at 19:57
-
$\begingroup$ More generally, there are methods using generating functions, and methods using inclusion-exclusion. $\endgroup$– Gerry MyersonCommented Feb 25, 2022 at 6:15
Add a comment
|