Olá gente! Hoje falarei sobre análise combinatória. Nesse primeiro post sobre o assunto pretendo apenas introduzir alguns conceitos básicos.
.
(fórmula da absorção)
![= \frac{(n-1)! \cdot (n-k) + (n-1)! \cdot k}{k! \cdot (n-k)!}= [;= \frac{(n-1)! \cdot (n-k) + (n-1)! \cdot k}{k! \cdot (n-k)!}=;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tMg0bTl_8tSTaFjAYMd_QTtA10NBvQhgGw22pwccNeNoWENEf5Mo4QGTrOcpiBj2HYs-Zt6ER6pdfc03lp5NBMMbSMmOO6gFkaPLy4MsQtimAR0Bcqx4LD_w7E5emrw3pNmm-wS3LaonsiBY1HAQe98vzXL6jOqtn809opOUGFYjLBohi64lZo1wo0L8udGAeXJyiTxjJ3Hpnyrsi_Te1khdBkA2hqZhz4ZJBavEShXA=s0-d)
![=\frac{n!}{k! \cdot (n-k)!} [;=\frac{n!}{k! \cdot (n-k)!};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tzepriUYx6KO372nLLvrqbk7NJ0vl0CAgQLVlMa-5AAlcvOxGBUuv_Wd5X8YxWyat2e-asH7AvliBiqmgEDsorPf6_mp5S5pctaYBEBeU7GkJVdoXuAXIX8OMnTF-LEipCEEVg7abTV9rXfmlg=s0-d)
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
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 é
.
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 [;4 \cdot 3 \cdot 2 \cdot 2 = 48;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uN7amygHQi_pYrF-j-At9rFpm_uNRIZYZ8FV8P7grnM__7dX0joJqt-ouocGYmZM4IksdaJuu-eBu5u2fSadD7YZEjbMeAXcIY123rk2OM_I66prvTg9M4OUGcZCAMRNejUU12FL4YTHKynhs=s0-d)
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á
modos de formar essa fila.
De modo geral, para ordenar n objetos distintos há
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
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 é:
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
(lê-se n escolhe k) como o número de subconjuntos de A que possuem k elementos. Sendo
. 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
formas, assim, o número de maneiras de escolher os k elementos é
Logo, há
maneiras de escolher esses representantes.
ALGUMAS PROPRIEDADES!
Se n e k são números inteiros positivos com
, então:
P.1- ![{n \choose k}={n \choose (n-k)} [;{n \choose k}={n \choose (n-k)};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vgEekOg5Ow6wKD2toYUJTvO_yoyiPnB4hZPfufma42VRuHNU6ycNHhJSidpfgtZL4n5DrljV73D5BsU5TOnIHOCwRvL_fzblKocxyp-32ZSY8F8A8_WwLOLMlYR5wazbgDD3ty0gYZ9gEzRTbTP_A=s0-d)
De fato, por definição
e
P.2-
Para demonstrar é só aplicar a definição!
P.3-
(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)} [;{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} = {(n+1) \choose (k+1)};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uRnoFYSdQRcuxyMy9RD3NuaIo4vGA-WydxRM-kmpiH0rNkBv6-CjERFSrfntpj19NiWS5tsTdxL-0DP-6nLgQaMnYtJowAxbF3qDwj8ngn8L6sVEATBKmLUVFBRkfr_bvYwi-GhCNvL27Fs6SRk37bW2FhIej_XVddjVXJBfUvT4ohBiwZwoezZWEktAfDQiY5sU-NB3mVOnEeznIUV_SNNRt0eRB3_G6-KDdh6qR2xzJxzx94P5w1a98QKluQ3-TcmMnTLoEe6CkuOYWfvP8--A=s0-d)
Vamos usar indução em n.
Se ![n=k [;n=k;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uu8JAdhkFpVf4Jq9Z7RtxSn32jl42ZdZS9YX8MWYqrusc2WxtLAUoyjeo5G9H0Vz_aaMQTQWZHxnHaVw=s0-d)
Se ![{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} = {(n+1) \choose (k+1)} [;{k \choose k} + {(k+1) \choose k} + \cdots + {n \choose k} = {(n+1) \choose (k+1)};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uRnoFYSdQRcuxyMy9RD3NuaIo4vGA-WydxRM-kmpiH0rNkBv6-CjERFSrfntpj19NiWS5tsTdxL-0DP-6nLgQaMnYtJowAxbF3qDwj8ngn8L6sVEATBKmLUVFBRkfr_bvYwi-GhCNvL27Fs6SRk37bW2FhIej_XVddjVXJBfUvT4ohBiwZwoezZWEktAfDQiY5sU-NB3mVOnEeznIUV_SNNRt0eRB3_G6-KDdh6qR2xzJxzx94P5w1a98QKluQ3-TcmMnTLoEe6CkuOYWfvP8--A=s0-d)
então
![{(n+1) \choose (k+1)} [;{(n+1) \choose (k+1)};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uqPwGlEtjY5f-ZYSBx2WOJdXak4F2jJuDTXlyFeZQQ-npFyZRxwj1g9o8Ka3WAV6yydZyv5TcZ4Cibr9nj0zFnCFI6xiUmMqOH_fKm7xSxOL2EbxQyW_WOdGZZfxTpvA=s0-d)
![+ {(n+1) \choose k} [; + {(n+1) \choose k};]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uLlCpqT3Ll4UWaytZiwLc_OFFqPj6WYyVQkUfg7DWEaISGyZelHiQf0sj3PyofAWJPyarL_zBKgGJUEB31LHFhtG9DhKXP3ESV9M4McAUxz6trUOiTSB3Xpa2wqRw=s0-d)
Pela propriedade 3...
C.Q.D.
P.5- ![{n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n [;{n \choose 0} + {n \choose 1} + \cdots + {n \choose n} = 2^n;]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uFIRja6ijc7oq9uGyBvITDnM7e55TebrBTWNakdoarLi2KIwM9F-n2D1S70OO3ibShSx2HLaW32tHjo9gU-nRSWRZAGIXCay1hBh8gR9-FvDbv16llMiWlJjOgPs2rW6iO0fY6Gb9uYl9SG7Vwd1uijlnzr02kFTK-toDBbylw59C9r5rw3D_tx3ZOu9bOYsywGFcRcbpQrBM--HnjBbRgq2oTydF_YM5y=s0-d)
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
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 !