Problema
(Indicado a partir do 1º ano do E. M.)
(SANTOS, J.P.O; MELLO, M.P; MURARI, I.T.C.: Introdução à Análise Combinatória – Adaptado)
Considere os conjuntos [tex]A=\{a,b,c,d,e,f,g\}[/tex] e [tex]B=\{ 1,2,3,4,5,6,7,8,9,10\}[/tex]. Quantas são as funções injetivas [tex]F[/tex] de [tex]A[/tex] em [tex]B[/tex], satisfazendo [tex]F(a)=9, F(b)=1[/tex] e [tex]F(c)=10[/tex]?
Lembretes
✐ Uma função [tex] f:X \rightarrow Y [/tex] é dita injetiva (ou injetora) se, para quaisquer elementos do domínio [tex]X[/tex], a seguinte condição for satisfeita: elementos diferentes têm imagens diferentes.
Em símbolos: [tex]\, \forall \, x_1,x_2\in X, x_1\ne x_2 \Rightarrow f(x_1) \ne f(x_2)[/tex].
✐ Princípio Fundamental da Contagem, ou Princípio Multiplicativo: Se
- uma decisão D1 puder ser tomada de [tex] m_1 [/tex] maneiras distintas,
- uma decisão D2 puder ser tomada de [tex] m_2 [/tex] maneiras distintas,
- [tex]\cdots[/tex]
- uma decisão Dk puder ser tomada de [tex]m_k [/tex] maneiras distintas e
- todas essas decisões forem independentes entre si (isto é, a escolha de uma não muda a quantidade de possibilidades para a escolha de outra),
então o número total de maneiras de tomarmos sucessivamente essas [tex]k[/tex] decisões é igual ao produto
[tex]\qquad \qquad \boxed{m_1\times m_2 \times \cdots \times m_k} \, .[/tex]
(Se você não se lembra desse Princípio, seria interessante dar uma passadinha nesta Sala de Estudo.)
Solução
Como [tex]F(a)=9[/tex] , [tex]F(b)=1\,[/tex] e [tex]\,F(c)=10[/tex], então para definirmos uma função [tex]F[/tex] de [tex]A[/tex] em [tex]B[/tex] basta atribuirmos valores para [tex]F(d)[/tex], [tex] F(e)[/tex], [tex] F(f)[/tex] e [tex]F(g)[/tex]. Como [tex]F[/tex] de [tex]A[/tex] em [tex]B[/tex] é injetiva então:
- para [tex]F(d)[/tex] temos [tex]7[/tex] possibilidades de valores, pois três dos elementos do contradomínio já são imagens de [tex]a,\,b,\, c[/tex];
- para [tex]F(e)[/tex] temos [tex]6[/tex] possibilidades de valores, pois quatro dos elementos do contradomínio já são imagens de [tex]a,\,b,\,c,\, d[/tex];
- para [tex]F(f)[/tex] temos [tex]5[/tex] possibilidades de valores, pois agora cinco dos elementos do contradomínio já são imagens;
- para [tex]F(g)[/tex] temos [tex]4[/tex] possibilidades de valores, pois seis dos elementos do contradomínio já são imagens.
Portanto, pelo Princípio Multiplicativo, temos [tex] 7 \cdot 6 \cdot 5 \cdot 4 = \fcolorbox{black}{#eee0e5}{$840$}[/tex] funções injetivas [tex]F[/tex] de [tex]A[/tex] em [tex]B[/tex], satisfazendo [tex]F(a)=9, F(b)=1[/tex] e [tex]F(c)=10[/tex].
Solução elaborada pelos Moderadores do Blog.