Resumos LEIC-A
IST LEIC-AGitHub
Edit page

Teoremas e Cálculo Combinatório

Teoremas sobre Cálculo Combinatório e Funções Geradoras

Teorema 1

Para todo o n,m∈N tem-se:∑k=0n(k+mm)=(n+m+1m+1)\text{Para todo o } n, m \in \N \text{ tem-se:} \sum_{k=0}^{n} {k+m \choose m} = {n+m+1 \choose m+1}

Demonstração:

Base da induc¸a˜o:n←0∑k=00(k+mm)=(0+mm)=(m+1m+1)=1Hip. Ind.:∑k=0n(k+mm)=(n+m+1m+1)Passo de induc¸a˜on+1←n∑k=0n+1(k+mm)=∑k=0n(k+mm)+(n+1+mm)==(n+1+mm+1)+(n+1+mm)=(n+2+mm+1)\text{\textbf{Base da indução:}}\quad n \leftarrow0 \\ \sum_{k=0}^{0}{k+m \choose m} = {0+m \choose m} = {m+1 \choose m+1} = 1 \\ \text{\textbf{Hip. Ind.}}: \sum_{k=0}^{n} {k+m \choose m} = {n+m+1 \choose m+1}\\ \text{\textbf{Passo de indução}}\quad n+1 \leftarrow n\\ \sum_{k=0}^{n+1} {k+m \choose m} = \sum_{k=0}^{n} {k+m \choose m} +{n+1+m \choose m}=\\ ={n+1+m \choose m+1}+{n+1+m \choose m} = {n+2+m \choose m+1}

Teorema 2

Se U eˊ a func¸a˜o geradora da sucessa˜o un, enta˜o a func¸a˜o geradora da sucessa˜osn=∑i=0nui (somas parciais de un)eˊ:S(z)=U(z)1−z\text{Se U é a função geradora da sucessão } u_n\text{, então a função geradora da sucessão}\\ s_n=\sum_{i=0}^{n}u_i\qquad \text{ (somas parciais de }u_n)\\ \text{é:}\\ S(z)=\frac{U(z)}{1-z}

Demonstração:

Demonstração do segundo teorema

Teorema 3

Para todo o m∈N1,1(1−z)m=∑k=0+∞(k+m−1m−1)zk\text{Para todo o }m \in \N_1,\\ \frac{1}{(1-z)^m}=\sum_{k=0}^{+\infty} {k+m-1 \choose m-1}z^k

Demonstração:

Base da induc¸a˜o:n←01(1−z)1=11−z=∑k=0+∞(k+1−11−1)zk=∑k=0+∞zkHip. Ind.: 1(1−z)m=∑k=0+∞(k+m−1m−1)zkPasso de induc¸a˜om+1←m1(1−z)m+1=11−z×1(1−z)m==11−z×∑k=0+∞(k+m−1m−1)zk(uk)∑k=0+∞(∑i=0k(i+m−1m−1))zk==∑k=0+∞(k+mm)zk\text{\textbf{Base da indução:}}\quad n \leftarrow0 \\ \frac{1}{(1-z)^1}=\frac 1 {1-z} = \sum_{k=0}^{+\infty}{k+1-1 \choose 1-1}z^k = \sum_{k=0}^{+\infty}z^k\\ \text{\textbf{Hip. Ind.: }}\frac{1}{(1-z)^m}=\sum_{k=0}^{+\infty} {k+m-1 \choose m-1}z^k\\ \text{\textbf{Passo de indução}}\quad m+1 \leftarrow m\\ \frac 1 {(1-z)^{m+1}}=\frac 1 {1-z}\times \frac 1 {(1-z)^m}=\\ = \frac 1 {1-z} \times \sum_{k=0}^{+\infty} {k+m-1 \choose m-1}z^k\qquad(u_k)\\ \sum_{k=0}^{+\infty}\left( \sum_{i=0}^k{i+m-1 \choose m-1}\right)z^k =\\ = \sum_{k=0}^{+\infty}{k+m \choose m}z^k

exemplos de aplicação:

1(1−z)2=∑k=0+∞(k+2−12−1)zk=∑k=0+∞(k+1)zk=n+1\frac{1}{(1-z)^2} =\sum_{k=0}^{+\infty}{k+2-1 \choose 2-1}z^k=\sum_{k=0}^{+\infty}(k+1)z^k= n+1

e generalizando:

1(1−λz)m=∑k=0+∞[(k+m−1m−1)λk]zk ondeun=(n+m−1m−1)yn\frac 1 {(1-\lambda z)^m} = \sum_{k=0}^{+\infty} \left[{k+m-1 \choose m-1}\lambda^k\right]z^k \text{ onde} \\ u_n={n+m-1 \choose m-1}y^n

Problemas de Contagem

Seja n∈N1n \in \N_1 e l∈N.l \in \N. O número de soluções inteiras não negativas da equação:

x1+x2+x3+x4+⋯+xn=lx_1+x_2+x_3+x_4+\dots+x_n=l

é dado pela expressão:

(l+n−1n−1){l+n-1 \choose n-1}

Demonstração:

Demonstração para a fórmula usada para problemas de contagem

Exemplos:

Exemplo 1

Exemplo 2

Dicas para Problemas de Combinatória

warning

Esta secção é extra e alguma da informação abaixo não foi lecionada em aula.

Dividir Bolas por Caixas

Admita-se que temos um problema em que queremos dividir nn bolas por mm caixas de forma que todas as bolas são iguais, mas que as caixas são diferentes. Ou seja, se a caixa 1 tiver duas bolas, não interessa QUE bolas são, mas a caixa 1 tiver duas bolas é diferente da caixa 2 ter duas bolas.
Exemplos de enunciados deste tipo (referir ao exercício 2.2 da série 1):

  • Exercício 2: bolas = chocolates; caixas = pessoas;
  • Exercício 3: bolas = 29 unidades; caixas = nin_i;
  • Exercício 4: bolas = lugares parlamentares; caixas = partidos;
  • Exercício 7: bolas = chocolates; caixas = variedades.

Este tipo de enunciados pode ser descrito por uma equação matemática:

x1+x2+⋯+xm=nx_1 + x_2 + \cdots + x_m = n

As variáveis x1,x2,⋯ ,xmx_1, x_2, \cdots, x_m têm um domínio (normalmente N0\mathbb{N}_0 ou N+\mathbb{N}^+) e estamos interessados no número de soluções da equação, para x1,x2,⋯ ,xmx_1, x_2, \cdots, x_m nesse domínio.
Vamos recuperar a ideia de bolas em caixas. Considere-se um conjunto de 10 bolas. Alinhamos as bolas:

∘∘∘∘∘∘∘∘∘∘\circ \circ \circ \circ \circ \circ \circ \circ \circ \circ

Admita-se que queremos dividir estas 10 bolas por 3 caixas. Fazer isto equivale a dividir as bolas acima em 3 secções, como por exemplo, da seguinte forma:

∘∘∘∣∘∘∘∘∘∣∘∘\circ \circ \circ | \circ \circ \circ \circ \circ | \circ \circ

O que a divisão acima representa é que vão 3 bolas para a primeira caixa, 5 bolas para a terceira e 2 bolas para a última caixa.
Note-se que cada posicionamento das barras define uma única divisão possível das 10 bolas pelas 3 caixas. Desta forma, o nosso problema de descobrir o número de formas de dividir 10 bolas por 3 caixas equivale a descobrir o número de formas de colocar 2 barras nos espaços entre as 10 bolas. Como entre as 10 bolas há 9 espaços, esta quantidade é dada por

(92){9 \choose 2}

Mais genericamente, o número de formas de distribuir nn bolas por mm caixas, é igual ao número de formas de meter m−1m-1 barras em n−1n-1 espaços, que é dado por:

(n−1m−1){n-1 \choose m-1}

CONCLUSÃO: O número de soluções para a equação

x1+x2+⋯+xm=nx_1 + x_2 + \cdots + x_m = n

para x1,x2,⋯ ,xm∈N+x_1, x_2, \cdots, x_m \in \mathbb{N}^+ é dado pelo coeficiente binomial acima.

CUIDADO: A explicação até aqui só é válida se cada caixa tiver no mínimo uma bola. E se este não for o caso?

Caso importante: As variáveis têm domínio em N0\mathbb{N}_0 e não em N+\mathbb{N}^+.
Recuperemos o caso em que queremos distribuir as 10 bolas por 3 caixas, mas queremos que haja a possibilidade de haver caixas vazias.
Vamos usar um clever big brain trick para transformar este problema no que tínhamos anteriormente: Adicionamos 3 bolas ao nosso conjunto de bolas e resolvermos o nosso problema como anteriormente.

∘∘∘∘∣∘∣∘∘∘∘∘∘∘∘\circ \circ \circ \circ | \circ | \circ \circ \circ \circ \circ \circ \circ \circ

Como já vimos isto vai dar (122){12 \choose 2} soluções. Now here's the clever part: como adicionámos 3 bolas que não deviam estar aqui e cada caixa tem pelo menos uma bola, podemos tirar uma bola a cada caixa:

⋅∘∘∘∣⋅∣⋅∘∘∘∘∘∘∘\cdot \circ \circ \circ | \cdot | \cdot \circ \circ \circ \circ \circ \circ \circ

Note-se que, por exemplo, a caixa 2 já ficou sem bola nenhuma. Chegamos então à conclusão que o número de soluções neste caso é:

(n+m−1m−1){ n+m-1 \choose m-1}

(o +m+m vem das mm bolas que acrescentamos, e depois retiramos).

Se tivermos uma restrição do tipo xk≥3x_k \geq 3 (a caixa kk tem de ter pelo menos 3 bolas) a solução é muito simples: começamos por colocar 2 das nossas bolas na caixa kk, e resolvemos o problema do costume para n−2n-2 bolas.

Conjugando estas duas técnicas acima, ficamos capazes de resolver qualquer tipo de restrições do tipo xk≥tx_k \geq t:

  1. adicionar bolas A TODAS AS CAIXAS até todas as variáveis terem domínio em N+\mathbb{N}^+;
  2. colocar bolas nas caixas que precisam de ter pelo menos tt bolas para t>1t>1;
  3. distribuir as restantes bolas como no problema inicial.

NOTA DO AUTOR (João Rocha)

Se o que acabaste de ler te deixa confuso de alguma forma, das duas uma:

  1. apaga completamente esta informação da tua cabeça. O objetivo deste texto é dar intuição para este tipo de problemas que podem aparecer no teste mas não é de todo necessário saber isto. Pessoalmente isto ajuda-me a identificar a resposta mais rápido mas só vai piorar a tua situação se te deixar confuso;
  2. se achares que há alguma coisa que podia estar melhor explicada, ou encontrares algum erro, fala comigo e eu tento melhorar isso.

Caso contrário fico feliz por ajudar :)

BÓNUS:

Para problemas do tipo

x1+x2+⋯+xm≤nx_1 + x_2 + \cdots + x_m \leq n

é-nos dito que o número de soluções (em N+)\mathbb{N}^+) é

(n+mm){ n+m \choose m }

Porquê? Esta resposta parece bastante parecida á fórmula para o problema de igualdade (variáveis de domínio em N0\mathbb{N}_0)... Será que isto é curiosidade?
Claro que não. O truque é adicionar uma variável xm+1x_{m+1} que "deitamos ao lixo". Ou seja:

x1+x2+⋯+xm≤n⇔x1+x2+⋯+xm+xm+1=nx_1 + x_2 + \cdots + x_m \leq n \Leftrightarrow x_1 + x_2 + \cdots + x_m + x_{m+1} = n

com xm+1∈N0x_{m+1} \in \mathbb{N}_0.

Chegamos então à solução esperada:

(n+m+1−1m+1−1)=(n+mm){ n+m+1-1 \choose m+1-1} = {n+m \choose m }

Funções Geradoras com mais do que uma variável

Pode ser algo overkill para aprender mas reparem que não há nenhuma razão para uma função geradora ser só numa variável.

Não há muito que eu posso dizer sobre isto na teoria, portanto vou só dar um exemplo:
No exercício 2.2.17 da série 1, as nossas sequências são da seguinte forma:

1x10y11x20y2⋯1xk0yk1xk+11^{x_1} 0^{y_1} 1^{x_2} 0^{y_2} \cdots 1^{x_k} 0^{y_k} 1^{x_{k+1}}

De forma que:

y1+y2+⋯+yk=n∧x1+x2+⋯+xk+1=my_1 + y_2 + \cdots + y_k = n \quad \wedge \quad x_1 + x_2 + \cdots + x_{k+1} = m

com x1,xk+1∈N0,y1,x2,y2,⋯ ,xk,yk∈N+x_1, x_{k+1} \in \mathbb{N}_0, y_1, x_2, y_2, \cdots, x_k, y_k \in \mathbb{N}^+. Neste ponto podemos ir buscar do nosso génio combinatório e usar os métodos discutidos na secção acima, mas aqui queremos falar de geradoras portanto isso fica como exercício para o leitor

. Vamos então representar a geradora deste problema:

G(x,y)=11−x(y11−y)(x11−x)(y11−y)⋯(x11−x)(y11−y)11−x==xk−1yk(11−x)k+1(11−y)k==xk−1yk(∑i=0∞(k+ii)xi)(∑j=0∞(k−1+ii)yj)\begin{aligned} G(x,y) &= \frac{1}{1-x} \left( y\frac{1}{1-y} \right) \left( x\frac{1}{1-x} \right) \left( y\frac{1}{1-y} \right) \cdots \left( x\frac{1}{1-x} \right) \left( y\frac{1}{1-y} \right) \frac{1}{1-x} = \\ &= x^{k-1} y^k \left( \frac{1}{1-x} \right)^{k+1} \left( \frac{1}{1-y} \right)^k = \\ &= x^{k-1} y^k \left(\sum_{i=0}^\infty {k+i \choose i} x^i \right) \left( \sum_{j=0}^\infty {k-1+i \choose i} y^j \right) \end{aligned}

Estamos interessados no coeficiente em xmynx^m y^n que é portanto dado por:

(k+m−k+1m−k+1)(k−1+n−kn−k)=(m+1k)(n−1k−1){k+m-k+1 \choose m-k+1}{k-1+n-k \choose n-k} = {m+1 \choose k}{n-1 \choose k-1}