Um pouco de Combinatória
Leônidas O. Brandão - DCC/IME/USP
Objetivo: |
Para alunos de Matemática de segundo grau; |
Com qualquer um dos problemas propostos a seguir é
possível introduzir conceitos como permutação, arranjo,
combinação, relação de Stifel e Triângulo de
Pascal; |
Os alunos devem trabalhar em grupo para conseguirem obter
algumas relações sobre os problemas |
O professor deverá servir de consultor (aos grupos), podendo a cada
intervalo fixo de tempo, colocar em lousa os resultados que os grupos
já obtiveram e promovendo com a sala um pequena discução sobre o
assunto (isto servirá para que o grupo compare suas idéias com a dos
demais grupos)
|
|
Apresentaremos os problemas/desafios e também uma possível "sequência
dedutiva". Também apresentamos algumas formalizações sobre as relações
propostas.
Problemas
- (1) Quais são as possíveis configurações e quantas:
- em relação ao sexo de n filhos de um casal
- em relação ao lançamento de n moedas
- (2) Expandir (a+b)n
Resolução
(1) |
Os dois problemas são idênticos (apenas a motivação muda -
homem/mulher e cara/coroa). |
|
Testes |
|
n=1 |
{ h, m } |
n=2 |
{hh, hm, mh, mm} |
n=3 |
{hhh, hhm, hmh, hmm, mhh, mhm, mmh, mmm} |
n=4 |
{hhhh, hhhm, hhmh, hhmm, hmhh, hmhm, hmmh, hmmm,
mhhh, mhhm, mhmh, mhmm, mmhh, mmhm, mmmh, mmmm} |
|
|
Notação: A configuração k tipos h,
implica necessariamente em n-k tipos m. Logo
podemos usar apenas uma variável
|
|
n |
Eventos |
Total |
1 |
|
2 ->
1[0] 1[1] |
2 |
0[h] -> 1 |
1[h] -> 2 |
2[h] -> 1 |
|
4 -> 1[0]
2[1] 1[2] |
3 |
0[h] -> 1 |
1[h] -> 3 |
2[h] -> 3 |
3[h] -> 1 |
|
8 ->
1[0] 3[1]
3[2] 1[3] |
4 |
0[h] -> 1 |
1[h] -> 4 |
2[h] -> 6 |
3[h] -> 4 |
4[h] -> 1 |
|
16 ->
1[0] 4[1]
6[2] 4[3]
1[4] |
|
Tabela: eventos possíveis e total de movimentos
Conjectura 1: (Relação de Stifel -
Triângulo de Pascal) O k-ésimo elemento da linha n é igual a soma
dos elementos (k-1) e k da linha n-1
Demonstração: vamos representar o
conjunto de todos os elementos, com n letras, sendo
k do tipo [h] por
(k,n)[h].
Idéia: |
O total de possibilidades que podemos formar com
k
[h], para n+1 pode ser obtido
anexando um h ao final de cada elemento de
(k-1,n) , juntando-se todos os elementos do
tipo (k,n)
|
Qualquer elemento de (k,n+1)[h] tem n+1 parcelas
contendo k letras tipo h. Assim, (k,n+1)[h]
pode ser dividido em dois subconjuntos (partição):
- conjunto dos elementos que terminam em h
=> as
n primeiras letras devem ter k-1 letras
h
(k-1,n)[h] h;
- conjunto dos elementos que terminam em m
=> as
n primeiras letras devem ter k letras
h
(k,n)[h] m.
(k-1,n)[h] h \
----------- - \ = (k,n+1)[h]
/ ------------
(k,n)[h] m /
----------- -
|
| |
Conjectura 2: O total de possibilidades
(ou eventos) é
2n.
Contra-exemplo: Nenhum aluno deverá
encontrar.
Demonstração: Olhando os exemplos fica
difícil.
|
Outra idéia: olhe os nascimentos
N1, N2,
... ,Nn |
Assim, cada nascimento tem 2 possibilidades |
N1
N2
...
Nn |
/\ /\ ... /\
h m h m h m |
2 x
2 x
... x
2 = 2n |
|
Conjectura 3: Qualquer que seja n,
os coeficientes dos termos que equidistam do meio são iguais.
1[0] n[1] ... x[k] ... | ... x[n-k] ... n[n-1] 1[n]
x x
Demonstração:
Idéia: |
Para n=7, um evento do tipo [k]:=[3] pode ser
_hh__h_ que é idêntico à representação
m__mm_m. Por outro lado, para este último evento
existe um correspondente h__hh_h, que é um evento do
tipo [n-k]=[4]. Isto quer dizer que a quantidade de eventos do tipo [k]
é igual a quantidade de eventos tipo [n-k], pois eventos do tipo [n-k]
são equivalentes aos tipo [k], bastando tracar as letras
h<->m. |
|
A demonstração segue desta observação que o número de eventos com
k[h]. e
(n-k)[m]. são equivalente. Assim, invertendo as letras,
h<->
m, temos que
k[h] e (n-k)[h]
são equivalente.
Combinação: Mas qual a regra que fornece
o número de eventos do tipo (k[h],(n-k)[m]) ?
O fator que multiplica (k[h],(n-k)[m]) é igual ao número de diferentes
maneiras de combinarmos os n nascimentos tomados k a k.
Observações
- Neste ponto pode-se demonstrar tal fato com mais cuidado:
- Como formar permutações: N!;
- Arranjos de k elementos:
AN,k = N.(N-1). ... .(N-k+1)
= N! / (N-k)!;
(ordem importa => lista)
- Combinações de k elementos: cada elemento da combinação pode
resultar k! elementos no arranjo, logo,
CN,k = AN,k/k! = N! / ( (N-k)!k! )
(ordem não importa => conjunto)
- É também possível discutir Triângulo de Pascal: mostre estas
relações na tabela "eventos possíveis e total de movimentos" (os
números em negrito e azul);
- Agora que os alunos sabem a fórmula para combinação simples,
relembrê-os do resultado proposto pela conjectura 1:
talvez eles fiquem curiosos em demonstrar que
CN,k = CN-1,k + CN-1,k-1
(relação de Stifel)
(2) |
Expandir (a+b)n: este é um
caso muito interessante, no qual Combinação Simples aparece
naturalmente |
|
Testes |
|
(a+b)1 |
1a + 1 b |
(a+b)2 |
a2+ab+ba+b2=
1a2 + 2ab + 1b2
|
(a+b)3 |
(a+b)(a2 + 2ab + b2) =
a3+2a2b+ab2 +
a2b+2ab2+b3 =
1a3 + 3a2b +
3ab2 + 1b3
|
(a+b)4 |
(a+b)(a3+3a2b+3ab2+b3)=
a4+3a3b+3a2b2+
ab3 +
a3b+3a2b2+3ab3+
b4 = |
|
1a4b0 +
4a3b1 +
6a2b2 +
4a1b3 +
1a0b4
|
|
Por que os fatores desta "expansão" é análogo aos fatores do problema
anterior? É coincidência?
Conjectura 4: O Produto Notável
(a+b)n gera 2n parcelas
diferentes (que posteriormente são reagrupadas em apenas n+1
devido ao fato que a ordem dos fatores não altera o
produto), sendo ANÁLOGO ao problema anterior.
Demonstração: Novamente, olhando apenas
os exemplos fica difícil.
|
Outra idéia: |
(a+b)n =
(a+b) (a+b) ... (a+b)
|
Assim, cada parcela contribui com exatamente 2 possibilidades
(ou a ou b) |
|
|
(a+b)
(a+b)
...
(a+b) |
_|_ _|_ ... _|_
| | | | | |
a b a b a b
2 x
2 x
... x
2 = 2n |
|
o
a _______|_______ b
| |
a ___|___ b a ___|___ b
| | | |
a _|_ b a _|_ b a _|_ b a _|_ b
| | | | | | | |
o o * o * o o o
|
As configurações * produzem os elementos:
(a,b,a) e (b,a,a)
Portanto este problema é idêntico ao anterior:
cada um dos termos de (a+b)n que resultam
em parcelas do tipo akbn-k, são obtidos
combinando os n fatores (de cada termo) tomados k a
k, ou seja, existem Cn,k=n!/( k!(n-k)! )
termos akbn-k
.