0
$\begingroup$

I am able to come up with good generating functions to solve combinatorial problems, but unable to appreciate its usefulness. For example, I have following combinatorial problem.

How many ways to pay $50$ using unlimited $1, 2 , 5$ coins, (1) when order matters, (2) when order does not matter.

My generating functions:

(1) Number of ways = coefficient of $x^{50}$ in $(1+x+x^2+x^3+...+x^{50})(1+x^2+x^4+x^6+...+x^{50})(1+x^5+x^{10}+x^{15}+...+x^{50})$

Till now, it's fun. But now what? Calculating the coefficient of $x^{50}$ from above expression is as good as counting all individual combination of $1,2,5$ to make $50$, manually. So how is generating function useful in counting?

For case (2) I have following generating function.

Number of ways = coefficient of $x^{50}$ in $(1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+...+\frac{x^{50}}{50!})(1+x^{2}+\frac{x^{4}}{2!}+\frac{x^{6}}{3!}+...+\frac{x^{50}}{25!})(1+x^{5}+\frac{x^{10}}{2!}+...+\frac{x^{50}}{10!})$

However this permutes only same coins. Unable to come up how all types of coins will be permuted among themselves. Also, same question like above, how generating function is helping in count? I can very well count it manually, like $5$ can occur in $0$ to $10$ times, and for each of these occurrences of $5$, count occurrences of $2$ and $1$.

$\endgroup$
2
  • $\begingroup$ Are you implying that if there are only $1$ coins, then the number of ways to pay $50$ is $\frac1{50!}$ if order does not matter? $\endgroup$ – Kenny Lau Mar 4 at 16:36
  • $\begingroup$ Things don´t always need to be useful in mathematics. Anyway, using algebraic/analytical tools for solving combinatorial problems is beautiful and useful all alone. $\endgroup$ – Arroz con Tomate Mar 4 at 16:42
1
$\begingroup$

I would say your generating function in (1) is actually the answer to the "order does not matter" question. A simple function which also works is $\dfrac{1}{(1-x)(1-x^2)(1-x^5)}$. This gives a sequence (starting at zero money) of $1,1,2,2,3,4,5,6,7,8,10,\ldots$ ways of paying coins.

For order mattering the numbers should be higher, you can use the generating function $\dfrac{1}{(1-x-x^2-x^5)}$. This gives a sequence (starting at zero money) of $1,1,2,3,5,9,15,26,44,75,128,\ldots$ ways of paying coins.

In both cases you can turn these into a recurrence for calculation, respectively

  • $a_n=a_{n-1}+a_{n-2}-a_{n-3}+a_{n-5}-a_{n-6}-a_{n-7}+a_{n-8}$ when order does not matter
  • $a_n=a_{n-1}+a_{n-2}+a_{n-5}$ when order matters

each starting $a_0=1$ and $a_n=0$ for $n<0$.

$\endgroup$
4
  • $\begingroup$ Can you please explain the logic behind these recurrence relations? $\endgroup$ – Sukti Sen Mar 6 at 15:38
  • $\begingroup$ @SuktiSen The second one is slightly easier to illustrate: the generating function has denominator $x^0-x^1-x^2-x^5$ so the recurrence is $a_{n-0}-a_{n-1}-a_{n-2}-a_{n-5}=0$. For the first you need to expand its denominator first. $\endgroup$ – Henry Mar 6 at 16:44
  • $\begingroup$ Ok got it. Is there a procedure to calculate the coefficients easily? If I want to how many ways to pay 50 using these generating functions, what's the easiest procedure (using manual calculation, not computer)? $\endgroup$ – Sukti Sen Mar 7 at 11:51
  • $\begingroup$ The second would involve adding up three numbers $50$ times ending with a $12$ digit answer. Is that too difficult? The second involves seven numbers $50$ times with addition and subtraction but a $3$ digit answer. Is that easier or harder? $\endgroup$ – Henry Mar 7 at 12:03

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.