Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
Do you know how to answer the question without the restriction that $x_1\le 2$? –  Brian M. Scott May 17 '13 at 22:47

5 Answers 5

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

share|improve this answer

$$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}$$

share|improve this answer
    
Great Link. I didn't know that. :) –  Babak S. May 19 '13 at 6:30

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^+}$$

share|improve this answer

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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.