Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have question. Can anyone able to solve this problem or figure out the idea how non negative integer solution $x_1+5x_2=n$ and $x_1+5x_2=60$ Using the convolution thank you so much

share|improve this question
2  
I don't know what generating functions, combinatorial game theory, and convolution have to do with anything, but obviously $n=60$. Maybe you can clarify your question. –  Rahul Mar 4 '13 at 7:33
add comment

2 Answers

up vote 3 down vote accepted

Here's a combinatorial interpretation: the number of solutions to the second equation is the number of ways to make 60 cents in change using 1 cent and 5 cent coins.

I assume that the second equation is a special case of the first, and that you want to know how to solve both. The method for $n=60$ illustrates the general case.

For a non-negative integer $a$, let $r_a$ be the number of non-negative integer solutions to $x_1=a$ and let $s_a$ be the number of non-negative integer solutions to $5x_2=a$. So $r_a$ is the number of ways to make $a$ cents in change using 1 cent coins alone, and $s_a$ is the number of ways of making $a$ cents in change using 5 cent coins alone. Can you characterize $r_a$ and $s_a$? The number of non-negative integer solutions to $x_1+5x_2=60$ is then given by the convolution $$r_0s_{60}+r_1s_{59}+\ldots+r_{60}s_0.$$ This is the coefficient of $x^{60}$ in the product of the generating functions for the coefficients $r_a$ and $s_a,$ $$(r_0+r_1x+r_2x^2+\ldots)(s_0+s_1x+s_2x^2+\ldots).$$

You should have found that $r_a=1$ for all $a$ and that $s_a=1$ for $a$ divisible by 5 and $s_a=0$ otherwise. Then $$r_0+r_1x+r_2x^2+\ldots=1+x+x^2+\ldots=\frac{1}{1-x}$$ and $$s_0+s_1x+s_2x^2+\ldots=1+x^5+x^{10}+\ldots=\frac{1}{1-x^5}.$$ Here's one method for extracting the coefficient of $x^n$ in the generating function $$\frac{1}{(1-x)(1-x^5)}.$$ Write $$\frac{1}{1-x}=\frac{1+x+x^2+x^3+x^4}{1-x^5}.$$ Then $$\frac{1}{(1-x)(1-x^5)}=\frac{1+x+x^2+x^3+x^4}{(1-x^5)^2}=(1+x+x^2+x^3+x^4)\sum_{r=0}^\infty\binom{-2}{r}(-x^5)^r,$$ where $\binom{-2}{r}=\frac{(-2)(-3)\ldots(-2-r+1)}{r!}$ is the generalized binomial coefficient. You can show that $(-1)^r\binom{-2}{r}=r+1$, and so the generating function is $$(1+x+x^2+x^3+x^4)\sum_{r=0}^\infty(r+1)x^{5r}.$$ The $x^{60}$ term comes from multiplying the $1=x^0$ term in the polynomial with the $r=12$ term in the summation. Hence the answer is $1\cdot(12+1)=13$.

This method can be generalized to the case where you have additional coin values, say 10 cent coins.

share|improve this answer
add comment

Since the left hand sides coincide, we immediately get $n = 60$, and the system reduces to the single equation $$x_1 + 5x_2 = 60$$ or equivalently $$x_1 = 60 - 5x_2 = 5(12 - x_2).$$ Now $x_1$ is non-negative iff $x_2\leq 12$. So there are exactly the $13$ non-negative solutions $$(x_1,x_2)\in\{(60 - 5x_2, x_2) \mid x_2\in\{0,\ldots,12\}\}.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.