# Number of solutions to equation - is there a better way of solving this than inclusion-exclusion?

We are asked to find the number of solutions for $a+b+c+d+e+f=20$ when $2 \leq a,b,c,d,e,f \leq 6$

Is there a better way of solving it than what I did ? because it an exam, this seems like a very time consuming and difficult way.

What I did:

Firsty, I changed the variable so they will all start from $0$.:

$x_1=a-2,x_2=b-2$ and so on, so we get $x_1+x_2+x_3+x_4+x_5+x_6=8$, $0 \leq x_1,x_2,x_3,x_4,x_5,x_6 \leq 4$

if the variables weren't bound by 4, the number of integer solutions is $\binom{13}{8}$

I defined the set of all bad answers (meaning one of the constraints isn't met) as $P$. Notice that the answer for the question is $\binom{13}{8}-|P|$ so the only thing left to do is find $|P|$.

let:

$A$ be the set of solutions where $x_1 \geq 5$

$B$ be the set of solutions where $x_2 \geq 5$ and so on...

It is easy to see that $P=A\cup B \cup C \cup D \cup E \cup F$ and so with inclusion-exclusion...

$|P|=|A\cup B \cup C \cup D \cup E \cup F| = |A|+|B|+|C|+|D|+|E|+|F|-|A\cap B|-|A\cap C|-|A\cap D|-|A\cap E|-|A\cap F|-|B\cap C|-|B\cap D|-|B\cap E|-|B\cap F|-|C\cap D|-|C\cap E|-|C\cap F|-|D\cap E|-|D\cap F|-|E\cap F|+|A\cap B\cap C|+|A\cap B\cap D|+|A\cap B \cap E|+|A\cap B\cap F|+|A\cap C\cap D|+|A\cap C \cap E|+|A \cap C \cap F|+...$ I'm not gonna even finish writing it since it's so absurdly long.

Is there a better option?

-
Your method of solution is fine. You have $|P|=\binom{6}{1}\binom{8}{3}$, since all the terms after the first 6 are equal to 0. –  user84413 Jan 20 '14 at 23:51

I don't check the details in your proof, but no doubt that your idea is correct.

Using Generating Function, we can give another solution, maybe it will be better? Uh...

In fact, if we want to know the number of solutions of the linear equation in the following form:

$a_0x_0+a_1x_1+\cdots+a_mx_m=n$ with $0 \leq a_i \leq b_i, a_i \in \mathbb{N}$ and $n \in \mathbb{N}$.

The Generating Function corresponding to the equation above is $f(x)=\prod_{i=0}^m (\sum_{j=0}^{b_i} x^{j{a_i}})$,

then the coefficient of $x^n$ in $f(x)$ gives the desired number.

Special Case

If $b_i=\infty (i=0,1,\cdots,m)$, then

$\sum_{j=0}^{b_i} x^{j{a_i}}=\sum_{j=0}^{\infty} x^{j{a_i}}=\dfrac{1}{1-x^{a_i}}$.

$f(x)=\prod_{i=0}^m (\dfrac{1}{1-x^{a_i}})$, it will be easier to determine the coefficient of $x^n$.

-

What you are computing is called Restricted compositions of natural numbers.

There is an explicit formula, see https://oeis.org/wiki/User:Adi_Dani_/Restricted_compositions_of_natural_numbers

The answer here is 951.

-