Olá gente! Hoje falarei sobre análise combinatória. Nesse primeiro post sobre o assunto pretendo apenas introduzir alguns conceitos básicos.
![[;\frac{n\cdot(n-1)\cdots (k+1) \cdot k}{k!} = \frac{n!}{k! (n-k)!};]](http://thewe.net/tex/%5Cfrac%7Bn%5Ccdot%28n-1%29%5Ccdots%20%28k+1%29%20%5Ccdot%20k%7D%7Bk%21%7D%20=%20%5Cfrac%7Bn%21%7D%7Bk%21%20%28n-k%29%21%7D "\frac{n\cdot(n-1)\cdots (k+1) \cdot k}{k!} = \frac{n!}{k! (n-k)!}")
.
![[;{n \choose (n-k)} = \frac{n!}{(n-k)![n-(n-k)]!}= \frac{n!}{(n-k)!k!};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20%28n-k%29%7D%20=%20%5Cfrac%7Bn%21%7D%7B%28n-k%29%21%5Bn-%28n-k%29%5D%21%7D=%20%5Cfrac%7Bn%21%7D%7B%28n-k%29%21k%21%7D "{n \choose (n-k)} = \frac{n!}{(n-k)![n-(n-k)]!}= \frac{n!}{(n-k)!k!}")
![[;{n \choose k} = \frac{n}{k} {(n-1) \choose (k-1)};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20k%7D%20=%20%5Cfrac%7Bn%7D%7Bk%7D%20%7B%28n-1%29%20%5Cchoose%20%28k-1%29%7D "{n \choose k} = \frac{n}{k} {(n-1) \choose (k-1)}")
(fórmula da absorção)
![[;{(n-1) \choose k} + {(n-1) \choose (k-1)} = \frac{(n-1)!}{k! \cdot (n-k-1)!} + \frac{(n-1)!}{(k-1)! \cdot (n-k)!} =;]](http://thewe.net/tex/%7B%28n-1%29%20%5Cchoose%20k%7D%20+%20%7B%28n-1%29%20%5Cchoose%20%28k-1%29%7D%20=%20%5Cfrac%7B%28n-1%29%21%7D%7Bk%21%20%5Ccdot%20%28n-k-1%29%21%7D%20%20+%20%5Cfrac%7B%28n-1%29%21%7D%7B%28k-1%29%21%20%5Ccdot%20%28n-k%29%21%7D%20= "{(n-1) \choose k} + {(n-1) \choose (k-1)} = \frac{(n-1)!}{k! \cdot (n-k-1)!} + \frac{(n-1)!}{(k-1)! \cdot (n-k)!} =")
![[;= \frac{(n-1)! \cdot (n-k) + (n-1)! \cdot k}{k! \cdot (n-k)!}=;]](http://thewe.net/tex/=%20%5Cfrac%7B%28n-1%29%21%20%5Ccdot%20%28n-k%29%20+%20%28n-1%29%21%20%5Ccdot%20k%7D%7Bk%21%20%5Ccdot%20%28n-k%29%21%7D= "= \frac{(n-1)! \cdot (n-k) + (n-1)! \cdot k}{k! \cdot (n-k)!}=")
![[; \frac{(n-1) \cdot (n-k+k)}{k! \cdot (n-k)!}=;]](http://thewe.net/tex/%20%5Cfrac%7B%28n-1%29%20%5Ccdot%20%28n-k+k%29%7D%7Bk%21%20%5Ccdot%20%28n-k%29%21%7D= "\frac{(n-1) \cdot (n-k+k)}{k! \cdot (n-k)!}=")
![[;=\frac{n!}{k! \cdot (n-k)!};]](http://thewe.net/tex/=%5Cfrac%7Bn%21%7D%7Bk%21%20%5Ccdot%20%28n-k%29%21%7D "=\frac{n!}{k! \cdot (n-k)!}")
![[;= {n \choose k};]](http://thewe.net/tex/=%20%7Bn%20%5Cchoose%20k%7D "= {n \choose k}")
![[;{k \choose k} = {(k+1) \choose (k+1)} = 1;]](http://thewe.net/tex/%7Bk%20%5Cchoose%20k%7D%20=%20%7B%28k+1%29%20%5Cchoose%20%28k+1%29%7D%20=%201 "{k \choose k} = {(k+1) \choose (k+1)} = 1")
![[;{(n+1) \choose (k+1)} + {(n+1) \choose k} = {(n+2) \choose (k+1)};]](http://thewe.net/tex/%7B%28n+1%29%20%5Cchoose%20%28k+1%29%7D%20+%20%7B%28n+1%29%20%5Cchoose%20k%7D%20=%20%7B%28n+2%29%20%5Cchoose%20%28k+1%29%7D "{(n+1) \choose (k+1)} + {(n+1) \choose k} = {(n+2) \choose (k+1)}")
Q-1) Dentre 4 jogadores de futebol, de quantas formas podemos escolher 1 atacante e 1 goleiro.
Esse problema ilustra o principio multiplicativo, que é enunciado da seguinte forma:
Se há K formas de tomar uma decisão A e não importando a decisão tomada há L formas de tomar a decisão B, então podemos tomar consecutivamente as decisões A e B de ![[;K \cdot L;]](http://thewe.net/tex/K%20%5Ccdot%20L "K \cdot L")
formas.
De fato:
Para escolher o atacante temos 4 opções, para cada atacante que for escolhido há 3 formas de escolher o goleiro.
Assim, o número total de formas de escolher essa dupla é ![[;4 \cdot 3= 12;]](http://thewe.net/tex/4%20%5Ccdot%203=%2012 "4 \cdot 3= 12")
.
Se restar dúvida, observe a arvore de possibilidades abaixo, ela lista todos os casos.
Q-2) De quantas formas podemos colorir a figura abaixo se dispormos de 4 cores e partes que possuam um segmento em comum não podem ter a mesma cor?
Observe que escolher a ordem em que iremos pintar a bandeira é essencial, caso contrário teremos grandes problemas mais tarde. Quando isso ocorrer, comece sempre pelo caso mais restrito, que no problema é a região 1.
Para pintar a parte 1 temos 4 possibilidades, depois de pintar a parte 1 há 3 formas de pintar a parte 2, a parte 3 pode ser pintada de 2 formas, pois não pode ter a mesma cor que as partes 1 e 2, e a parte quatro pode ser pintada também de 2 formas, pois não pode ter a mesma cor que as partes 1 e 3. Pelo princípio multiplicativo, há ![[;4 \cdot 3 \cdot 2 \cdot 2 = 48;]](http://thewe.net/tex/4%20%5Ccdot%203%20%5Ccdot%202%20%5Ccdot%202%20=%2048 "4 \cdot 3 \cdot 2 \cdot 2 = 48")
formas de pintar essa figura.
Q-3) De quantas formas podemos colocar 11 pessoas em fila?
Há 11 formas de escolher quem ocupará o primeiro lugar, 10 para o segundo, 9 para o terceiro... 2 para o décimo e 1 para o décimo primeiro. Logo, há![[;11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 39916800;]](http://thewe.net/tex/11%20%5Ccdot%2010%20%5Ccdot%209%20%5Ccdot%208%20%5Ccdot%207%20%5Ccdot%206%20%5Ccdot%205%20%5Ccdot%204%20%5Ccdot%203%20%5Ccdot%202%20%5Ccdot%201%20=%2039916800 "11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 39916800")
modos de formar essa fila.
De modo geral, para ordenar n objetos distintos há ![[;n \cdot (n-1) \cdots 2 \cdot 1;]](http://thewe.net/tex/n%20%5Ccdot%20%28n-1%29%20%5Ccdots%202%20%5Ccdot%201 "n \cdot (n-1) \cdots 2 \cdot 1")
formas de fazê-lo. Lê-se n fatorial e representamos como "n!".
Q-4) De quantas formas 5 pessoas podem se sentar formando uma roda?
A primeira pessoa pode ser escolhida de 5 formas, a segunda de 4 formas, a terceira de 3, a segunda de 2 e a ultima só de 1 forma. Porém as rodas ABCDE, BCDEA, CDEAB, DEABC e EABCD são equivalentes, logo são ![[;\frac{5!}{5}=4!;]](http://thewe.net/tex/%5Cfrac%7B5%21%7D%7B5%7D=4%21 "\frac{5!}{5}=4!")
maneiras de formar essa roda.
Generalizando um pouco, o número de maneiras de dispor n objetos em um circulo, se as rotações coincidirem é o número de maneiras que as pessoas podem ser permutadas, dividido pelo número de rotações, que é: ![[;\frac{n!}{n}=(n-1)!;]](http://thewe.net/tex/%5Cfrac%7Bn%21%7D%7Bn%7D=%28n-1%29%21 "\frac{n!}{n}=(n-1)!")
Esse tipo de combinação é chamado de permutação circular.
Q-5) Dentre uma turma de 20 pessoas, queremos selecionar 3 para serem representantes de turma. De quantas maneiras podemos escolher esses representantes?
Sendo A um conjunto de n elementos, definimos ![[;{n \choose k};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20k%7D "{n \choose k}")
(lê-se n escolhe k) como o número de subconjuntos de A que possuem k elementos. Sendo ![[;{n \choose k}= \frac{n!}{k!(n-k)!};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20k%7D=%20%5Cfrac%7Bn%21%7D%7Bk%21%28n-k%29%21%7D "{n \choose k}= \frac{n!}{k!(n-k)!}")
. De fato, o primeiro elemento pode ser escolhido de n formas, o segundo de (n-1)... o k-ésimo elemento pode ser escolhido de (n-k+1). Porém esses k elementos podem ser permutados entre si de ![[;k!;]](http://thewe.net/tex/k%21 "k!")
formas, assim, o número de maneiras de escolher os k elementos é
Logo, há ![[;\frac{20!}{3! \cdot 17!}= 1140;]](http://thewe.net/tex/%5Cfrac%7B20%21%7D%7B3%21%20%5Ccdot%2017%21%7D=%201140 "\frac{20!}{3! \cdot 17!}= 1140")
maneiras de escolher esses representantes.
ALGUMAS PROPRIEDADES!
Se n e k são números inteiros positivos com ![[;n>k;]](http://thewe.net/tex/n%3Ek "n>k")
, então:
P.1- ![[;{n \choose k}={n \choose (n-k)};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20k%7D=%7Bn%20%5Cchoose%20%28n-k%29%7D "{n \choose k}={n \choose (n-k)}")
De fato, por definição ![[;{n \choose k} = \frac{n!}{k! (n-k)!};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20k%7D%20=%20%5Cfrac%7Bn%21%7D%7Bk%21%20%28n-k%29%21%7D "{n \choose k} = \frac{n!}{k! (n-k)!}")
e
P.2-
Para demonstrar é só aplicar a definição!
P.3- ![[;{n \choose k} = {(n-1) \choose k} + {(n-1) \choose (k-1)};]](http://thewe.net/tex/%7Bn%20%5Cchoose%20k%7D%20=%20%7B%28n-1%29%20%5Cchoose%20k%7D%20+%20%7B%28n-1%29%20%5Cchoose%20%28k-1%29%7D "{n \choose k} = {(n-1) \choose k} + {(n-1) \choose (k-1)}")
(relação de Stifel)
C.Q.D.
P.4- ![[;{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} = {(n+1) \choose (k+1)};]](http://thewe.net/tex/%7Bk%20%5Cchoose%20k%7D%20+%20%7B%28k+1%29%20%5Cchoose%20k%7D%20+%20%5Ccdots%20+%20%7Bn%20%5Cchoose%20k%7D%20=%20%7B%28n+1%29%20%5Cchoose%20%28k+1%29%7D "{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} = {(n+1) \choose (k+1)}")
Vamos usar indução em n.
Se ![[;n=k;]](http://thewe.net/tex/n=k "n=k")
Se
então ![[;{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} + {(n+1) \choose k} =;]](http://thewe.net/tex/%7Bk%20%5Cchoose%20k%7D%20+%20%7B%28k+1%29%20%5Cchoose%20k%7D%20+%20%5Ccdots%20+%20%7Bn%20%5Cchoose%20k%7D%20+%20%7B%28n+1%29%20%5Cchoose%20k%7D%20= "{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} + {(n+1) \choose k} =")
![[;{(n+1) \choose (k+1)};]](http://thewe.net/tex/%7B%28n+1%29%20%5Cchoose%20%28k+1%29%7D "{(n+1) \choose (k+1)}")
![[; + {(n+1) \choose k};]](http://thewe.net/tex/%20+%20%7B%28n+1%29%20%5Cchoose%20k%7D "+ {(n+1) \choose k}")
Pela propriedade 3...
C.Q.D.
P.5- ![[;{n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n;]](http://thewe.net/tex/%7Bn%20%20%5Cchoose%200%7D%20+%20%7Bn%20%5Cchoose%201%7D%20+%20%5Ccdots%20+%20%7Bn%20%5Cchoose%20n%7D%20=%202%5En "{n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n")
Para demonstrar essa propriedade vamos pensar no que essa soma representa.
Se é o número de subconjuntos com k elementos de um conjunto com n elementos, então essa soma mostra quantos subconjuntos um conjunto de n elementos tem no total.
Logo, precisamos contar de quantas maneiras podemos formar esse subconjunto. Cada um dos n elementos tem 2 opções, estar ou não nesse subconjunto que queremos formar. Logo, pelo principio multiplicativo, são ![[;2^n;]](http://thewe.net/tex/2%5En "2^n")
maneiras de formar esse subconjunto.
Por hoje é só! Espero que este post tenha sido util. Brevemente voltarei com algumas coisas um pouco mais avançadas sobre combinatória. Se você gostou, recomende aos seus amigos nas redes sociais e se inscreva por e-mail para receber nossas atualizações.
Lembre-se: Para melhorar a qualidade de nossas postagens avalie este post nas caixas logo abaixo. É rapidinho!
Até mais!
Fonte:
Apostila 2 distribuina no Programa de Iniciação Científica da OBMEP - Você pode baixa-la clicando aqui
Apostila da aula 3 do curso de combinatória do POTI (Polo de Treinamento Intensivo) escrita pelo Prof. Carlos Shine - Você pode vizualiza-la clicando aqui
Fonte:
Apostila 2 distribuina no Programa de Iniciação Científica da OBMEP - Você pode baixa-la clicando aqui
Apostila da aula 3 do curso de combinatória do POTI (Polo de Treinamento Intensivo) escrita pelo Prof. Carlos Shine - Você pode vizualiza-la clicando aqui
Gostei muito deste post.
ResponderExcluirSó não entendi as propriedades,por burrice minha msm !