Ir ao conteúdo principal

Matemática Discreta: notas de aula

Ricardo Machado

Seção 6.4 Combinações Simples

Subseção 6.4.1 Nota Histórica

A primeira descrição conhecida sobre coeficientes binomiais (equivalente a combinações simples) está em um dos livros do matemático indiano do século X, Halayudha. O livro possui o título Mṛta-Sañjīvanī e é conhecido como um comentário do livro Chandaḥśāstra do poeta e matemático indiano, Pingala (dos séculos III/II A.C.). O comentário de Halayudha inclui uma apresentação do triângulo de Pascal (chamado meruprastāra).
Por volta de 1150, o matemático indiano Bhāskarācārya (Bhaskara II) fez uma exposição dos coeficientes binomiais em seu livro Līlāvatī.
Figura 6.4.1. Līlāvatī de Bhāskarācārya, traduzido para inglês por Patwardhan, Naimpally e Shyam Lal Singh.

Subseção 6.4.2 Combinações Simples

Em determinadas situações, precisamos escolher algumas opções, sem que a ordem seja importante. Confira o exemplo a seguir.

Exemplo 6.4.2.

De quantas maneiras é possível fazer uma salada de frutas, usando quatro frutas distintas, se temos disponíveis as frutas: abacaxi, banana, maçã, mamão, manga e uva?
Solução.
São 6 opções para a primeira fruta, 5 opções para a segunda fruta, 4 opções para a terceira fruta, e finalmente, 3 opções para a última fruta.
Note que, dessa maneira a ordem está sendo levada em consideração. Como cada escolha de \(4\) frutas pode ser ordenada de \(P_4\) maneiras, dividindo \(6\times 5\times 4\times 3\) por \(P_4\) passamos a contar cada salada exatamente uma vez. A resposta é dada por
\begin{equation*} \frac{6\times 5\times 4\times 3}{P_4} = 15. \end{equation*}

Tecnologia 6.4.3.

No Sage, podemos obter uma lista com todos os subconjuntos de {1, 2, 3, 4, 5, 6}, tomados 4 a 4. Basta usar o seguinte código:

Definição 6.4.4.

O número de formas de escolher \(p\) elementos, dentre \(n\) elementos disponíveis, sem que a ordem importe, é chamado de número de combinações de \(n\) elementos, tomados \(p\) a \(p\).
Observe que, o número de subconjuntos com \(p\) elementos, de um conjunto com \(n\) elementos é exatamente o número de combinações de \(n\text{,}\) tomados \(p\) a \(p\text{.}\) As notações para o número de combinações de \(n\text{,}\) \(p\) a \(p\) são dadas por:
\begin{equation*} C_n^p, ~~ C_{n, p}, ~~ C(n, p) ~~\text{ ou }~~\binom{n}{p}. \end{equation*}
Temos \(n\) modos de escolher o primeiro elemento, \(n-1\) modos de escolher o segundo elemento, e assim sucessivamente, até \(n-p+1\) modos de escolher o \(p\)-ésimo elemento.
Agora observe que contamos muito mais agrupamentos do que deveríamos, pois para conjuntos, a ordem não importa, portanto precisamos dividir pelo número de formas de ordenar estes \(p\) elementos que escolhemos de forma ordenada, ou seja, por \(p!\text{.}\) Assim:
\begin{equation*} C(n,p) = \frac{n(n-1)\cdots(n-p+1)}{p!} = \frac{n(n-1)\cdots(n-p+1)}{p!} \cdot \frac{(n-p)!}{(n-p)!} \end{equation*}
Fazendo as contas concluímos que
\begin{equation*} C(n,p) = \frac{n!}{p!(n-p)!}. \end{equation*}

Tecnologia 6.4.6.

\(C_n^p\) pode ser calculado no Sage com o código binomial(n, p). Para abreviar vamos usar C(n, p) = binomial(n, p). Teste o código abaixo, para o caso \(n=8\text{,}\) \(p=3\text{.}\)

Exemplo 6.4.7.

Uma criança possui 5 figurinhas distintas e outra criança possui 7 figurinhas distintas. Se as figurinhas da primeira criança são todas diferentes das figurinhas da segunda criança, de quantas maneiras é possível trocar 4 figurinhas pertencentes a primeira criança com 4 pertencentes a segunda?
Solução.
A primeira criança pode escolher suas 4 figurinhas de \(C_5^4\) maneiras e a segunda criança pode escolher suas 4 figurinhas de \(C_7^4\) maneiras. Portanto, o número de maneiras de realizar a troca é
\begin{equation*} C_5^4 \times C_7^4 = 175. \end{equation*}

Exemplo 6.4.8.

Um Juiz dispõe de 11 mulheres, das quais somente 4 são advogadas.
  1. Para formar um único júri com 9 juradas. Qual é o número de formas de compor o júri, com pelo menos 2 advogadas?
  2. Para formar um único júri com 6 juradas. Qual é o número de formas de compor o júri, com pelo menos 2 advogadas?
Solução.
item a) Basta escolher 9 juradas, pois pelo menos duas serão advogadas. Isto pode ser feito de \(C_{11}^9=55 \) maneiras.
item b) Se escolhermos diretamente 6 juradas, dentre as 11 mulheres disponíveis, estaremos contando os casos em que não temos pelo menos duas advogadas. Precisamos contornar este problema.
Para garantir que estamos contando todos os casos em que pelo menos duas advogadas foram selecionadas, vamos separar em três casos. 1º vamos contar o número de maneiras de selecionar 2 advogadas e 4 não advogadas. 2º vamos contar o número de maneiras de selecionar 3 advogadas e 3 não advogadas. 3º vamos contar o número de maneiras de selecionar 4 advogadas e 2 não advogadas. Como os casos são disjuntos, pelo Princípio aditivo a resposta é
\begin{equation*} C_4^2\times C_7^4 + C_4^3\times C_7^3 + C_4^4\times C_7^2 = 371. \end{equation*}
No Sage, esse cálculo pode ser feito da seguinte maneira:

Exemplo 6.4.9.

De quantos modos podemos dividir 12 pessoas em três grupos de quatro pessoas cada?
Solução.
Para o primeiro grupo, temos um total de \(C_{12}^4 \) maneiras de selecionar as 4 pessoas.
Para o segundo grupo temos um total de \(C_8^4 \) maneiras de selecionar as 4 pessoas.
Para o terceiro grupo temos um total de \(C_4^4 \) maneiras de selecionar as 4 pessoas.
Como a ordem dos grupos não importa, precisamos dividir por \(3!\) Portanto a resposta é
\begin{equation*} \frac{C_{12}^4\times C_8^4\times C_4^4}{3!} = 5775. \end{equation*}

Exercícios 6.4.3 Exercícios

1.

Quantas diagonais possuem um polígono de \(n\) lados?
Resposta.
\(\dfrac{n(n-3)}{2} \)
Solução.
Cada vértice pode ser ligado a \(n-3\) outros vértices por meio uma diagonal, pois o vértice nem pode ser ligado a ele mesmo, nem aos seus dois vértices adjacentes, usando diagonais. Como são \(n\) vértices ficamos com \(n(n-3)\) diagonais, mas elas foram contadas duas vezes, portanto a resposta é
\begin{equation*} \frac{n(n-3)}{2}. \end{equation*}

2.

Quantas são as pedras de um dominó comum?
Resposta.
28
Solução.
As pedras de um dominó possuem dois números que podem ter valores de 0 até 6. Dessas pedras, 7 possuem os dois números iguais. Para formar uma pedra com dois números diferentes, temos \(C_7^2\) modos de escolher os números. Portanto o número de pedras de um dominó comum é
\begin{equation*} 7 + C_7^2 = 28. \end{equation*}

3.

(UFPE 2012) As pedras de um dominó usual são compostas por dois quadrados, com 7 possíveis marcas (de zero pontos até 6 pontos). Quantas pedras terá um dominó se cada quadrado puder ter até 9 pontos? Veja no desenho abaixo um exemplo de uma nova pedra do dominó.
Resposta.
55
Solução.
As pedras desse dominó possuem dois números que podem ter valores de 0 até 9. Dessas pedras, 10 possuem os dois números iguais. Para formar uma pedra com dois números diferentes, temos \(C_{10}^2\) modos de escolher os números. Portanto o número de pedros desse dominó é
\begin{equation*} 10 + C_{10}^2 = 55. \end{equation*}

4.

(UFPE 2001) Quantos são os paralelogramos com lados sobre os segmentos da figura seguinte, onde os segmentos que não se interceptam são paralelos.
Resposta.
90
Solução.
Podemos prolongar os segmentos que definem os lados dos paralelogramos conforme a figura abaixo:
Figura 6.4.10. Paralelogramos com prolongamento de segmentos.
Observe que escolher dois segmentos em cima e dois segmentos do lado esquerdo define um único paralelogramo. Observe também que cada paralelogramo da figura corresponde a dois segmentos na parte de cima e dois segmentos do lado esquerdo. Portanto, a resposta é o número de maneiras de escolher 2 dentre 6 segmentos na parte de cima, multiplicado pelo número de maneiras de escolher 2 dentre 4 segmentos no lado esquerdo:
\begin{equation*} C_6^2\times C_4^2 = 90. \end{equation*}

5.

(PROFMAT 2015) Uma escola de educação básica possui 12 professores de matemática, sendo que 8 atuam exclusivamente no Ensino Fundamental e 4 atuam exclusivamente no Ensino Médio. Para a organização da 1ª Olimpíada de Matemática da escola, será formada uma comissão de 5 professores de matemática, de modo que pelo menos um deles seja professor do Ensino Médio. De quantas maneiras essa comissão poderá ser formada?
Resposta.
\(736\)
Solução.
Vamos contar o total de modos de escolher 5 professores dentre os 12, depois subtraímos o número de casos em que nenhum professor do ensino médio foi selecionado. O número de soluções é
\begin{equation*} C_{12}^5 - C_8^5 = 736. \end{equation*}

6.

(UFBA 2006) Durante uma reunião, ocorreu uma divergência quanto à formação de uma comissão gestora, a ser escolhida entre os presentes. Um grupo defendia uma comissão com três membros, sendo um presidente, um vice-presidente e um secretário. Outro grupo queria uma comissão com três membros sem cargos definidos. A primeira alternativa oferece 280 possibilidades de escolha a mais que a segunda. Determine o número de pessoas presentes à reunião, sabendo-se que esse número é maior que 5.
Resposta.
8
Solução.
Seja \(n\) a quantidade de pessoas na reunião. No primeiro caso temos \(n\times(n-1)\times (n-2)\) modos de escolher a comissão. No segundo caso temos \(C_n^3\) modos de escolher a comissão. Como a primeira alternativa oferece \(280\) possibilidades de escolha a mais que a segunda, temos
\begin{equation*} n\times(n-1)\times (n-2) = C_n^3+280. \end{equation*}
Logo
\begin{equation*} n\times(n-1)\times (n-2) = \frac{n\times(n-1)\times (n-2)}{6}+280 \end{equation*}
e
\begin{equation} n\times(n-1)\times (n-2) = \frac{6\times 280}{5} = 336.\tag{6.4.1} \end{equation}
Observe que no lado esquerdo da equação (6.4.1) temos o produto de três números naturais consecutivos, e do outro lado, temos o número \(336\text{.}\) Fatorando e reescrevendo como produto de três números naturais consecutivos obtemos:
\begin{equation*} 336 = 2^4\times 3\times 7 = 6\times 7\times 8. \end{equation*}
Portanto, \(n-2 = 6, n-1 = 7\) e \(n=8\text{.}\)

7.

(OBM 2004 - 2ª fase do nível 3)
Os doze alunos de uma turma de olimpíada saíam para jogar futebol todos os dias após a aula de matemática, formando dois times de 6 jogadores cada e jogando entre si. A cada dia eles formavam dois times diferentes dos times formados em dias anteriores. Ao final do ano, eles verificaram que cada 5 alunos haviam jogado juntos num mesmo time exatamente uma vez. Quantos times diferentes foram formados ao longo do ano?
Dica.
Temos \(C_{12}^6\) maneiras de escolher 6 dentre 12 alunos. Note que para cada 5 alunos fixados, temos 7 times possíveis.
Resposta.
\(132 \)

8.

(OBM 2006 - 2ª fase do nível 3)
Seja \(n\) inteiro positivo. De quantas maneiras podemos distribuir \(n+1\) brinquedos distintos para \(n\) crianças de modo que toda criança receba pelo menos um brinquedo?
Dica.
Escolha uma criança para receber dois brinquedos, em seguida escolha os dois brinquedos dessa criança. Agora distribua um brinquedo para cada criança que restou.
Resposta.
\(n\times \dfrac{(n+1)!}{2}. \)

9.

(OBM 2013 - 2ª fase do nível 3)
Para cobrir um tabuleiro de dimensões \(1\times112\text{,}\) podemos utilizar heptaminós amarelos, de dimensões \(1\times7\text{,}\) e octaminós vermelhos, de dimensões \(1\times8\text{.}\) De quantos modos podemos cobrir completamente o tabuleiro?
Resposta.
\(6437 \)
Solução.
Suponha que vamos usar \(x\) heptaminós e \(y\) octaminós. Para cobrir tudo, temos \(7x + 8y = 112\text{.}\)
Observe que \(112 = 2\times7\times8\) é múltiplo de \(7\) e de \(8\text{.}\) Assim, \(7x\) é múltiplo de 8, pois \(7x = 112 - 8y = 8(14 - y)\text{.}\) Analogamente, \(8y\) é múltiplo de 7, pois \(8y = 112 – 7x = 7(16 – x)\text{.}\) Como \(7\) e \(8\) são primos entre si, \(x\) é múltiplo de \(8\) e \(y\) é múltiplo de \(7\text{.}\)
Sendo \(x = 8t\) e \(y = 7u\text{,}\) temos \(7\times8t + 8\times7u = 112 \Leftrightarrow t + u = 2\text{.}\) Assim, os valores de \((t,u)\) são \((0,2), (1,1)\) e \((2,0)\text{,}\) que correspondem a \((x,y)\) sendo \((0,14), (8,7)\) e \((16,0)\text{.}\)
Analisando os três casos:
1º: \((x, y) = (0, 14)\text{,}\) apenas uma maneira de cobrir, pois todas as peças são octaminós.
2º: \((x, y) = (8, 7)\text{,}\) temos no total \(8+7=15\) peças que colocaremos no tabuleiro. Como as peças de tamanho diferente possuem cores distintas e o tabuleiro ficará sem ''buracos'', precisamos escolher as posições que serão colocados os heptaminós, ou as posições que serão colocados os octaminós, pois estes dois valores são iguais. O número de maneiras de fazer isto é
\begin{equation*} C_{15}^{7} = C_{15}^{8} = 6435. \end{equation*}
3º: \((x, y) = (16, 0)\text{,}\) análogo ao primeiro caso, apenas uma maneira.
No total temos \(1+C_{15}^{7}+1 = 1+6435+1 = 6437\) maneiras de cobrir completamente o tabuleiro.

10.

(OBM 2015 - 2ª fase do nível 3)
Um subconjunto de \(5\) elementos do conjunto \(\{1,2,3, ... , 20\}\) é dito largo se ao colocar os seus elementos em ordem crescente tivermos a propriedade de que a diferença do segundo menos o primeiro é maior que \(1\text{,}\) do terceiro para o segundo é maior que \(2\text{,}\) do quarto para o terceiro é maior que \(3\) e do quinto para o quarto é maior que \(4\text{.}\) Existem quantos subconjuntos largos?
Resposta.
\(252 \)
Solução.
Sejam \(a \lt b \lt c \lt d \lt e\) os elementos de um conjunto largo. Assim, \(b > a + 1, c > b + 2, d > c + 3\) e \(e > d + 4\text{,}\) ou seja, \(1 ≤ a \lt b − 1 \lt c - 3 \lt d - 6 \lt e - 10 ≤ 10\text{.}\)
Desta forma, \(\{a, b - 1, c - 3, d - 6, e - 10\}\) é um subconjunto de \(\{1,2,3,\ldots,10\}\text{.}\) Reciprocamente, se \(\{x, y, z, w, t\}\) é um subconjunto de \(\{1,2,3,\ldots,10\}\) com \(x \lt y \lt z \lt w \lt t\) então \(\{x, y + 1, z + 3, w + 6, t + 10\}\) é um conjunto largo, pois \(y + 1 - x > 1, z + 3 - (y + 1) > 2, w + 6 - (z + 3) > 3\) e \(t + 10 - (w + 6) > 4\text{.}\)
Com isso, a quantidade de subconjuntos largos é igual à quantidade de subconjuntos de \(5\) elementos de \(\{1,2,3,\ldots,10\}\text{,}\) que é
\begin{equation*} C_{10}^5 = \frac{10!}{5!5!} = 252. \end{equation*}

11.

(FUVEST 2020 - 2ª fase) Um jogo educativo possui 16 peças nos formatos: círculo, triângulo, quadrado e estrela, e cada formato é apresentado em 4 cores: amarelo, branco, laranja e verde. Dois jogadores distribuem entre si quantidades iguais dessas peças, de forma aleatória. O conjunto de 8 peças que cada jogador recebe é chamado de coleção.
  1. Quantas são as possíveis coleções que um jogador pode receber?
  2. A regra do jogo estabelece pontuações para as peças, da seguinte forma: círculo = 1 ponto, triângulo = 2 pontos, quadrado = 3 pontos e estrela = 4 pontos. Quantas são as possíveis coleções que valem 26 pontos ou mais?
Resposta.
a) \(12870 ~~~~\) b) \(85\)
Solução.
item a) O número de possíveis coleções é dado por:
\begin{equation*} C_{16}^8 = 12870. \end{equation*}
item b) As coleções possíveis são:
1) 4 estrelas e 4 quadrados totalizando 28 pontos:
\begin{equation*} C_4^4\times C_4^4 = 1 \end{equation*}
2) 4 estrelas, 3 quadrados e 1 triângulo totalizando 27 pontos:
\begin{equation*} C_4^4\times C_4^3\times C_4^1 = 1\times 4\times 4 = 16 \end{equation*}
3) 4 estrelas, 3 quadrados e 1 círculo totalizando 26 pontos:
\begin{equation*} C_4^4\times C_4^3\times C_4^1 = 1\times 4\times 4 = 16 \end{equation*}
4) 4 estrelas, 2 quadrados e 2 triângulos totalizando 26 pontos:
\begin{equation*} C_4^4\times C_4^2\times C_4^2 = 1\times 6\times 4 = 36 \end{equation*}
5) 3 estrelas, 4 quadrados e 1 triângulo totalizando 26 pontos:
\begin{equation*} C_4^3\times C_4^4\times C_4^1 = 4\times 1\times 4 = 16 \end{equation*}
Portanto existem \(1+16+16+36+16 = 85\) coleções possíveis.

12.

(FUVEST 2018 - 2ª fase) Em um torneio de xadrez, há \(2n\) participantes. Na primeira rodada, há \(n\) jogos. Calcule, em função de \(n\text{,}\) o número de possibilidades para se fazer o emparceiramento da primeira rodada, sem levar em conta a cor das peças.
Resposta.
\(\dfrac{(2n)!}{2^n\times n!} \)
Solução.
Para o primeiro jogo, temos um total de \(C_{2n}^2\) maneiras de escolher os participantes. Para o segundo jogo, temos um total de \(C_{2n-2}^2\) maneiras de escolher os participantes e assim sucessivamente, até que para o último jogo ficamos com \(C_2^2\) maneiras de escolher os participantes.
Observe que a ordem os jogos não importa. Portanto, precisamos dividir pela quantidade de maneiras de ordenar esses jogos. A resposta é dada por:
\begin{equation*} \frac{C_{2n}^2\times C_{2n-2}^2\times \cdots \times C_{2}^2}{n!} = \frac{(2n)!}{2^n\times n!}. \end{equation*}
en.wikipedia.org/wiki/Binomial_coefficient
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone