4
$\begingroup$

How would I find the number of non negative integer solutions to this problem? $$x_1 + x_2 + x_3 + x_4 = 12$$ if $0 \leq x_1 \leq 2$.

$\endgroup$
  • 2
    $\begingroup$ Do you know how to answer the question without the restriction that $x_1\le 2$? $\endgroup$ – Brian M. Scott May 17 '13 at 22:47
6
$\begingroup$

Without the restriction on $x_1$ this is a standard stars-and-bars question and can be answered using the formula (or the reasoning) at the link. However, the resulting count will include the unwanted solutions that have $x_1>2$. You can finish the problem by counting these and subtracting that number from the number of unrestricted solutions.

To count the solutions with $x_1>2$, let $y_1=x_1-3$, $y_2=x_2$, $y_3=x_3$, and $y_4=x_4$. Then each solution to $$x_1+x_2+x_3+x_4=12\tag{1}$$ with $x_1>2$ corresponds to a solution to $$y_1+y_2+y_3+y_4=9\tag{2}$$ with no upper limit on any of the variables, and vice versa. (In all cases I’m assuming that the solutions must be in non-negative integers.) Thus, you need only get the number of unrestricted solutions to $(1)$ and subtract from it the number of unrestricted solutions to $(2)$, and you’ll have the number of solutions to $(1)$ with $x_1\le 2$.

$\endgroup$
2
$\begingroup$

$$x_1 + x_2 + x_3 + x_4 = 12, 0 \leq x_1 \leq 2$$ According to http://oeis.org/wiki/User:Adi_Dani_/Restricted_compositions_of_natural_numbers there is derived formula $${\binom{m}{k}}_{s}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+k-si-1}{m-1}\,$$ for number of solutions of $$x_0+x_1 + x_2 +...+ x_{m-1} =k,0\leq x_i\leq s-1$$

in our case $k=12,s=3,m=4$ $${\binom{4}{12}}_{3}=\sum_{i=0}^{4}(-1)^{i}\binom{4}{i}\binom{15-3i}{3}=$$ $$=\binom{4}{0}\binom{15}{3}-\binom{4}{1}\binom{12}{3}+\binom{4}{2}\binom{9}{3}-\binom{4}{3}\binom{6}{3}+\binom{4}{4}\binom{3}{3}=$$

$$=\binom{15}{3}-4\binom{12}{3}+6\binom{9}{3}-4\binom{6}{3}+\binom{3}{3}$$

$\endgroup$
  • 1
    $\begingroup$ Great Link. I didn't know that. :) $\endgroup$ – mrs May 19 '13 at 6:30
0
$\begingroup$

Hint: Consider the following $3$ cases.

$x_1=0$, $x_1=1$ and $x_1=2$.

Now you have reduced the problem to a standard distribution question where $$x_2+x_3+x_4=12,11,10 \; \; \forall x_2,x_3,x_4 \in \mathbb{N_0^+}$$

$\endgroup$
0
$\begingroup$

This can be boiled down to the stars and bars problem: http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29

Let us consider just the case where $x_1 = 0$ Then $x_2 + x_3 + x_4 = 12$ Imagine there are 12 "stars" on the table. We need all the possible ways of putting 2 bars within these stars. From the wiki article, this is equal to: $\binom{2+12-1}{12}$

Similarly, do this work for $x_1 = 1$ and $x_1 = 2$

$\endgroup$
0
$\begingroup$

The number of solutions $\def\N{\mathbf N}(x_1,x_2,x_3,x_4)\in\N^4$ to $x_1+x_2+x_3+x_4=k$ is the coefficient of $X^k$ in the power series expansion of $\frac1{(1-X)^4}$, which coefficient is $(-1)^k\binom{-4}k=\binom{k+3}k$, which is also $\binom{k+3}3$ if $k\geq0$. If you want to limit one variable to being${}<m$ (with $m>0$), just observe that the number of solutions of the problem which have $x_1\geq m$ equals the number of (unrestricted) solutions to $x_1+x_2+x_3+x_4=k-m$. You need to subtract these, so you get as number of solutions for the restricted problem $$ \binom{k+3}k - \binom{k-m+3}{k-m} \qquad\text{which is also $\dbinom{k+3}3-\dbinom{k-m+3}3$ if $m\leq k$.} $$ Now plug in $k=12$ and $m=3$ to obtain $\binom{15}3-\binom{12}3=235$.

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