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.

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?

share|improve this question
    
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 at 23:51

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer

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.

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.