Introduction to generating functions through the Binomial Theorem

Qual é o coeficiente de $x^5$ na expansão de $(x+1)^{13}$? Ou qual será o coeficiente de $x^i$ na expansão de $(x+1)^{13}$? E de $(x+1)^n$? Então e de $(x+c)^n$?
Pelo binómio de Newton temos que $$(x+c)^n = \sum_{i=0}^n \binom{n}{i}c^{n-i}x^i$$ mas como é que podemos chegar a essa fórmula? Vamos começar por escrever os fatores de $(x+c)^n$ todos lado a lado: $$(x+c)\times(x+c)\times\cdots\times(x+c)$$ e agora pensamos no resultado de aplicar a propriedade distributiva neste polinómio todo sem fazer simplificações. A título de exemplo, tomemos $n = 2,3$: $$\begin{align} (x+c)^2 &= (x+c)(x+c) \\ &= xx + xc + cx + cc\\ (x+c)^3 &= (x+c)(x+c)(x+c) \\ &= (xx + xc + cx + cc)(x + c) \\ &= xxx + xxc + xcx + xcc + cxx + cxc + ccx + ccc\end{align}$$ O que podemos ver é que cada parcela final veio de escolher, dentro de cada factor $(x+c)$, ou o $x$ ou o $c$. A parcela $xcx$ vem da escolha $(\underline{x}+c)(x + \underline{c})(\underline{x}+c)$ e a parcela $xxc$ vem da escolha $(\underline{x}+c)(\underline{x}+c)(x + \underline{c})$. A razão pela qual não fizémos uma única simplificação é precisamente essa: para podermos identificar cada parcela com uma escolha de vários $x$ e vários $c$ na factorização.
Podemos agora decidir simplificar a nossa expressão e aglomerar todas as parcelas consoante o seu expoente em $x$. Obviamente, a contribuição de cada parcela vai depender do número de $x$ que aparecem nessa parcela: $xcx$ contribui para a parcela de $x^2$ porque $xcx$ tem $2$ vezes o $x$; por outro lado, cada parcela surgiu após fazermos uma escolha dentro de cada um dos factores existentes, portanto todas as parcelas têm o mesmo número de letras, que é o mesmo que dizer que se escolhi $i$ vezes o $x$, então tive de ter escolhido $n-i$ vezes o $c$: se escolhi duas vezes o $x$ em $xcx$ então é porque só escolhi uma vez o $c$, já que no exemplo anterior $n=3$.
Este raciocínio permite-nos concluir quais serão os coeficientes $a_0, a_1, a_2$ e $a_3$ em $a_0c^3 + a_1c^2x + a_2cx^2 + a_3x^3$: $a_0$ é o número de maneiras diferentes que eu tenho para escolher $0$ vezes o $x$ em $(x+c)^3$, que é só uma: escolher $c$ em cada factor. $a_1$ é o número de maneiras que eu tenho para escolher $1$ vez o $x$ (e portanto $2$ vezes o $c$) em $(x+c)^3$, que são 3. De modo semelhante temos $a_2 = 3$ e $a_3 = 1$:
$$\begin{align}(x+c)^3 &= a_0c^3 + a_1c^2x + a_2cx^2 + a_3x^3 \\ &= c^3 + 3c^2x + 3cx^2 + x^3\end{align}$$ O ponto importante aqui é que o coeficiente em $x^i$ está relacionado com escolher $i$ vezes o $x$. Daqui para a frente tomemos sempre $c = 1$, para que o coeficiente em $x^i$, ao ser multiplicado por alguma potência de $c$, não seja alterado.
Se eu tiver três bolas de cores diferentes, de quantas maneiras posso escolher duas dessas bolas? É sabido que a resposta é $\binom{3}{2} = 3$, mas façamos o seguinte raciocínio: vamos dizer que temos três sacos, um com cada bola, e vamos ver de quantas maneiras podemos decidir tirar - ou não - cada bola do seu saco. Para cada saco, identificamos tirar a bola com $x$ e identificamos não tirar a bola com $1$. Assim, escrever $(x+1)(x+1)(x+1)$ codifica, pela propriedade distributiva, todas as maneiras que temos para escolher tirar algumas das bolas! Por exemplo a parcela $x\times1\times x$ corresponde a tirar as primeira e terceira bolas e não tirar a segunda... Mas não nos importa que bolas tiramos, apenas interessa tirar $2$ bolas, ou seja, interessa ter $x^2$ no final! Para isso, basta olhar para o coeficiente de $x^2$ na expansão de $(x+1)^3$ para saber de quantas maneiras podíamos ter tirado $2$ bolas. Já vimos em cima que $x^2$ tem coeficiente $3$, logo a resposta é $3$.
Podemos agora perceber melhor que escolhemos $c = 1$ para facilitar a nossa contagem.

Começamos a ver as funções geradoras a aparecer. Podemos usar funções geradoras em problemas de combinatória, onde arranjamos uns polinómios "úteis" no contexto do problema, multiplicamo-los, e depois procuramos a nossa resposta no coeficiente de algum $x^i$. O expoente de $x$ está sempre a "contar" alguma coisa. Tome-se este problema: se eu tiver $2$ bolas vermelhas e $3$ bolas azuis, de quantas maneiras posso escolher um grupo de $4$ bolas?
Vamos pôr de novo as bolas vermelhas todas num saco e as azuis todas noutro. Vou associar o saco vermelho com o polinómio $(1 + x + x^2)$: o expoente de $x$ representa quantas bolas tirei do saco, e o coeficiente de $x^i$ (que é $1$ nas três parcelas) representa quantas maneiras tenho de retirar $i$ bolas vermelhas do saco! É óbvio que há sempre só uma maneira porque as bolas vermelhas são todas iguais. Qual será o polinómio a associar ao saco azul? Por um raciocínio semelhante vemos que é $(1 + x + x^2 + x^3)$. Para obtermos a resposta ao nosso problema, basta expandir $$(1 + x + x^2)(1 + x + x^2 + x^3)$$ e ler o coeficiente de $x^4$! Já que $$(1 + x + x^2)(1 + x + x^2 + x^3) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5$$ vemos que a nossa resposta é $2$! Há apenas duas maneiras de ter $4$ bolas no total: ou temos $2$ vermelhas e $2$ azuis ou temos $1$ vermelha e $3$ azuis. Nos outros coeficientes temos as respostas às perguntas de quantas formas diferentes posso tirar $i$ bolas de entre $2$ vermelhas e $3$ azuis? De um modo mais formal, uma função geradora é uma série que associamos a uma sucessão, para que possamos usar técnicas e operações de séries nessas mesmas sucessões.
Tomemos um último exemplo ainda menos trivial. De quantas maneiras podemos tirar $7$ bolas de entre $10$ bolas verdes e $4$ bolas vermelhas, sabendo que temos de tirar um número par de bolas verdes e sabendo que cada bola vermelha tem um número único que a identifica? Para resolver este problema temos de começar por associar um polinómio a cada conjunto de bolas. Se o expoente de $x$ contar o número de bolas tiradas, e porque sabemos que há uma única maneira de tirar $0$ bolas verdes, tal como só há uma maneira de tirar $2,4,6,8$ ou $10$, a função geradora que representa as escolhas das bolas verdes é $$1 + x^2 + x^4 + x^6 + x^8 + x^{10}$$ Por outro lado as bolas vermelhas agora são todas diferentes, portanto o polinómio a associar não é $$1 + x + x^2 + x^3 + x^4$$ De facto, há $4$ maneiras diferentes de tirar uma única bola vermelha, $6$ maneiras de tirar duas bolas vermelhas, $4$ maneiras de tirar três bolas e uma única maneira de tirar as $4$ bolas, logo o polinómio é $$1 + 4x + 6x^2 + 4x^3 + x^4 = (1 + x)^4$$ Evidentemente que o polinómio obtido é igual a $(1+x)^4$, já que o raciocínio de deixar dentro do saco ($1$) ou retirar do saco ($x$) cada bola, se aplica. Já temos os dois polinómios e agora basta-nos multiplicá-los: $$\begin{align}(1+x)^4(1 + x^2 + x^4 + x^6 + x^8 + x^{10}) &= 1 + 4 x + 7 x^2 + 8 x^3 \\ &+ 8 x^4 + 8 x^5 + 8 x^6 + 8 x^7 + 8 x^8 \\ &+ 8 x^9 + 8 x^{10} + 8 x^{11} + 7 x^{12} \\ &+ 4 x^{13} + x^{14}\end{align}$$ e a resposta certa é $8$, que é o coeficiente de $x^7$. Para os mais céticos, a verificação é fácil: temos de tirar $4$ ou $6$ bolas verdes (8 bolas verdes já é demais e $2$ é de menos, só temos $4$ bolas vermelhas). Se tirarmos $4$, faltam $3$ vermelhas, e podemos escolhê-las de $4$ maneiras diferentes. Se tirarmos $6$ verdes precisamos de uma última vermelha, que pode ser escolhida de $4$ maneiras diferentes, logo há $4+4 = 8$ escolhas diferentes no total.
Num próximo post incluirei mais problemas de combinatória (e mais interessantes) e mostrarei também como podemos usar funções geradoras para encontrar fórmulas explícitas para relações de recorrência.

What is the coefficient of $x^5$ in the expansion of $(x+1)^{13}$? Then what is the coefficient of $x^i$ in the expansion of $(x+1)^{13}$? And in the expansion of $(x+1)^n$? And what if we expand $(x+c)^n$ instead?
By the binomial theorem we have that $$(x+c)^n = \sum_{i=0}^n \binom{n}{i}c^{n-i}x^i$$ but how can one deduce that formula? Let us start by writing all the factors of $(x+c)^n$ side by side: $$(x+c)\times(x+c)\times\cdots\times(x+c)$$ and now let us consider the result of applying the distributive property without making any simplifications. As an example, let $n = 2,3$: $$\begin{align} (x+c)^2 &= (x+c)(x+c) \\ &= xx + xc + cx + cc\\ (x+c)^3 &= (x+c)(x+c)(x+c) \\ &= (xx + xc + cx + cc)(x + c) \\ &= xxx + xxc + xcx + xcc + cxx + cxc + ccx + ccc\end{align}$$ We see that every term comes from choosing, inside each $(x+c)$, either the $x$ or the $c$. The term $xcx$ comes from the choice $(\underline{x}+c)(x + \underline{c})(\underline{x}+c)$ and the term $xxc$ from the choice $(\underline{x}+c)(\underline{x}+c)(x + \underline{c})$. The reason why I opted not to simplify is that: we can identify each term with a choice of some $x$ and some $c$ in the product of the factors $(x+c)$.
Now we can simplify our expression by joining together all terms that have the same exponent in $x$. Obviously the contribution of each term will depend on the number of times $x$ is written in it: $xcx$ contributes to $x^2$ because in $xcx$ the $x$ appears two times; on the other hand, each term comes from choosing a sequence of $x$ and $c$ from a fixed number of factors $(x+c)$, therefore each term will have the same number of letters, which in turn implies that having chosen the $x$ exactly $i$ times comes with having chosen the $c$ exactly $n-i$ times: picking the $x$ twice in $xcx$ means I picked $c$ only once, given that in the example $n = 3$.
This train of thought allows one to conclude what are the coefficientes $a_0, a_1, a_2$ e $a_3$ in $a_0c^3 + a_1c^2x + a_2cx^2 + a_3x^3$: $a_0$ is the number of ways you can pick $0$ times the $x$ in $(x+c)^3$, which is just one: inside each factor choose the $c$. $a_1$ is the number of ways in which you can pick $1$ time the $x$ (and thus $2$ times the $c$) in $(x+c)^3$, which is $3$. In a similar fashion we have $a_2 = 3$ and $a_3 = 1$:
$$\begin{align}(x+c)^3 &= a_0c^3 + a_1c^2x + a_2cx^2 + a_3x^3 \\ &= c^3 + 3c^2x + 3cx^2 + x^3\end{align}$$ The key idea here is that the coefficient of $x^i$ is related to choosing $i$ times the $x$. For the sake of simplicity I will take $c = 1$, so that multiplying the $x^i$ with $c^{n-i}$ actually does nothing.
If I have three balls of different colours, in how many ways can I pick two of them? We know the answer is $\binom{3}{2} = 3$, but let us pursue a different train of thought: assume we have three bags, each one of them with a different ball, and we are to count in how many ways you can choose, for each bag, to leave it alone or to remove its ball. For each bag, let us identify removing the ball with $x$ and identify not removing the ball with $1$. Having done that, $(x+1)(x+1)(x+1)$ is a compact way (if we use the distributive property) of writing all the different ways in which we can make the decisions of emptying some bags and leaving the others as they are! For example, the term $x\times1\times x$ encodes the choice of emptying the first and third bags, but leaving the second one as-is... But for our counting problem we don't really care about what balls are chosen, we just need to be sure we chose exactly $2$ balls, that is, we care about all terms that simplify to $x^2$! To count those, we just need to look at the coefficient of $x^2$ in the expansion of $(x+1)^3$. We have seen that the said coefficient is $3$, thus the answer is that there are exactly $3$ ways of doing that.
From this simple example we can see that setting $c=1$ made our counting easier.

This was a very simple example of a generating function. We can use generating functions to solve counting problems by finding some "useful" polynomials and manipulating them, so that in the end the answer we were looking for is the coefficient of some $x^i$. Think of the exponent of $x$ as a sort of "counter". Take this toy example: if I have $2$ red balls and $3$ blue balls, in how many ways can I pick $4$ balls?
Let us put all the red balls in a bag and all the blue balls in another bag and let us associate the red bag with $(1 + x + x^2)$: the exponent of $x$ represents how many balls I took out of that bag and the coefficient of $x^i$ (which is always $1$ in this case) represents the number of ways in which I can remove $i$ balls from the bag. It is obvious that there is only one way because the red balls are all the same. What is the polynomial that we should associate with the blue bag? Following a similar train of thought we get to $(1 + x + x^2 + x^3)$. The answer to our problem can be found by expanding $$(1 + x + x^2)(1 + x + x^2 + x^3)$$ and by reading the coefficient of $x^4$! Given that $$(1 + x + x^2)(1 + x + x^2 + x^3) = 1 + 2x + 3x^2 + 3x^3 + 2x^4 + x^5$$ we see the answer is $2$! You can take $4$ balls in two different ways: either take $1$ red ball and $3$ blue balls or $2$ red balls and $2$ blue balls. The other coefficients hold the answer to the questions in how many ways can we take $i$ balls by choosing from $2$ red and $3$ blue balls? In a more formal way, generating functions are series you associate to given sequences so that you can apply the machinery of series and of functions to the initial sequences.
Let us go over a less trivial example. In how many ways can we take $7$ balls from $10$ green balls and $4$ red balls, knowing we can only take an even number of green balls and given that each red ball has a different number on it? To solve this problem let us associate a polynomial to each set of balls. If the exponent of $x$ counts the number of balls we took, and because all green balls are the same, there is one way in which we take no green balls, as there is only one way in which we take $2,4,6,8$ or $10$ green balls, meaning we will associate the green balls with $$1 + x^2 + x^4 + x^6 + x^8 + x^{10}$$ On the other hand, the red balls are all different thus their polynomial will not be $$1 + x + x^2 + x^3 + x^4$$ In fact, we can choose a single red ball in $4$ different ways, two red balls in $6$ different ways, three red balls in $4$ different ways and the four balls in a single way, thus their polynomial will be $$1 + 4x + 6x^2 + 4x^3 + x^4 = (1 + x)^4$$ Evidently the polynomial we got to is the expansion of $(1+x)^4$, given that the train of thought of leaving each ball inside the bag ($1$) or removing it from the bag ($x$) holds. We now have the two polynomials we needed, we just need to multiply them together: $$\begin{align}(1+x)^4(1 + x^2 + x^4 + x^6 + x^8 + x^{10}) &= 1 + 4 x + 7 x^2 + 8 x^3 \\ &+ 8 x^4 + 8 x^5 + 8 x^6 + 8 x^7 + 8 x^8 \\ &+ 8 x^9 + 8 x^{10} + 8 x^{11} + 7 x^{12} \\ &+ 4 x^{13} + x^{14}\end{align}$$ and the answer is $8$ which is the coefficient of $x^7$. For the skeptical, let us check the answer: we are forced to take either $4$ or $6$ green balls ($8$ is too many and $2$ is not enough, we only have $4$ red ones). If we take $4$ green balls, we still have to take $3$ red balls, which we can do in $4$ different ways. If we take $6$ green balls we need to take a single red ball, which can be done in four different ways, amounting to a grand total of $4+4 = 8$ possible choices.
In a future post I will include more (interesting) counting problems to solve with generating functions and I will also show how to use generating functions to find explicit formulas for recurrence relations.