Observe que existe abrirmos uma expressão da forma e obtemos na expressão a resposta de um problema de combinatória: "de quantas maneiras podemos selecionar dentre objetos sem que a ordem importe?". Será que isso pode acontecer em outros lugares? Sim! Observe a expressão
Temos também aqui, ao abrirmos outra expressão, a resposta para outro problema de combinatória: "de quantas maneiras podemos ordenar objetos em uma fila?". Será que existem outros problemas que podemos resolver "abrindo" expressões algébricas? Sim: este será um trabalho para as funções geratrizes.
Considere uma função (sim, começa do ). Então a função geratriz associada a essa sequência será
As próximas duas expressões podem ser deduzidas utilizando fórmulas de progressões geométricas. Mas como aparecem muito em funções geratrizes, deixaremos aqui:
Além disso,
.
Observação[]
Se e , então o coeficiente de de é
Exemplo[]
De quantas maneiras podemos coletar reais de pessoas, sendo que as primeiras pessoas podem dar real ou nada e a vigésima pessoa pode dar real , reais ou nada.
Solução: Sejam as quantidades de dinheiro que as pessoas podem dar. Observe que
onde podem ser ou , enquanto pode ser , ou .
Expressões dessa forma aparecem quanto abrimos o produto . O número de vezes que aparece é a nossa resposta, ou seja, o coeficiente de .
Considere e . Os coeficientes de de e chamaremos de e , respectivamente. Queremos o coeficiente de de .
Note que e (os outros 's são iguais a zero). O coeficiente de de será
Como os únicos 's diferentes de zero são , e , a expressão anterior se torna
Exemplo[]
De quantas maneiras podemos distribuir bolas idênticas em caixas distintas se a primeira caixa não pode ter mais do que bolas, mas qualquer número de bolas pode ir nas outras seis?
Solução: Sejam a quantidade de bolas que aparecem em cada caixa. Então
onde e . A resposta do nosso problema aparece se abrirmos
.
Queremos o coeficiente de dessa expressão. Vamos escrevê-la de modo que fique mais fácil de falarmos sobre seus coeficientes:
Sejam e e considere e os seus coeficientes, respectivamente.
Observe que e , enquanto os outros 's são iguais a . Além disso,
.
Com isso, o coeficiente de de será
Exemplo[]
Quantos são os subconjuntos de .
Solução: Aqui quem nos dá a resposta é . O coeficiente de nos diz quantos são os subconjuntos de de elementos. Por isso, vale a pena encontrar a soma de todos os coeficientes da nossa conta. Sabemos que
Daí a quantidade desejada será
Fórmula da Multisecção[]
Se
então
onde é a -ésima raiz primitiva da unidade.
Exemplo[]
Calcule .
Solução: Até podemos calcular essa expressão de um modo um mais rápido:
Mas vamos usar a Fórmula de Multisecção para mostrar como ela funciona. Repare que queremos calcular
.
Se considerarmos
,
segue que a soma que queremos calcular pode ser escrita como
Mas repare que . Daí nossa expressão se torna:
Será que vale a pena tirar o "mdc" e depois abrir essa expressão para simplificarmos nossa conta? Observe que os denominadores são parecidos com , e . Além disso, . Seria legal forçarmos essas coisas aparecerem.
Só falta fazermos algo parecido aparecer na parte debaixo da fração do meio. O que está atrapalhando? O que está multiplicando o . Para fazermos ele sumir, uma ideia é multiplicarmos em cima e embaixo da fração por : assim fazemos aparecer e podemos trocar por :
Como os fatores apareceram invertidos, podemos multiplicar por em cima e embaixo para fazermos três frações sumirem e ficarmos somente com uma:
Podemos em cada uma das três vezes que o aparece dentro dos colchetes. Mas na primeira vez que ele aparece parece mais simples usarmos que . Mas podemos usar nas outras duas vezes:
Ok, ainda aparece uma fração dentro do colchetes e a parte debaixo dela é . Uma ideia para fazermos ele sumir é multiplicarmos em cima e embaixo por . Com isso, fazermos aparecer . Daí nossa expressão se reescreve como
Vale a pena colocarmos em evidência nas duas últimas parcelas de dentro do colchetes:
Se lembrarmos que :
Como e são raízes de , segue que . Daí
Exemplo (IMO 1995)[]
Seja um primo ímpar. Quantos são os subconjuntos de elementos de tais que a soma dos seus elementos é divisível por ?
Observação: Você pode encontrar uma solução desse problema no canal do Luciano aqui.
Observação: Existe outra solução deste problema que pode ser encontrada aqui.
Solução: Poderíamos começar com a função geratriz
E na hora da multiplicação escolheríamos se, e somente se, pertence ao subconjunto. Mas ao fazermos isso, não saberíamos quantos elementos possuem cada subconjunto. O que fazer nesse caso? Colocar outra letra.
Vamos usar a letra para falar sobre a soma dos elementos e para falar sobre a quantidade de elementos do conjunto. Assim a função geratriz que vale a pena considerar será
Ao abrirmos a conta, cada termo poderá ser associado a um subconjunto de , onde o expoente de nos diz a soma dos elementos do subconjunto e nos diz quantidade de elementos do subconjunto.
Como ele pede a quantidade de conjuntos de elementos cuja soma dos elementos seja múltiplo de , devemos encontrar a soma dos coeficientes de , onde é múltiplo de . Considere o coeficiente de . Queremos calcular
Vamos chamar a soma de a soma dos coeficientes de tal que . Repare que isso nos dará um polinômio em . Para terminarmos o problema basta calcularmos o coeficiente de desse polinômio. Uma maneira de podermos calculá-la é pela Fórmula da Multisecção. Mas para isso, devemos fixar e fazer variar. Assim ao usá-la:
Na expressão é raiz -ésima primitiva da unidade. Se calcularmos esse somatório, nosso problema estará resolvido (pois aí basta calcularmos o coeficiente de ).
Para isso, vale a pena mexermos um pouco mais em . Observe que devemos mexer nessa expressão para . Para obtemos
E quanto a ? A nossa expressão se tornará:
Para calcularmos esse produto vale a pena entendermos melhor . Sabemos que
Como deixam todos os restos na divisão por possíveis (você pode saber mais sobre isso aqui) e o mesmo ocorre com , segue que são, em alguma ordem, e o mesmo vale para , segue que
Olha que lindo: o sumiu da nossa conta. Depois de limpar as lágrimas de tanta felicidade, vale a pena estudarmos melhor . Vamos chamar essa expressão de . Uma maneira de conhecermos bem um polinômio é entendermos bem as suas raízes. Observe que se, e somente se, para vale
Uma maneira de melhorarmos essa conta é tirarmos da parte debaixo da fração. E como podemos fazer isso? Uma maneira é fazermos aparecer lá (já que ). Para isso, vamos multiplicar a parte de cima e a debaixo por e assim
.
Como , as raízes de são . Com isso, existe uma constante tal que
.
Para entendermos a completamente, precisamos descobrir o valor de . Observe que se abrirmos a última igualdade, o termo independente do polinômio será . Já se voltarmos à definição inicial de , o termo independente será . Com isso, . Assim
.
Assim
Os termos multiplicando parecem um pouco com a fatoração de que é . Considere . Observe que é raiz de se, e somente se, é raiz de . Ou seja, as raízes de são . Com isso,
.
Como é ímpar, podemos dizer que . Daí
.
Ao voltarmos a ,
Agora sim temos condições de voltar a :
Por isso, para terminarmos o problema, basta encontrarmos o coeficiente de de . Observe que o coeficiente de de é . Já o de é . Por isso, o coeficiente da expressão desejada é
.
Exemplo (Cone Sul 2004)[]
Sejam , inteiros positivos. Em um tabuleiro , quadriculado em quadradinhos de lado , considere todos os caminhos que vão do vértice superior direito ao inferior esquerdo, percorrendo as linhas do quadriculado exclusivamente nas direções e .
Define-se a área de um caminho como sendo a quantidade de quadradinhos do tabuleiro que há abaixo desse caminho. Seja um primo tal que , onde representa o resto da divisão de por e representa o resto da divisão de por . Em quantos caminhos a área é um múltiplo de ?
Solução: Vamos nomear algumas coisas para podermos nos organizar melhor. Consideraremos aqui que é o número de colunas e é o de linhas.
Considere um caminho que vai do vértice superior direito ao inferior esquerdo, satisfazendo as condições do enunciado. Tomemos a quantidade de quadradinhos da -ésima coluna (da esquerda para a direta) que está embaixo do caminho.
Como o caminho só vai para baixo ou para a esquerda, segue que . Além disso, se tivermos 's satisfazendo estas condições, conseguiremos determinar um caminho.
Observe que a área do caminhos é .
Definamos e .
O problema aqui é que não sabemos mexer com funções geratrizes com . Para corrigirmos isto, consideraremos a sequência , para . Desta forma, a condição simplesmente se torna para .
Conseguimos agora escrever a área em função dos 's? Para isto, uma das maneiras é escrevermos os 's em função dos 's.
Note que
Se somarmos estas igualdades,
Desta forma, a área pode ser dada por
Para não carregarmos este , façamos e assim
Mas agora precisamos carregar ? Não. Basta fazermos . Assim,
Além disso,
Desta forma, para terminarmos o problema, basta encontrarmos o número de soluções de
tais que e
é um múltiplo de .
Precisamos então de uma função geratriz em que aparece nos expoentes e . Para isto, consideraremos
Como ficará depois que fizermos a distributiva? Observe que é formado por fatores. Em cada passo da distributiva, devemos multiplicar uma parcela de cada um dos fatores.
O primeiro fator vai contribuir com algum número da forma . Já o segundo irá contribuir com algum número da forma , enquanto o terceiro terá um da forma e assim por diante. Em geral, o -ésimo fator nos dará .
Desta forma, cada parcela de será da forma
que é justamente o que queríamos. Ou seja,
onde acabará sendo o número de soluções de
e
com . Em particular, é o número de caminhos de área conforme o enunciado. Porém queremos a quantidade de caminhos cuja área é um múltiplo de . Ou seja, queremos
Como podemos fazer para achar isso? Iremos usar a Fórmula da Multiseção:
onde é uma raiz -ésima da unidade. Queremos então o coeficiente de do somatório do lado esquerdo da igualdade. Para isto, basta descobrirmos o coeficiente de do somatório do lado direito da igualdade e depois dividirmos por .
Comecemos explorando melhor o somatório da direita. Calculemos os coeficientes de de . Para ,
O coeficiente de neste caso é o número de soluções de , com para , que é (conforme você pode descobrir aqui).
Vamos explorar para o caso em que . Para facilitar, lembre-se que . Desta forma,
Mas a parte legal é: conhecemos algo parecido com isso. Como é a raiz -ésima da unidade,
Assim, pode ser útil fazer:
Mas só podemos usar se o último termo do produtório tiver índice (ou ele for da forma ). Para conseguirmos aproximar por um múltiplo de , vamos fazer a divisão de por . Sejam e o quociente e o resto, respectivamente. Pelo Algoritmo da Divisão de Euclides,
com . E olha que legal, fizemos o resto aparecer. Façamos aparecer o produto dos termos até o com o índice . Para isto, multiplicaremos o numerador e o denominador de por
Desta forma, se reescreve como
Vamos nos preocupar em abrir
Comecemos com
Observe que, como , os restos da divisão de por são, em alguma ordem, .
Então
Além disso, como os restos da divisão de por são, em alguma ordem, , segue que
Pelo mesmo motivo,
Em geral,
para . Desta forma,
Com isso, se transforma em
E quanto ao produtório restante? Ao invés de nos esforçar para calculá-lo, vamos encontrar o seu coeficiente. Para que fique mais fácil nosso trabalho, façamos
Vamos entender os termos de para analisarmos os coeficientes de .
Observe que o produto possui fatores (lembre-se que ). Por isso, os termos, depois do desenvolvimento, serão , com .
Por outro lado, os termos de possuirão expoentes múltiplos de . Como
segue que o expoente de de é congruente a módulo , com .
Vejamos que é impossível aparecer o coeficiente neste caso, pois não dá para ter um resto com . Com efeito, segundo o enunciado
.
Desta forma, não tem nenhum termo não nulo com o expoente de igual a (mas isso quando ). Logo, o único que contribui para é . O coeficiente de , neste caso, é .
Logo, o número procurado de caminhos que satisfaz as condições do enunciado é .