# Find the generating function for equation $2x_1+3x_2+5x_3+7x_4=n$ with restrictions and number of solutions for $n = 50$

Question:

Find the generating function for the number integer solutions of the equation $$2x_1+3x_2+5x_3+7x_4=n$$, where $$0 \leq x_1, 4 \leq x_2,4 \leq x_3,$$ and $$5 \leq x_4$$, and find the number of solutions for n=50.

Attempt:

Without restrictions, I know I would get $$\frac{1}{(1-x^2)} \cdot \frac{1}{(1-x^3)}\cdot \frac{1}{(1-x^5)} \cdot \frac{1}{(1-x^7)}$$. The restrictions part is what I'm really struggling dealing with. For instance, would I get $$(x^6 + x^9 + ...)$$ or $$(x^{12} + x^{15}+...)$$ for $$x_2$$?

I can use Mathematica to solve my problem, but I'm not sure what I would use to solve my problem.

• Hint: partial fractions – Thomas Andrews Oct 15 '18 at 23:04
• @ThomasAndrews could you elaborate a bit more? – cosmicbrownie Oct 15 '18 at 23:09
• Since $x_2\ge 4$, the smallest value that $3x_2$ can contribute is $3\cdot 4=12$. So it is $x^{12}+x^{15}+\dots$. – Mike Earnest Oct 16 '18 at 0:09
• @MikeEarnest my generating function is $\frac{1}{(1-x^2)} \cdot \frac{x^{12}}{(1-x^3)}\cdot \frac{x^{20}}{(1-x^5)} \cdot \frac{x^{35}}{(1-x^7)}$. Does this look correct? – cosmicbrownie Oct 16 '18 at 0:58
• @cosmicbrownie Are you sure the restrictions are correct? – Toby Mak Oct 16 '18 at 3:07

Back to the generating function, so we can get the general case.

Using Wolfram Alpha and partial fractions, I get that $$\frac{1}{(1-x^2)(1-x^3)(1-x^5)(1-x^7)}$$ is equal to:

\begin{align}&\frac{1}{9}\cdot\frac{1}{ x^2 + x + 1} \\&+ \frac{1}{5}\cdot\frac{x^2 + 1}{x^4 + x^3 + x^2 + x + 1} \\&+ \frac 1 7\cdot\frac{x^5 + 2 x^3 + x^2 + x + 2}{x^6 + x^5 + x^4 + x^3 + x^2 + x + 1} \\&- \frac{23}{112}\cdot\frac{1}{x-1} \\&+\frac{1}{16}\cdot\frac{1}{x+1} \\&+ \frac{251}{2520}\cdot\frac 1{(x - 1)^2}\\&- \frac{13}{420}\cdot\frac{1}{ (x - 1)^3} \\&+ \frac 1{210}\cdot\frac{1}{(x - 1)^4} \end{align}

Which can be written as:

\begin{align}&\frac{1}{16}\cdot\frac{1-x}{1-x^2} \\&+\frac{1}{9}\cdot\frac{1-x}{1-x^3}\\& + \frac{1}{5}\cdot\frac{1-x+x^2-x^3}{1-x^5} \\&+ \frac{1}{7}\cdot\frac{2-x+x^3-2x^4+x^5-x^6}{1-x^7} \\&+ \frac{23}{112}\cdot\frac{1}{1-x} \\&+ \frac{251}{2520}\cdot\frac{1}{(1-x)^2}\\&+\frac{13}{420}\cdot\frac{1}{(1-x)^3}\\&+\frac{1}{210}\cdot\frac{1}{(1-x)^4}\end{align}

For any $$n$$, we'd want to find the coefficient of $$x^{n-67}$$ in this expression.

Since $$\frac{1}{16}+\frac{1}{9}+\frac{1}{5}+\frac{2}{7}<1$$, the first bunch of terms adjust the coefficient less than $$\pm 1$$, so a good approximation is:

$$f(n)=\frac{23}{112} + \frac{251}{2520}\binom{n-66}{1} +\frac{13}{420}\binom{n-65}{2} +\frac{1}{210}\binom{n-64}{3}.$$

In particular, the correct value will be one of $$\left\lfloor f(n)\right\rfloor$$ or $$\left\lceil f(n)\right\rceil.$$

Which depends on the values of $$n_2=(n-67)\bmod 2,$$ $$n_3=(n-67)\bmod 3,$$ $$n_5=(n-67)\bmod 5$$ and $$n_7=(n-67)\bmod 7.$$

For example, if $$n=92$$ then $$n_2=1,n_3=1, n_5=0,n_7=4$$ and the added terms are:

$$\frac{-1}{16}+\frac{-1}{9}+\frac{1}{5}+\frac{-2}{7}<0$$ so the count is $$\lfloor f(n)\rfloor.$$

This comes out to $$29$$ exactly if you sum up all the terms.

Writing $$H_{a_0,a_1,\dots,a_{q-1}}(n)=\begin{cases}0& n<0\\ a_i&i\equiv n\pmod q\end{cases}$$

Then the exact formula (with $$m=n-67$$) is:

\begin{align}&\frac{1}{16}H_{1,-1}(m)\\&+\frac{1}9 H_{1,-1,0}(m) \\&+ \frac{1}{5}H_{1,-1,1,-1,0}(m)\\&+\frac{1}{7} H_{2,-1,0,1,-2,1,-1}(m)\\& +\frac{23}{112} \\&+ \frac{251}{2520}\binom{m+1}{1} \\&+\frac{13}{420}\binom{m+2}{2} \\&+\frac{1}{210}\binom{m+3}{3}\end{align}

Let $$g(m) = \frac{251}{2520}\binom{m+1}{1} +\frac{13}{420}\binom{m+2}{2} +\frac{1}{210}\binom{m+3}{3}$$, and note that $$\frac{23}{112} = \frac{1}{16}+\frac{1}{7}.$$

• When $$m\equiv 0\pmod 7$$ the count is $$\lceil g(m)\rceil.$$
• When $$m\equiv 3,5\pmod 7$$ the count is $$\lceil g(m)\rceil$$ unless $$m\equiv 1,13\pmod {30}$$, otherwise it is the nearest integer to $$g(m).$$
• When $$m\equiv 1,4,6\pmod 7$$ the count is the nearest integer to $$g(m).$$
• When $$m\equiv 2\pmod 7$$ then it is the nearest integer to $$g(m)$$ id $$m\equiv 1,3,4\pmod{5}$$, otherwise it is $$\lceil g(m)\rceil.$$