2
$\begingroup$

How many solutions are there to the equation $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 25$ where each $x_i$ is a non-negative integer, $3 \leq x_1 \leq 10, \ 2 \leq x_2 \leq 7$ and $x_3 \geq 5$

I have been able to do all my counting problems but this one. I can not find an equation for max number per variety.

I know that I will subtract the min for each $x$ from the total, but I can not do $\begin{pmatrix} 15 \\ 6\end{pmatrix}$ cause that would not factor in the max per variety.

What is the equation I would use for this?

$\endgroup$
5
$\begingroup$

The generating function would be

$$(x^3+x^4+...+x^{10})(x^2+x^3+...+x^7)(x^5+x^6+...)(1+x+x^2+...)^3$$

Simplify, $$x^{10}(1-x^8)(1-x^6)({1\over 1-x})^6$$

Now we are finding the coefficient of $x^{25}$ of the above, which is same as $x^{15}$ in

$$(1-x^8)(1-x^6)({1\over 1-x})^6=(1-x^8-x^6+x^{14})({1\over 1-x})^6$$

So the coefficient of $x^{15}$ is

(coefficient of $x^{15}$ in $({1\over 1-x})^6$)$-$(coefficient of $x^{7}$ in $({1\over 1-x})^6$)$-$(coefficient of $x^{9}$ in $({1\over 1-x})^6$)$+$(coefficient of $x^{1}$ in $({1\over 1-x})^6$)

Which is basically

$${15+6-1\choose6-1}-{7+6-1\choose6-1}-{9+6-1\choose6-1}+{1+6-1\choose6-1}$$

$\endgroup$
  • $\begingroup$ I get $\binom{20}{5}-\color{#C00000}{\binom{14}{5}}-\binom{12}{5}+\binom{6}{5}$. I think you want to be looking at the coefficient of $x^9$ instead of $x^8$. $\endgroup$ – robjohn Dec 4 '15 at 14:22
  • $\begingroup$ You are right, I made a mistake calculating $15-6$, will fix it. $\endgroup$ – cr001 Dec 4 '15 at 16:39
2
$\begingroup$

The answer will be the coefficient of $x^{25}$ from the below expression-

$$(x^3+x^4+ \dots+x^{10})(x^2+x^3+ \dots+x^7)(x^5+x^6+ \dots+x^{20})(x^0+x^1+ \dots+x^{15})(x^0+x^1+ \dots+x^{15})(x^0+x^1+ \dots+x^{15}).$$

$\endgroup$
0
$\begingroup$

Hint: Try to find out the coefficient of $x^{25}$ from the below expression-

$$(x^3+x^4+ \dots+x^{10})(x^2+x^3+ \dots+x^7)(x^5+x^6+ \dots+x^{20})(1+x+\dots+x^{15})^3.$$

That will be your answer.

$\endgroup$
  • 1
    $\begingroup$ I think you need another three $({1\over 1-x})$ in your generating function. $\endgroup$ – cr001 Dec 4 '15 at 5:19
  • $\begingroup$ Thanks. Yes that was a major slip. I forgot to check that there are more variables. $\endgroup$ – Rajat Dec 4 '15 at 7:10
0
$\begingroup$

Let $y_1=x_1-3, \;y_2=x_2-2, \;y_3=x_3-5$, and $y_i=x_i$ for $4\le i\le 6$.

Then $y_1+\cdots+y_6=15$ with $y_1\le7$ and $y_2\le5$;

so if S is the set of solutions in nonnegative integers without restrictions,

$A_1$ is the set of solutions with $y_1\ge8$, and $A_2$ is the set of solutions with $y_2\ge6$,

$\displaystyle |S|-|A_1|-|A_2|+|A_1\cap A_2|=\binom{20}{5}-\binom{12}{5}-\binom{14}{5}+\binom{6}{5}$

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