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 .