$a+b+c+d+e=79$ with constraints

Question

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.

Answer 1

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*}

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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