7
$\begingroup$

How many non-negative integer solutions are there to $a+b+c+d+e=79$ with the constraints $a\ge7$, $b\le34$ and $3\le c\le41$?

I get that for $a\ge7$ you do $79-7=72$, $\binom{72+5-1}{5-1}=\binom{76}4$. For $b\ge35$ I think it's $\binom{47}4$ and I'm not too sure what it is for $3\le c\le41$ and I also have no clue as to how to do them all at the same time.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Can you solve it without the constraints using stars and bars? For the $a \ge 7$ constraint, just make $a'=a-7$ and use that with a sum of $72$. The rest? $\endgroup$ – Ross Millikan May 6 '17 at 1:10
  • $\begingroup$ Is the sum equal to $79$ or $75$? Your attempt seems to be based on the latter number. $\endgroup$ – N. F. Taussig May 6 '17 at 2:17
  • $\begingroup$ If you have a maximum, count the ways without the constraint and subtract the ways over the maximum. You know how to do that from the $a$ constraint. For $3 \le c \le 41$, let $c'=c-3$ to get the minimum, then subtract $c' \gt 38$ to get the maximum. $\endgroup$ – Ross Millikan May 6 '17 at 2:22
  • $\begingroup$ You need to consider all the constraints together, but your attempts only address one at a time; this is not sufficient. $\endgroup$ – Marc van Leeuwen May 6 '17 at 4:37
  • $\begingroup$ Use Partition Theory. $\endgroup$ – Pixel May 6 '17 at 7:06
7
$\begingroup$

Here is an answer based upon generating functions.

  • $a\geq 7$ can be encoded as \begin{align*} z^7+z^8+z^9+\cdots=z^7\left(1+z+z^2+\cdots\right)=\frac{z^7}{1-z}\tag{1} \end{align*}

  • $b\leq 34$ can be encoded as \begin{align*} 1+z+z^2+\cdots+z^{34}=\frac{1-z^{35}}{1-z}\tag{2} \end{align*}

  • $3\leq c\leq 41$ can be encoded as \begin{align*} z^3+z^4+\cdots+z^{41}=z^3\left(1+z+z^2+\cdots+z^{38}\right)=\frac{z^3\left(1-z^{39}\right)}{1-z}\tag{3} \end{align*}

  • $d,e\geq 0$ can be both encoded as \begin{align*} 1+z+z^2+\cdots=\frac{1}{1-z}\tag{4} \end{align*}

We want to find the number of non-negative integer solutions of \begin{align*} a+b+c+d+e=79 \end{align*} with the constraints given above.

Denoting with $[z^n]$ the coefficient of $z^n$ we are looking for \begin{align*} [z^{79}]&\frac{z^7}{1-z}\cdot\frac{1-z^{35}}{1-z}\cdot \frac{z^3\left(1-z^{39}\right)}{1-z}\cdot \left(\frac{1}{1-z}\right)^2\tag{5}\\ &=[z^{79}]z^{10}\frac{(1-z^{35})(1-z^{39})}{(1-z)^5}\\ &=[z^{69}]\frac{(1-z^{35})(1-z^{39})}{(1-z)^5}\tag{6}\\ &=[z^{69}]\left(1-z^{35}-z^{39}\right)\sum_{k=0}^\infty\binom{-5}{k}(-z)^k\tag{7}\\ &=\left([z^{69}]-[z^{34}]-[z^{30}]\right)\sum_{k=0}^\infty\binom{k+4}{4}z^k\tag{8}\\ &=\binom{73}{4}-\binom{38}{4}-\binom{34}{4}\tag{9}\\ &=1088430-73815-46376\\ &=968239 \end{align*}

in accordance with the answer of @CYKwong.

Comment:

  • In (5) we select the coefficient of $[z^{79}]$ of the product of the generating functions (1) to (4) which correspond to the valid ranges specified for $a$ to $e$.

  • In (6) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

  • In (7) we multiply out the numerator and skip terms with powers greater than $69$ since they do not contribute to $[z^{69}]$. We also apply the binomial series expansion.

  • In (8) we use the linearity of the coefficient of operator, apply the same rule as in (6) three times and use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$.

  • In (9) we select the coefficients accordingly.

$\endgroup$
3
$\begingroup$

Note that

$$\sum_{m=k}^{n}\binom{m}{k}=\binom{n+1}{k+1}$$

The number of solutions of the equation $d+e=79-a-b-c$ is

$$\begin{cases}\displaystyle \binom{79-a-b-c+1}{1}=\binom{80-a-b-c}{1}, &\text{if }a\le79-b-c \\[0.2cm] 0,&\text{otherwise}\end{cases} $$

The number of solutions of the equation $a+d+e=79-b-c$ such that $a\ge7$ is

$$\begin{cases} \displaystyle\sum_{a=7}^{79-b-c}\binom{80-a-b-c}{1}=\displaystyle\sum_{m=1}^{73-b-c}\binom{m}{1}=\binom{74-b-c}{2}, &\text{if }b\le 72-c \\[0.2cm] 0,&\text{otherwise}\end{cases} $$

The number of solutions of the equation $a+b+d+e=79-c$ such that $a\ge7$ and $b\le34$ is

\begin{align*} &\;\begin{cases} \displaystyle\sum_{b=0}^{72-c}\binom{74-b-c}{2}=\sum_{m=2}^{74-c}\binom{m}{2}=\binom{75-c}{3}, &\text{if }39\le c\le 41 \\[0.2cm]\displaystyle\sum_{b=0}^{34}\binom{74-b-c}{2}=\sum_{m=40-c}^{74-c}\binom{m}{2}, &\text{if }c\le 38 \\[0.2cm] 0,&\text{otherwise}\end{cases} \\ =&\;\begin{cases} \displaystyle\binom{75-c}{3}, &\text{if }39\le c\le 41 \\[0.2cm] \displaystyle \sum_{m=2}^{74-c}\binom{m}{2}-\sum_{m=2}^{39-c}\binom{m}{2} =\binom{75-c}{3}-\binom{40-c}{3}, &\text{if }c\le 37\\[0.2cm] \displaystyle \sum_{m=2}^{36}\binom{m}{2}=\binom{37}{3}, &\text{if }c= 38 \\[0.2cm] 0,&\text{otherwise}\end{cases} \end{align*}

The number of solutions of the equation $a+b+c+d+e=79$ such that $a\ge7$ and $b\le34$ and $3\le x\le41$ is

\begin{align*} &\;\sum_{c=3}^{37}\left[\binom{75-c}{3}-\binom{40-c}{3}\right]+\binom{37}{3}+\sum_{c=39}^{41}\binom{75-c}{3}\\ =&\;\sum_{m=38}^{72}\binom{m}{3}-\sum_{m=3}^{37}\binom{m}{3}+\binom{37}{3}+\binom{36}{3}+\binom{35}{3}+\binom{34}{3}\\ =&\;\sum_{m=3}^{72}\binom{m}{3}-2\sum_{m=3}^{37}\binom{m}{3}+\binom{37}{3}+\binom{36}{3}+\binom{35}{3}+\binom{34}{3}\\ =&\;\binom{73}{4}-2\binom{38}{4}+\binom{37}{3}+\binom{36}{3}+\binom{35}{3}+\binom{34}{3}\\ =&\;968239 \end{align*}

$\endgroup$
  • $\begingroup$ I checked the answer with an Excel VBA program. So I think it is correct. $\endgroup$ – CY Aries May 6 '17 at 7:48
  • 1
    $\begingroup$ The answer is also equal to $\displaystyle \binom{73}{4}- \binom{38}{4}- \binom{34}{4}$. Maybe there is a better method to reach the answer. $\endgroup$ – CY Aries May 6 '17 at 7:54
  • $\begingroup$ What about generating functions? $\endgroup$ – user370967 May 6 '17 at 8:11
  • $\begingroup$ $\binom{73}{4}=\binom{79-7-3+5-1}{5-1}$ is the number of solutions with the constraints $a\ge7$ and $c\ge 3$. $\endgroup$ – CY Aries May 6 '17 at 8:19
  • $\begingroup$ @CYKwong: Nice answer. The results coincide. (+1) $\endgroup$ – Markus Scheuer May 6 '17 at 9:39
2
$\begingroup$

So we are looking for non-negative solutions for to $a+b+c+d+e=79$ with the constraints $a\ge7$, $b\le34$ and $3\le c\le41$

I always like, in this kind of problem, to work with generating functions. Everything variable gets a polynomial such that its powers correspond to the restraints, and such that he requested solution would be the coefficient of $x^{79}$ in their product:

The restriction on $a$ translates to the function $$(x^7 + x^8 + x^9 + \ldots) = x^7\left(\frac{1}{1-x}\right)$$ For $b$ we have $$(1+ x + x^2 + \ldots x^{34}) = \frac{1-x^{35}}{1-x}$$ all using standard geometric series. For $c$ we have $$\left(x^3 + x^4 + \ldots + x^{41}\right) = x^3\left(1+x+ \ldots + x^{38}\right) = x^3\left(\frac{1-x^{39}}{1-x}\right)$$ while $d$ and $e$ have no restrictions so we use $$(1+x+x^2 + \ldots) = \frac{1}{1-x}$$

So the answer to your question is the coefficient of $x^{79}$ in:

$$x^7 \frac{1}{1-x} (1-x^{35})\frac{1}{1-x} x^3 (1-x^{39})\frac{1}{1-x}\left(\frac{1}{1-x}\right)^2 $$ which comes down to the coefficient of $x^{69}$ (removing the always present $x^{10}$) in:

$$(1-x^{35})(1-x^{39})(1-x)^{-5} = (1 - x^{35} - x^{39} + x^{74})\sum_{k=0}^\infty {k+4 \choose k} x^k$$ using the generalised binomial formula.

And this coefficient equals $${73 \choose 69} - {38 \choose 34}- {34 \choose 30}$$

$\endgroup$
0
$\begingroup$

We may solve this problem by finding the number of solutions with the following constraints

(1) $a\ge7 $ and $c\ge3$

(2) $a\ge7 $ and $c\ge42$

(3) $a\ge7 $, $b\ge35$ and $c\ge3$

(4) $a\ge7 $, $b\ge35$ and $c\ge42$

The answer to the problem is the answer of (1) - the answer of (2) - the answer of (3) + the answer of (4)

(1) Let $a'=a-7$ and $c'=c-3$. The equation is equivalent to $a'+b+c'+d+e=79-7-3 $, where the variables are nonnegative integers. The number of solutions is $\binom{79-7-3+4} {4 }=\binom {73}{4}$.

(2) Similar to (1), the number of solutions is $\binom{79-7-42+4} {4 }=\binom {34}{4}$.

(3) The number of solutions is $\binom{79-7-3-35+4} {4 }=\binom {38}{4}$.

(4) is impossible as $a+b+c>79$.

$\endgroup$
  • $\begingroup$ how did you write case (2)$c \geq 42$ ,In the question the condition is $3 \leq c \leq 41 $! $\endgroup$ – virat May 16 '17 at 12:13
  • $\begingroup$ It's inclusion - exclusion principle $\endgroup$ – CY Aries May 16 '17 at 12:16
0
$\begingroup$

This problem can be solved using the principle of inclusion. First observe that the problem is equivalent to finding the number of non-negative integer solutions to $$ a'+b+c'+d+e=69\tag{1} $$ where $b\leq 34, c'\leq 38$. Let $B$ be the set of non-negative integer solutions to (1) where $b\geq 35$ and $C$ be the set of set of non-negative integer solutions to (1) where $c'\geq 39$ and let $U$ be the set of non-negative integer solutions to (1) without any constraints. The number of solutions equals $$ \begin{align} |\bar{B}\cap\bar{C}| &=|U|-|B|-|C|+|B\cap C|\\ &=\binom{5+69-1}{4}-\binom{5+(69-35)-1}{4}-\binom{5+(69-39)-1}{4} + 0\\ &=\binom{73}{4}-\binom{38}{4}-\binom{34}{4} \end{align} $$ by the principle of inclusion exclusion where $|B\cap C|=0$ since if $b\geq 35$ and $c'\geq 39$, then $b+c'\gt 69$.

$\endgroup$
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

How many non-negative integer solutions are there to $\ds{a + b + c + d + e = 79}$ with the constraints $\ds{\quad a \geq 7\,,\quad b \leq 34\quad\mbox{and}\quad 3 \leq c \leq 41}$ ?.

The answer is given by \begin{align} \mc{N} & = \sum_{a = 7}^{\infty}\sum_{b = 0}^{34}\sum_{c = 3}^{41}\sum_{d = 0}^{\infty} \sum_{e = 0}^{\infty}\bracks{z^{79}}z^{a + b + c + d + e} = \sum_{a = 0}^{\infty}\sum_{b = 0}^{34}\sum_{c = 0}^{38}\sum_{d = 0}^{\infty} \sum_{e = 0}^{\infty}\bracks{z^{79}}z^{\pars{a + 7} + b + \pars{c + 3} + d + e} \\[5mm] & = \bracks{z^{69}}\sum_{a = 0}^{\infty}\sum_{b = 0}^{34}\sum_{c = 0}^{38} \sum_{d = 0}^{\infty}\sum_{e = 0}^{\infty}z^{a + b + c + d + e} = \bracks{z^{69}}\pars{\sum_{a = 0}^{\infty}z^{a}}^{3} \pars{\sum_{b = 0}^{34}z^{b}}\pars{\sum_{c = 0}^{38}z^{c}} \\[5mm] & = \bracks{z^{69}}{1 \over \pars{1 - z}^{3}}\,{z^{35} - 1 \over z - 1} \,{z^{39} - 1 \over z - 1} = \bracks{z^{69}}{z^{74} - z^{39} - z^{35} + 1 \over \pars{1 - z}^{5}} \\[5mm] & = -\bracks{z^{30}}\pars{1 - z}^{-5} - \bracks{z^{34}}\pars{1 - z}^{-5} + \bracks{z^{69}}\pars{1 - z}^{-5} \\[5mm] & = -{-5 \choose 30}\pars{-1}^{30} - {-5 \choose 34}\pars{-1}^{34} + {-5 \choose 69}\pars{-1}^{69} = -{34 \choose 30} - {38 \choose 34} + {73 \choose 69} \\[5mm] & = \bbx{968239} \end{align}

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