1

I'm currently doing generating functions, and the purpose of those functions is to find how many ways there are to choose an x amount of objects.

I just don't understand how they get to the final conclusion. Take for example this exercise:

You have to go to the baker and you have to buy r amount of cakes. The baker has 3 cheese-cakes, 2 apricots-cakes, and 4 strawberry-cakes. How many different ways are there for you to choose?

This gives us the following generating function: $(1 + x + x^2 + x^3)(1 + x + x^2)(1 + x + x^2 + x^3 + x^4)$

After resolving this function, we get the polynomial: $1 + 3x + 6x^2 + 9x^3 + 11x^4 + 11x^5 + 9x^6 + 6x^7 + 3x^8 + x^9$

I understand how they get the generating function, and how to resolve it to get the polynomial, but now the solution of the exercise says:

So we can conclude that there are 6 different ways to choose 7 cakes.

I know the 6 and 7 relate to each other because one is the exponent of the other (see the term $6x^7$), but how do they get to the number 6, and 7?

There are 9 different cakes, so why 7?

O'Niel
  • 239

2 Answers2

1

Actually, there are $3$ different types of cakes but the cakes of the same type are identical (I mean for example $4$ strawberry-cakes are identical in themselves so whichever you choose doesn't matter). This is also the reason why all the coefficients of $1$, $x$, $x^2$,... in the generating function $(1 + x + x^2 + x^3)(1 + x + x^2)(1 + x + x^2 + x^3 + x^4)$ are $1$ (It means there is $1$ way of choosing $1$ cake or $2$ cakes or $3$ cakes or $4$ cakes from $4$ strawberry-cakes and others are similar). Therefore, even though we are choosing $7$ cakes from $9$ cakes, the answer is this small.

Note that this reasoning also explains why we should consider the coefficient of the term $x^7$ while choosing $7$ cakes. Because what we are doing is choosing:

  • $1$ cheese-cake($x$), $2$ apricot-cakes($x^2$), $4$ strawberry-cakes($x^4$) with $1$ way (If we multiply these terms, we get $1x^7$, so there is only $1$ way of choosing);

Other cases are similar:

  • $2$ cheese-cake, $2$ apricot-cakes, $3$ strawberry-cakes with $1$ way;

  • $2$ cheese-cake, $1$ apricot-cakes, $4$ strawberry-cakes with $1$ way;

  • $3$ cheese-cake, $2$ apricot-cakes, $2$ strawberry-cakes with $1$ way;

  • $3$ cheese-cake, $1$ apricot-cakes, $3$ strawberry-cakes with $1$ way;

  • $3$ cheese-cake, $0$ apricot-cakes, $4$ strawberry-cakes with $1$ way;

So in total we have $6$ ways to choose $7$ cakes from $9$ cakes.

ArsenBerk
  • 13,211
0

The generating function approach is as follows. We would like to know the number of integer solutions to $$x_1 + x_2 + x_3 = r$$ subject to $0 \le x_1 \le 3$, $0 \le x_2 \le 2$, and $0 \le x_3 \le4$. To solve the problem with a generating function, let $a_r$ be the number of solutions for $r = 0, 1, 2, 3, \dots$ and define $$f(x) = \sum_{r=0}^{\infty} a_r x_r$$ (In this case we know that $a_r = 0$ for $r>9$, so $f(x)$ is actually a polynomial.)

You have already found that $$\begin{align}f(x) &= (1 + x + x^2 + x^3)(1+x+x^2)(1+x+x^2+x^3+x^4) \\ &= 1+3 x+6 x^2+9 x^3+11 x^4+11 x^5+9 x^6+6 x^7+3 x^8+x^9 \end{align}$$ so $a_0 = 1$, $a_1=3$, $a_2=6$, ..., $a_7=6$, ..., $a_9=1$.

The number of ways to choose 7 cakes is just the value of $a_7$, but the generating function gives the number of ways to choose $r$ cakes for all values of $r$.

awkward
  • 14,736