Até aqui você é capaz de resolver qualquer problema que envolva contagens de listas e subconjuntos seja usando todos
os valores disponíveis ou apenas uma parte deles. Uma coisa interessante da matemática é que alguns padrões surgem à
medida que se cria novos conceitos.
Um desses padrões foi descoberto em vários países em épocas diferentes, mas o nome que usaremos é atribuído ao
matemático francês Blaise Pascal e é denominado Triângulo de Pascal.
A relação é simples:
Ou seja, o número de subconjuntos que podemos formar com a adição de apenas 1 elemento no universo de opções é igual à
soma dos totais de subconjuntos de tamanho {k-1} das opções originais com a quantidade de subconjuntos
de tamanho {k} das {n} opções originais. Parece um pouco chato todo esse papo, mas se
certifique que está acompanhando.
Para verificar se o triângulo de Pascal é verdadeiro, vamos começar quebrando a equação e desenvolvendo suas formas
completas:
Não se assuste, foram apenas pequenas alterações feitas na formulação clássica de {n \choose k}. Escreva
em um papel para se certificar que entendeu.
A próxima parte é bem feia e pode assustar, mas é simplesmente uma soma de frações comum do estilo {\frac{a}{b} +
\frac{c}{d} = \frac{ad+cb}{bd}} aplicada equação para {{n \choose k-1} + {n \choose k}}:
Opa, chegamos em um ponto interessante! Temos ambos os divisores (a parte de baixo da divisão) iguais, agora
resta mostrar que os dividendos (a parte de cima da divisão) são iguais. Para que fique mais limpo,
trabalharemos com os dividendos separadamente. Agora só temos que provar essa pequena igualdade:
\displaystyle (n + 1)! = n!k + n!(n - k + 1)
Primeiramente, relembremos:
\displaystyle (n+1)! = (n+1)\underbrace{(n)(n-1)...3.2.1}_{ \ Isso \ aqui \ é \ igual \ a \ n!}
Tendo mostrado que essa propriedade é verdadeira, podemos ver como o Triângulo de Pascal é verdadeiro. Você com certeza viu isso, mas em formato de pirâmide. Aqui é um Triângulo Retângulo de Pascal.
{0}
{1}
{2}
{3}
{4}
{5}
{\cdots}
{k}
{0}
\tiny {0 \choose 0}
{1}
\tiny {1 \choose 0}
\tiny {1 \choose 1}
{2}
\tiny {2 \choose 0}
\tiny {2 \choose 1}
\tiny {2 \choose 2}
{3}
\tiny {3 \choose 0}
\tiny {3 \choose 1}
\tiny {3 \choose 2}
\tiny {3 \choose 3}
{4}
\tiny {4 \choose 0}
\tiny {4 \choose 1}
\tiny {4 \choose 2}
\tiny {4 \choose 3}
\tiny {4 \choose 4}
{5}
\tiny {5 \choose 0}
\tiny {5 \choose 1}
\tiny {5 \choose 2}
\tiny {5 \choose 3}
\tiny {5 \choose 4}
\tiny {5 \choose 5}
{\vdots}
{n}
\tiny {n \choose 0}
\tiny {n \choose 1}
\tiny {n \choose 2}
\tiny {n \choose 3}
\tiny {n \choose 4}
\tiny {n \choose 5}
\tiny {n \choose k}
Fazendo os devidos cálculos pela aplicação para todos os casos {{n \choose k}} teremos:
{0}
{1}
{2}
{3}
{4}
{5}
{\cdots}
{0}
{1}
{1}
{1}
{1}
{2}
{1}
{2}
{1}
{3}
{1}
{3}
{3}
{1}
{4}
{1}
{4}
{6}
{4}
{1}
{5}
{1}
{5}
{10}
{10}
{5}
{1}
{\vdots}
{\vdots}
{\ddots}
Para prosseguirmos, o professor Hammack usa os exercícios 3.5.13 e 3.5.14 como ferramentas para expor algumas
implicações do triângulo de Pascal.
Exercício 3.5.13: Suponha que {n,k \in \mathbb{Z}} e {0 \leq k \leq n}. De
posse da fórmula da combinação \tiny {{n \choose k} = \frac{n!}{k!(n-k)!}}, demonstre
que \tiny { {n \choose k} = {n \choose {n-k}} }.
A resposta para essa questão está no solucionário do próprio livro. Assumindo que { n,k \in \mathbb{Z}
} e { 0 \leq k \leq n }, aplicando o conceito das combinações podemos ver que
Exercício 3.5.14: Suponha que {n,k \in \mathbb{Z}} e {0 \leq k \leq n}.
Usando apenas a definição de combinação da página 31 (sem usar a fórmula), demonstre que \tiny { {n \choose
k} = {n \choose {n-k}} }.
Para responder essa questão nós vamos ter que abordar 3 casos possíveis. Quando temos { k = n },
estamos dizendo que queremos saber quantos subconjuntos de tamanho {n} podemos fazer com
{n} elementos, cuja resposta é claramente 1. Quando temos { k = 0 }, só temos 1 subconjunto
possível, que é o conjunto vazio {\emptyset}. Ou seja (se você leu o capítulo 02, você
entendeu o que a gente quis dizer aqui), {(k = 0 \ \lor \ k = n) \implies {n \choose k} = {n \choose n - k}
= 1}. Esses são os casos das laterais do triângulo de Pascal.
Agora teremos que trabalhar com os casos onde {0 < k < n}. Dentro dessa situação, temos o caso
onde {k = n/2}. Nesse caso, é simples ver que {{n \choose k} = {n \choose \frac{n}{2}} = {n
\choose n - \frac{n}{2}} = {n \choose \frac{n}{2}} = {n \choose n - k}}. Agora que já eliminamos todos os
casos mais evidentes, precisamos desenvolver uma lógica que contemple todos os demais.
Primeiro vamos pensar num conjunto qualquer {N}. Como estamos contando subconjuntos, se
{N} possuir elementos repetidos, isso não nos afeta, visto que um conjunto não leva em consideração a ordem
nem elementos repetidos. Para nos certificarmos, vamos criar um subconjunto {N^* = \{n \in N : n_k \neq n_w
\ \forall \ k \neq w \}}. Esse conjunto {N^*} não tem nenhum elemento repetido. Primeiro,
vamos contar todos os subconjuntos de tamanho {k} de {N^*}. Cada subconjunto
{k_i \subseteq N^*} será do tipo {\{n_1,n_2,n_3,...,n_k\}}. Uma vez que formamos um conjunto
{k_i} ainda teremos {n - k} elementos “sobrando” para criarmos novos subconjuntos.
Desse modo, teremos um total de {k(n-k)} possibilidades. Do outro lado do problema, vamos pensar no
caso para os subconjuntos de tamanho {(n-k)}. Eles serão do tipo
{\{n_1,n_2,...,n_{n-k}\}}. Similarmente, para cada subconjunto com {(n-k)} elementos,
teremos {n-(n-k)=n-n+k=k} elementos “sobrando” para construirmos novos subconjuntos, o que também
nos dá um total de {k(n-k)} subconjuntos possíveis. Como temos o mesmo número de possibilidades,
fica demonstrada a simetria entre {{n \choose k}} e {{n \choose n-k}} de acordo com
o enunciado da questão. {\blacksquare}
Com a demonstração dos exercícios 3.4.13 e 3.4.14, nós podemos ver que o triângulo de Pascal possui uma simetria.
Começando pelas laterais, as colunas onde {k = 0} e {k = n} são sempre iguais a
{1}. Mas além dessas, as colunas intermediárias também possuem uma simetria dada por {{n
\choose k} = {n \choose n-k}}. Isso quer dizer que as segundas colunas sempre serão iguais às penúltimas.
Do mesmo modo, as terceiras colunas sempre serão iguais às antepenúltimas. Nos casos onde o {k} é
ímpar, teremos uma coluna do meio que será a única sem uma repetição do valor.
A partir dessa simetria, os matemáticos perceberam uma relação entre os valores de cada elemento das linhas do
triângulo de Pascal com os coeficientes dos binômios do tipo {(a+b)^n}. Esse fato é chamado de
Teorema Binomial. Como o nome diz, um binômio é formado por quaisquer dois números (chamados de
monômios) {a} e {b} relacionados por uma soma.
Perceba como os coeficientes em vermelho seguem exatamente o padrão estabelecido pelo triângulo de Pascal. Nós vamos
partir dessa constatação para a definição do teorema binomial. Relaxa que a gente vai indo em partes.
Os primeiros e últimos termos do binômio estão à n-ésima potência, (deixaremos {a^{n-n}}
multiplicando o último termo e {b^{n-n}} o primeiro, apenas para que o desenvolvimento fique mais
claro, afinal, é um número elevado a zero e não mudará nosso resultado). Portanto:
Um fator importante para a notação mais limpa é que {a} está sempre elevado a {n}
subtraído a k-ésima entrada, e {b} está sempre elevado a k-ésima potência.
Pronto. Com isso já conseguimos definir nosso teorema.
Teorema Binomial Se {n} é um inteiro não negativo, então:
O autor deixa a demonstração como exercício para o capítulo 10. Nós vamos precisar de alguma ferramentas para poder
demonstrá-lo, então, aguarde um pouco para ver essa demonstração mais adiante nesse curso.
Deixe um comentário