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.


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.

| cite | improve this question | | | | |
  • $\begingroup$ Hint: partial fractions $\endgroup$ – Thomas Andrews Oct 15 '18 at 23:04
  • $\begingroup$ @ThomasAndrews could you elaborate a bit more? $\endgroup$ – cosmicbrownie Oct 15 '18 at 23:09
  • $\begingroup$ 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$. $\endgroup$ – Mike Earnest Oct 16 '18 at 0:09
  • $\begingroup$ @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? $\endgroup$ – cosmicbrownie Oct 16 '18 at 0:58
  • $\begingroup$ @cosmicbrownie Are you sure the restrictions are correct? $\endgroup$ – 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.$
| cite | improve this answer | | | | |

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.