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.

$x_1 + x_2 + x_3 + x_4 + x_5 = 20$ if $0\leq x_i\leq 5$

I know how to get the total amount without restrictions. $24C4 = 10 626$

But I'm not sure how I would do it if there's a restriction like this. Could someone explain how in a simple manner?

share|improve this question
2  
Please rewrite the question. As it stands, it's completely incomprehensible. –  nbubis Jan 23 '13 at 14:27
    
$x1+x2+x3+x4+x5$ is not an equation, so it does not have solutions. –  Thomas Andrews Jan 23 '13 at 14:29
    
I think he ask 'the number of pairs $(x_1,x_2,x_3,x_4,x_5)$ satisfies that $x_i\ge 0$ for $i=1,2,\cdots,5$, $x_1+x_2+\cdots+x_5\le 5$'. –  tetori Jan 23 '13 at 14:32
    
Number of solutions of what? perhaps you mean "quantity of natural numbers that can be written as $x_1+\cdots+x_5$, with each $x_i\in\mathbb N$ and $x_i\leq 5"$. Your writing is awful. –  Matemáticos Chibchas Jan 23 '13 at 14:33
    
Doug: Your number is the coefficient of $x^{20}$ in the expansion of $(1+x+x^2+x^3+x^4+x^5)^5$. That is, 126. –  coffeemath Jan 23 '13 at 14:52

2 Answers 2

up vote 2 down vote accepted

A simpler argument probably exists, but here is my idea: For $1\leq i\leq 5$ let $A_i=\{(x_1,\dots,x_5)\in\mathbb N^5: x_1+\cdots+x_5=20, x_i>5\}$. You want to calculate $c=|A_1\cup\cdots\cup A_5|$, which is the number of undesired solutions. From this you get your answer, namely $10626-c$.

In order to calculate $c$ we apply inclusion-exclusion principle: consider the number of solutions $(x_1,\dots,x_5)\in\mathbb N^5$ of $x_1+\cdots+x_5=20$ with $x_{i_1},\dots,x_{i_k}>5$, where $i_1,\dots, i_k$ are fixed and satisfy $1\leq i_1<i_2<\cdots<i_k\leq 5$ (of course we must have $1\leq k\leq 5$). In other words, we are seeking for $|A_{i_1}\cap\cdots\cap A_{i_k}|$. Note that you can write $x_{i_\ell}=6+y_{i_\ell}$ with $y_{i_\ell}\in\mathbb N$, and $y_{i_\ell}$ has no restriction. Your equation becomes $6k+z_1+\cdots+z_5=20$, with $z_1,\dots,z_5\in\mathbb N$ without further restriction, that is solutions in $\mathbb N^5$ of $z_1+\cdots+z_5=20-6k$. There are $\dbinom{24-6k}{4}$ such solutions for each choice of indices $i_1,\dots, i_k$, which in turn can be made in $\dbinom5k$ ways. The number of solutions is obviously $0$ for $k=4,5$. Therefore, by inclusion-exclusion principle: $$c=\sum_{k=1}^3(-1)^{k+1}\binom5k\binom{24-6k}4=\,\text{do it by yourself!}\,.$$

share|improve this answer

number of solutions of equation $$x_1+x_2+...+x_s=m,0\leq x_i\leq s$$ is $${\binom{m}{k}}_{s}=\sum_{i=0}^{m}(-1)^{i}\binom{m}{i}\binom{m+k-si-1}{m-1}\,$$ in this case $$m=20,s=5,k=5$$ $${\binom{20}{5}}_{5}=\sum_{i=0}^{5}(-1)^{i}\binom{20}{i}\binom{24-5i}{19}\,$$

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.