Home » Materiais » Combinatória

Links

    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   
    0[h] -> 1
    1[h] -> 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 .