PAPMEM_JAN_2020_Binominalia

Prévia do material em texto

Como mexer com coeficientes binomiais sem sujar as mãos
Roberto Imbuzeiro Oliveira∗
10 de Janeiro de 2020
1 Introdução
Imagine que você nunca viu um coeficiente binomial ou uma potência de dois na vida. Tudo
o que você conhece são as definições desses objetos.
Definição 1 (Coeficiente binomial e potência de 2) Dados n, k ∈N, o número(
n
k
)
conta o número de subconjuntos de tamanho k obtidos a partir de um universo com n objetos. Chamamos
ainda de 2n o número total de subconjuntos de um universo de n elementos.
Podemos observar que:
Teorema 1 Temos (nk) = 0 se k > n e (
n
0) = 1 sempre.
Prova: De fato, não pode haver um conjunto com k > n elementos dentro de outro com n
elementos. Por outro lado, o único conjunto com 0 elementos é o vazio. 2
Além disso:
Teorema 2 Para qualquer n, a soma dos valores de (nk) para k = 0, 1, . . . , n é igual a 2
n.
Prova: Com efeito, podemos partir o conjunto de subconjuntos de
[n] := {1, 2, 3, . . . , n}
em categorias de acordo com seus tamanhos k = 0, 1, . . . , n. A categoria dos subconjuntos
com k elementos tem exatamente (nk) elementos. Pelo princı́pio aditivo da contagem, pode-
mos contar quantos subconjuntos há no total apenas somando os números de elementos nas
diferentes categorias. 2
∗IMPA. rimfo@impa.br
1
Eis um outro resultado que podemos provar sem nem olhamos pras fórmulas.
Teorema 3 Para todos n, k ∈N com n ≥ 1,(
n
k
)
=
(
n
n− k
)
.
Prova: Vamos supôr que 0 ≤ k ≤ n, porque em caso contrário tudo fica fácil. O ponto é que,
escolhido um subconjunto de k elementos, escolhemos unicamente um subconjunto de n− k
elementos (o complementar) e vice-versa. Ou seja, há uma bijeção natural entre subconjuntos
com k e n− k elementos. (Um aluno meu resumiu este resultado como sendo: escolher quem
fica no time é a mesma coisa que escolher quem não fica!) 2
Os três teoremas que escrevemos acima não envolvem as fórmulas usuais para os coeficientes
binomiais. Eles partem estritamente das definições que demos.
Até onde podemos chegar com essa ideia de mexer com os coeficientes binomiais sem
”abrir” os famigerados fatoriais? Veremos que é possı́vel ir bastante longe e que até mesmo
a fórmula para (nk) pode ser deduzida diretamente das definições e dos dois princı́pios de
contagem (aditivo e multiplicativo). Nossa inspiração e vários dos nossos problemas vêm de
[1, Capı́tulo 6].
2 Times e capitães
Nesta seção, veremos vários probleminhas relacionados ao resultado abaixo.
Teorema 4 Para todos n ∈N, k ∈N\{0}:(
n
k
)
k = n
(
n− 1
k− 1
)
.
(Pare para pensar nele antes de seguir!)
Uma dica para solucionar este tipo de problema é pensar em times (grupos de pessoas) e
em capitães (pessoas especiais selecionadas dentro de cada time. De fato:
O coeficiente binomial (nk) conta quantos times com k pessoas podemos formar a partir de um universo
de n indivı́duos. O fator de k adicional nos diz de quantas maneiras podemos escolher uma pessoa
especial – um capitão – dentro do time.
Pensando assim, não é difı́cil provar o teorema.
Prova: (do Teorema 4) O lado esquerdo da expressão nos diz que, se escolhemos o time pri-
meiro e depois o capitão, temos um total de (nk) k possibilidades. Outra maneira de fazer essa
mesma escolha é começar indicando um capitão (n possibilidades) e depois o restante do time
(k− 1 pessoas a mais dentre as n− 1 pessoas restantes). Logo o número de escolhas para o
time-com-capitão também é igual a n (n−1k−1). 2
Este teorema pode ser usado para achar uma recursão e uma fórmula para os números
binomais. Nossa ideia é não fazer isso, pelo menos por enquanto!
Vejamos alguns outros problemas relacionados ao acima.
2
Exercı́cio 1 Prove de forma análoga ao teorema anterior as identidades abaixo, para n, k ∈ N\{0}
quaisquer.
1. (nk) k = (n− k + 1) (
n
k−1);
2. se n ≥ 2, k (k− 1)(nk) = n(n− 1)(
n−2
k−2).
Um problema um pouco mais sofisticado é dado abaixo.
Teorema 5 Para todos n ≥ 1,
n2n−1 =
n
∑
k=1
k
(
n
k
)
.
Prova: Podemos interpretar o lado direito da seguinte forma. Para formar um time-com-
capitão, sem número pré-determinado de pessoas, primeiro escolhemos uma dentre as n pes-
soas para ser o capitão e depois escolhemos um subconjunto de tamanho qualquer dentre as
n− 1 restantes (esse subconjunto pode ser até o vazio: o time pode ter só o capitão).
Para achar o lado direito, note que o número total de pessoas no time, incluindo o capitão,
é um número qualquer k ∈ {1, . . . , n}. Para cada valor desdes de k, já sabemos que k(nk) conta
o número de escolhas para times com k pessoas e um capitão selecionado dentro do time.
Somando em k, vemos, pelo princı́pio aditivo da contagem, que vale a fórmula acima. 2
Exercı́cio 2 Prove que, se n ≥ 2,
n (n− 1) 2n−2 =
n
∑
k=2
k (k− 1)
(
n
k
)
.
Exercı́cio 3 (Para casa) Invente problemas coma ideia de times e capitães!
3 Somas de coeficientes binomiais
Dizem que um tal de Pascal provou a fórmula abaixo.
Teorema 6 (Triângulo de Pascal) Para todos n, k ∈N com n, k ≥ 2:(
n
k
)
=
(
n− 1
k− 1
)
+
(
n− 1
k
)
.
Seria fácil provar isso a partir da fórmula dos coeficientes. No entanto, você não conhece a
fórmula! O que fazer? Como provar essa relação a partir do significado dos coeficientes?
Depois de pensar um pouco, muitos alunos chegam à seguinte solução.
Prova: (do Teorema 6) Vamos fazer a prova para n ≥ 2 porque o caso n = 1 é fácil.
O lado esquerdo da expressão conta quantos conjuntos de k elementos podemos fazer a
partir dos números {1, 2, . . . , n}. Podemos dividir estes conjuntos em dois grupos:
• os que não contêm o número n;
• os que contêm o número n.
3
O primeiro grupo consiste de subconjuntos de tamanho k de {1, . . . , n− 1}; portanto, há (n−1k )
elementos no primeiro grupo.
Os conjuntos no segundo grupo têm a forma S ∪ {n}, onde S ⊂ {1, . . . , n− 1} tem k− 1
elementos. Há (n−1k−1) escolhas possı́veis para S; portanto, o segundo grupo tem (
n−1
k−1) elemen-
tos. 2
A ideia da prova acima, como em muitas outras envolvendo o princı́pio aditivo, é quebrar o
conjunto de possibilidades em partes e contar as partes separadamente. No problema abaixo,
essa ideia aparece de forma bem diferente.
Proposição 1 Para qualquer n ∈N, (
2n
2
)
= 2
(
n
2
)
+ n2.
Prova: A definição de coeficiente binomial nos diz que(
2n
2
)
= número de escolhas para 1 ≤ i < j ≤ 2n.
Observe que há três grupos possı́veis e mutuamente excludentes de possibilidades para estas
escolhas.
1. 1 ≤ i < j ≤ n - isto corresponde a escolher um par entre 1 e n, logo há (n2) escolhas
possı́veis nesta classe.
2. n + 1 ≤ i < j ≤ 2n - isto corresponde a escolher um par no conjunto {n + 1, . . . , 2n}.
Como este conjunto tem n elementos, temos as mesmas (n2) escolhas possı́veis neste caso.
3. 1 ≤ i ≤ n, n + 1 ≤ j ≤ 2n. Há n escolhas possı́veis para i e, feita esta escolha, n escolhas
possı́veis para j. Portanto há n2 escolhas possı́veis de pares nesta classe.
Obtemos a proposição somando as contribuições de cada classe. 2
Exercı́cio 4 Prove de forma similar que, para quaisquer n, m naturais:(
n + m
2
)
=
(
n
2
)
+
(
m
2
)
+ n.m.
Exercı́cio 5 Prove de forma similar que, para qualquem n ≥ 1 natural:(
2n + 2
n + 1
)
=
(
2n
n + 1
)
+ 2
(
2n
n
)
+
(
2n
n− 1
)
.
Exercı́cio 6 Ache uma fórmula semelhante para (3n3 ).
Vejamos agora um problema bem mais desafiador.
Teorema 7 Para quaisquer n, r ∈N\{0},(
r
r
)
+
(
r + 1
r
)
+ · · ·+
(
n
r
)
=
(
n + 1
r + 1
)
.
4
Vale a pena pensar um pouco neste problema antes de se aventurar numa solução. De
onde pode vir esta soma? Uma ideia é combinar a prova do Triângulo de Pascal com a do
”time”.
Prova: (do Teorema 7) O lado direito da expressão conta de quantas maneiras podemos formar
um time com r + 1 pessoas a partir de um grupo com n + 1 indivı́duos. Vamos imaginar que
as pessoas têm números indo de 1 a n + 1 e que o capitão do time é automaticamente o cara
de número mais alto. Nestecaso, uma vez escolhido o time, o capitão já está determinado (e
por isso há apenas (n+1r+1) possibilidades).
Apesar disso, podemos imaginar que escolhemos o time começando pelo capitão e depois
escolhendo os outros membros. Como o time tem r + 1 elementos, o capitão do time (o maior
elemento do conjunto) deverá necessariamente ter um número k ∈ {r + 1, . . . , n + 1}.
Escolhido o capitão com número k, os demais r membros do grupo deverão ser escolhidos
dentre os números {1, . . . , k − 1}, de modo que o capitão tenha o maior número no time.
Portanto,
se o capitão tem número k, há (k−1r ) escolhas para o resto do time.
Para calcular o total de escolhas, basta então somar o número de escolhas para os diferentes
valores k = r + 1, r + 2, . . . , n + 1:
n+1
∑
k=r+1
(
k− 1
r
)
=
(
r
r
)
+
(
r + 1
r
)
+ · · ·+
(
n
r
)
.
Portanto, a soma é igual a (n+1r+1), como querı́amos demonstrar. 2
4 Por que os coeficientes binomiais aparecem no binômio de New-
ton?
Você ainda não sabe a fórmula dos coeficientes binomiais, mas talvez se lembre do binômio
de Newton.
∀a, b ∈ R : (a + b)n =
n
∑
k=0
(
n
k
)
akbn−k.
Como podemos argumentar que esta fórmula vale? Melhor ainda: como podemos entender
a aparição de objetos de contagem de conjuntos nesta fórmula?
A chave para isso está em pensar na propriedade distributiva da multiplicação e no signi-
ficado dos coeficientes. Obviamente, temos:
(a + b)n = (a + b)(a + b) . . . (a + b)︸ ︷︷ ︸
n vezes
. (1)
Quando expandimos o produto, o que fazemos é escolher um termo a ou b para cada fator.
O resultado é é uma sequência de fatores a ou b com a seguinte cara:
abaabb . . . ab,
o que pode ser reescrito como
akbn−k
5
se tomamos k como sendo número de a’s escolhidos na sequência. Veja que 0 ≤ k ≤ n.
Dado k, quantas são as escolhas de termos a ou b que resultam na expressão akbn−k? É fácil
ver que, para chegarmos a esta expressão, temos que decidir escolher o termo a em exatamente k
fatores do produto na equação (1). Como são n fatores, há exatamente (nk) escolhas que levam
a este resultado. Portanto,
(a + b)n = ∑ (todas as sequências aba . . . com n termos a ou b)
=
n
∑
k=0
(todas as sequências com k termos a e n− k termos b)
=
n
∑
k=0
(
n
k
)
akbn−k.
Exercı́cio 7 Você consegue generalizar o raciocı́nio acima para o trinômio de Newton (a + b + c)n?
Isso envolverá os coeficientes trinomiais.
5 Coeficientes binomiais e permutações
Para terminar, finalmente provaremos a fórmula conhecida para o coeficiente binomial (só
que com uma pegadinha!).
Teorema 8 Dados k, n ∈N com 1 ≤ k ≤ n,(
n
k
)
k! (n− k)! = n!.
Esta fórmula está escrita de um jeito que não é o usual. Não é à toa: vamos prová-la sem saber
qual é a fórmula do fatorial! De fato, quero que você use apenas a definição abaixo.
Definição 2 Dado n ∈ N, n! é o número de permutações de um conjunto de n elementos, ou seja, é o
número de maneiras em que podemos ordenar n elementos distintos.
Você consegue enxergar a relação entre essa definiçãoe o teorema? Pense um pouco antes
de ler a prova.
Prova: (do Teorema 8) O lado direito da expressão conta as permutações de n elementos, por
exemplo 1, . . . , n. Para escrever uma permutação dessas – digamos a1, a2, . . . , an, –, podemos
proceder da seguinte maneira:
1. Primeiros escolhemos o conjunto S = {a1, . . . , ak} com os os k primeiros elementos da
permutação, mas sem escolher a ordenação entre eles ou entre os elementos restantes. Temos
aqui (nk) possibilidades.
2. Depois escolhemos uma ordem para os elementos de S e para isso temos k! possibilida-
des (já que |S| = k).
3. Por fim, ordenamos os n− k elementos restantes e para isso temos (n− k)! possibilida-
ades.
6
Com alguma atenção, podemos ver que todas as escolhas acima levam a permutações de
n elementos distintas, e que toda permutação pode ser escolhida pelo processo acima.
Concluı́mos que é possı́vel permutar os números de 1 a n de exatamente(
n
k
)
k! (n− k)! maneiras diferentes,
portanto este número é igual a n!. 2
Referências
[1] Paul Zeitz. The Art and Craft of Problem Solving (2nd edition). John Wiley and Sons, Inc
(2007).
7
	Introdução
	Times e capitães
	Somas de coeficientes binomiais
	Por que os coeficientes binomiais aparecem no binômio de Newton?
	Coeficientes binomiais e permutações