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 n e k, com 1≤k≤n, vale a seguinte igualdade:
k(nk)=n(n−1k−1).
Lembrete para Solução 1
(1) Se m e p são números naturais tais que p⩽m, definimos o número binomial denotado por \dbinom{m}{p} da seguinte maneira:
\qquad \boxed{\dbinom{m}{p}=\dfrac{m!}{\left(m-p\right)!\, p!}}\, .
Solução 1
Sejam n\; e \;k números naturais tais que 1 \leq k \leq n.
Usando o Lembrete 1, segue que:
\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)} \,.
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 p dentre m elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combinação simples de m elementos tomados p a p. A quantidade desse tipo de agrupamentos é denotada por C_{m,\,p} ou C_m^p\, e equivale ao número binomial {\left( \begin{array}{c} m \\ p \end{array} \right)}:
\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.
(3) Princípio Fundamental da Contagem, ou Princípio Multiplicativo, para duas decisões:
Se uma decisão A pode ser tomada de m maneiras distintas e, tomada essa decisão A, uma decisão B puder ser tomada de n maneiras distintas, então a quantidade de maneiras de se tomar sucessivamente as decisões A e B é igual a ~\boxed{ m \times n}\, .
(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á n alunos e queremos formar um Clube com k alunos, dentre os quais um será o líder.
Podemos pensar de duas formas diferentes; vejamos:
- Dos n alunos, vamos escolher k alunos para o Clube, o que podemos fazer de C_n^k\,={\left( \begin{array}{c} n \\ k \end{array} \right)} maneiras. Em seguida, escolhemos o líder, o que pode ser feito de k formas distintas.
Logo, segue do Princípio Multiplicativo que podemos formar o Clube com líder de
\qquad \qquad k {\left( \begin{array}{c} n \\ k \end{array} \right)} maneiras distintas.\qquad \textcolor{#800000}{(i)} - Por outro lado, podemos primeiro escolher um dentre os n alunos para ser o líder do Clube que será formado. Daí, sobram n-1 alunos e precisamos escolher dentre eles k-1 para completar a formação do Clube.
Segue do Princípio Multiplicativo que há
\qquad \qquad n\, C_{n-1}^{k-1}\,=n{\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)} possibilidades de montar o Clube.\qquad \textcolor{#800000}{(ii)}
Portanto, por \textcolor{#800000}{(i)} e \textcolor{#800000}{(ii)}, segue que \boxed{k {\left( \begin{array}{c} n \\ k \end{array} \right)} = n {\left( \begin{array}{c} n-1 \\ k-1 \end{array} \right)}}.
Solução elaborada pelos Moderadores do Blog.