Problema
(Indicado a partir do 2º ano do E. M.)
(BENJAMIN, A.T; QUINN, J.J. Proofs that Really Count: The Art of Combinatorial Proof)
Prove que, para quaisquer números naturais [tex]n\;[/tex] e [tex]\;k[/tex], com [tex] 1 \leq k \leq n[/tex], vale a seguinte igualdade:
[tex] k {\left( \begin{array}{c} n \\ k \end{array} \right)} = n {\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}[/tex].
Lembrete para Solução 1
(1) Se [tex]m[/tex] e [tex]p[/tex] são números naturais tais que [tex]p \leqslant m\, [/tex], definimos o número binomial denotado por [tex]\dbinom{m}{p}[/tex] da seguinte maneira:
[tex]\qquad \boxed{\dbinom{m}{p}=\dfrac{m!}{\left(m-p\right)!\, p!}}\, .[/tex]
Solução 1
Sejam [tex]n\;[/tex] e [tex]\;k[/tex] números naturais tais que [tex] 1 \leq k \leq n[/tex].
Usando o Lembrete 1, segue que:
[tex]\qquad k \left(\begin{array}{c} n \\ k \end{array} \right) = k \cdot \dfrac{n!}{k!(n-k)!}\\
\qquad k \left(\begin{array}{c} n \\ k \end{array} \right) = \dfrac{k \cdot n \cdot (n-1)!}{k \cdot (k-1)! \cdot (n-k)!}\\
\qquad k \left(\begin{array}{c} n \\ k \end{array} \right) = n \cdot \dfrac{(n-1)!}{(k-1!) \cdot (n-k)!}\\
\qquad \boxed{k \left(\begin{array}{c} n \\ k \end{array} \right) = n\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)} \,. [/tex]
Solução elaborada pelos Moderadores do Blog.
Lembretes para Solução 2
(2) Uma das maneiras de agruparmos elementos de um dado conjunto é escolhê-los levando-se em consideração apenas a sua natureza, sem se importar em que ordem eles foram escolhidos ou apresentados. Esse tipo de agrupamento de elementos é denominado uma Combinação simples. Particularmente, quando escolhemos [tex]p[/tex] dentre [tex]m[/tex] elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combinação simples de [tex]m[/tex] elementos tomados [tex]p[/tex] a [tex]p[/tex]. A quantidade desse tipo de agrupamentos é denotada por [tex]C_{m,\,p}[/tex] ou [tex]C_m^p\,[/tex] e equivale ao número binomial [tex]{\left( \begin{array}{c} m \\ p \end{array} \right)}[/tex]:
[tex]\qquad C_{m,\,p}=C_m^p={\left( \begin{array}{c} m \\ p \end{array} \right)}=\dfrac{m!}{(m-p)!\,p!} \text{ , com } m,p\in\mathbb{N} \text{ e }p\leqslant m[/tex].
(3) Princípio Fundamental da Contagem, ou Princípio Multiplicativo, para duas decisões:
Se uma decisão A pode ser tomada de [tex] m [/tex] maneiras distintas e, tomada essa decisão A, uma decisão B puder ser tomada de [tex] n [/tex] maneiras distintas, então a quantidade de maneiras de se tomar sucessivamente as decisões A e B é igual a [tex]~\boxed{ m \times n}\, . [/tex]
(Se você não se lembra desse Princípio, seria interessante dar uma passadinha nesta Sala de Estudo.)
Solução 2
Diferente da prova algébrica da Solução 1, procuraremos oferecer agora uma resolução combinatória mais intuitiva. Imagine que, em uma sala de aula, há [tex]n[/tex] alunos e queremos formar um Clube com [tex]k[/tex] alunos, dentre os quais um será o líder.
Podemos pensar de duas formas diferentes; vejamos:
- Dos [tex]n[/tex] alunos, vamos escolher [tex]k[/tex] alunos para o Clube, o que podemos fazer de [tex]C_n^k\,={\left( \begin{array}{c} n \\ k \end{array} \right)}[/tex] maneiras. Em seguida, escolhemos o líder, o que pode ser feito de [tex]k[/tex] formas distintas.
Logo, segue do Princípio Multiplicativo que podemos formar o Clube com líder de
[tex]\qquad \qquad k {\left( \begin{array}{c} n \\ k \end{array} \right)}[/tex] maneiras distintas.[tex]\qquad \textcolor{#800000}{(i)}[/tex] - Por outro lado, podemos primeiro escolher um dentre os [tex]n[/tex] alunos para ser o líder do Clube que será formado. Daí, sobram [tex]n-1[/tex] alunos e precisamos escolher dentre eles [tex]k-1[/tex] para completar a formação do Clube.
Segue do Princípio Multiplicativo que há
[tex]\qquad \qquad n\, C_{n-1}^{k-1}\,=n{\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}[/tex] possibilidades de montar o Clube.[tex]\qquad \textcolor{#800000}{(ii)}[/tex]
Portanto, por [tex]\textcolor{#800000}{(i)}[/tex] e [tex] \textcolor{#800000}{(ii)}[/tex], segue que [tex]\boxed{k {\left( \begin{array}{c} n \\ k \end{array} \right)} = n {\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}}[/tex].
Solução elaborada pelos Moderadores do Blog.