Em 2023 eu li até a seção sobre o PFC do livro de Análise Combinatória do Morgado porque estava fazendo Estatística na faculdade, curso que possui Análise Combinatória e Cálculo como pré-requisito. Mas por estar apanhando demais nos exercícios, parei e nunca mais li o Morgado.
Atualmente estou de férias na faculdade e no próximo semestre farei uma matéria optativa chamada Matemática Discreta, onde estudarei tudo que está no Morgado.
Animado com o próximo semestre, fiz minha mãe contar quantos looks podemos formar com x camisas e y shorts, enquanto viajávamos.
Além disso, eu e ela tentamos deduzir a fórmula de combinação simples, mas não conseguimos (apesar de termos avançado no entendimento da fórmula). Mas quando fui dormir nesse dia, a solução veio na minha cabeça e consegui chegar na fórmula.
(gostei muito de como esse momento aconteceu)
Neste post, escreverei exatamente o mesmo raciocínio que comecei com minha mãe e terminei no colchão. Definitivamente não será uma demonstração, mas é a forma que consegui de decorar fórmula de combinação simples. Pode-se dizer que é uma dedução, já que usei os conhecimentos que eu tinha para chegar na fórmula (sem ter visto ela antes).
Conteúdo do post
— publicidade —
O que é a fórmula de combinação simples
Para deduzir a fórmula de combinação simples, precisamos primeiro saber o que ela faz.
A fórmula de combinação simples te dá quantos subconjuntos de $p$ elementos podemos formar a partir de um conjunto de $n$ elementos (com $p < n$).
Em outras palavras, a fórmula de combinação simples te diz quantas possibilidades de escolher $p$ objetos dentre $n$ objetos existem.
Usarei $C_{n}^p$ para denotar essa quantidade de subconjuntos/possibilidades.
Agora que sabemos isso podemos deduzir a fórmula.
Assim como fiz quando tentei deduzir com a minha mãe, começarei tentando deduzi-la usando números, e não letras.
Dedução com números
Para deduzir a fórmula de combinação, eu imaginei a seguinte situação:
Suponha que você queira escolher $5$ carrinhos de hot wheels dentre $12$ carrinhos (para dar de presente para seu sobrinho, por exemplo). Quantas combinações de $5$ carrinhos é possível escolher?
Para escolher o primeiro carrinho, teremos $12$ opções. Para escolher o segundo carrinho, teremos $11$ opções (pois já escolhemos um). Para escolher o terceiro carrinho, teremos $10$ opções… E assim vai até o quinto carrinho, onde teremos $8$ opções.
Como eu já conhecia o PFC, concluí que o número de combinações seria $\frac{12!}{7!}$. Isso dá $95040$ combinações!
Apesar do número gigantesco, confiei na minha lógica e achei que tinha chegado na resposta certa. Maas, ao olhar a resposta (do total de possibilidades, não a fórmula!) vi que estava errado. Conversando com a minha mãe eu percebi que errei porque contei as combinações mais de uma vez!
Para entender isso direito, bora chamar os carrinhos de carrinho 1, carrinho 2, carrinho 3, e etc.
Note que dá no mesmo se eu escolher os carrinhos 1, 4, 11, 2, 9 ou os carrinhos 9, 1, 4, 2, 11. Em ambas as combinações, eu compraria exatamente os mesmos carrinhos para o meu sobrinho. No entanto, na resposta que dei acima eu estou considerando as duas combinações como combinações diferentes!
Essa afirmação precisaria ser justificada, mas não me preocupei com isso.
O ponto é: pelo fato da ordem não importar nós contamos toda combinação mais de uma vez.
Daí, para deduzir a quantidade total de combinações, minha missão se tornou eliminar as combinações repetidas da conta que fiz.
Como não estava fácil, eu decidi listar “na força bruta” quantas combinações repetidas teríamos caso quiséssemos escolher apenas os carrinhos 1, 2 e 3.
As combinações repetidas são:
- 1, 2, 3
- 1, 3, 2
- 2, 1, 3
- 2, 3, 1
- 3, 1, 2
- 3, 2, 1
Ou seja, contaríamos $6$ vezes a mesma combinação.
Se quiséssemos escolher 4 carrinhos, as combinações repetidas seriam:
- 1, 2, 3, 4
- 1, 2, 4, 3
- 1, 3, 2, 4
- 1, 3, 4, 2
- 1, 4, 2, 3
- 1, 4, 3, 2
- 2, 1, 3, 4
- 2, 1, 4, 3
- 2, 3, 1, 4
- 2, 3, 4, 1
- 2, 4, 1, 3
- 2, 4, 3, 1
- 3, 1, 2, 4
- 3, 1, 4, 2
- 3, 2, 1, 4
- 3, 2, 4, 1
- 3, 4, 1, 2
- 3, 4, 2, 1
- 4, 1, 2, 3
- 4, 1, 3, 2
- 4, 2, 1, 3
- 4, 2, 3, 1
- 4, 3, 1, 2
- 4, 3, 2, 1
Ou seja, teríamos $24$ combinações repetidas!
Eu não sei como garantir que essas são de fato todas as combinações repetidas, mas lá no fundo eu sei que são. Acho que uma forma de provar isso seria usando o PFC.
No entanto, mesmo listando todas as combinações repetidas para esses casos particulares, eu ainda não tinha conseguido deduzir a fórmula, então fui dormir.
Mas quando fechei o olho percebi o que estava acontecendo: para escolher $3$ carrinhos, havia $3!$ combinações repetidas, e para escolher $4$ carrinhos, havia $4!$ combinações repetidas!
Então eu concluí que para tirar todas as combinações repetidas da conta que eu fiz, bastava dividi-la por $5!$.
Fazendo isso obtemos:
$C_{12}^5 = \frac{12!}{7! 5!} = \frac{479001600}{5040 \cdot 120} = 792$
E essa resposta está certa!
Logo, ao escolher 5 carrinhos de hot wheels dentre 12 carrinhos, eu posso fazer isso de 792 formas diferentes!
Dedução com letras
Caso troquemos o $5$ por $p$ e o $12$ por $n$ na conta anterior, obteremos:
$C_{n}^p = \frac{n!}{(n-p)!p!}$
(note que $7 = 12 – 5$)
E essa é a dedução prometida!
Diário de Estudos
Escrever este post foi uma experiência interessante. Eu escrevi ele em 2 dias (normalmente eu demoro semanas), e fiz isso 2 dias antes do novo semestre começar. Foi assim por dois motivos:
- Porque só tive que descrever o raciocínio que me levou à fórmula de combinação simples, sem a intenção de usar letras ou provar que o raciocínio está certo.
- E porque quero ver como minha linguagem mudará após eu terminar o curso de Matemática Discreta.
Vai ser uma experiência legal fazer esse curso. Desde 2023 eu tenho interesse em Análise Combinatória (lembro que foi uma merda fazer Estatística sem saber Análise Combinatória) e finalmente estudarei isso na faculdade.
A ementa do curso de Matemática Discreta é:
Infelizmente eu precisaria de pelo menos 1 ano estudando só essa matéria pra aprender tudo isso, mas não tem problema. O Morgado é um livro que quero fazer todos os exercícios antes de morrer, então pensarei no curso como um cursinho preparatório para o Morgado.
Muito obrigado por chegar até aqui :]
Eu provavelmente vou sumir até as próximas férias (como sempre faço) que será em janeiro, mas espero ter boas ideias de posts para escrever até lá.
Deixarei sugerido dois posts legais para você ler enquanto eu não volto:
Resumo da história da Matemática no ocidente – Quarto 707
Resumo de Algoritmos Numéricos – Quarto 707
— publicidade —
As nossas conversas me fazem pensar e com as suas explicações escritas tudo faz sentido e eu aprendo um pouquinho cada dia. Amo estar presente no seu dia a dia e mesmo que seja só um pouquinho, você nem imagina como é grandioso e gratificante para mim.
Que venha muitos e muitos problemas para eu pensar…
<33333
Agora explica pro tio mega orgulhoso e sem entender muito rsrs , ou melhor , quase nada de nada kkk.
A resposta que vc deu ao comentário da mamãe srsr
Parabéns nego , que Deus te abençoe e conserve essa inteligência, que nem podemos dizer que é do homem , é dom de Deus srsr
Contrariando mais uma vez o pensamento do matemático, mas aí eu digo , dane-se , o matemático não sou eu kkk.
Sucesso meu Grande Professor… te amo .
Explico sim kkkkkkk. Queria muito que essa inteligência fosse dom de Deus kkkk. Por enquanto ainda não é pq não sei usar ela pra fazer coisas boas, mas vou aprender.
Muito obrigado tio! Também te amo muito!
Adorei sua escrita, dessa forma foi bem mais claro de entender pq precisa tirar as combinações repetidas. Você podia fazer um outro post no final do período sobre mais algum tema de matemática discreta.
Gostei muito e voltarei mais vezes!!
muuuuito obrigado Layza :’]
Saber que uma estudante de matemática gostou do post me deixa muito feliz. Pode ter certeza que farei mais posts sobre matemática discreta dps que o período acabar, então trate de voltar mesmo!