Pular para o conteúdo principal

ENEM - Análise combinatória - Combinações com repetição

Há alguns problemas de contagem muito interessantes que não podem ser resolvidos apenas com os conhecimentos básicos de análise combinatória. Alguns requeremesquecer o glamour e contar na raça mesmo, outros uma sofisticação maior. Nesta mini-aula de dois posts vamos aprender sobre combinações com repetição e distribuição de objetos em caixas, ambos conceitos bem úteis para a OBM/OBMEP.




Introdução



Considere o seguinte problema: Dados os números 2, 4, 7, 9 e 10, quantos produtos diferentes é possível estabelecer multiplicando quaisquer 2 deles, se cada fator pode aparecer mais de uma vez nesse produto?



Inicialmente somos tentados a achar que a resposta é uma combinação de 5 elementos tomados de 2 a 2, mas nessa contagem ignoramos os produtos de dois números iguais. Um desses produtos é 2 x 2. Poderíamos considerar que estamos combinando 10 elementos ao invés de 5, mas nesse caso contaríamos o mesmo produto mais de uma vez.



Outra questão: De quantos modos podemos particionar um número em n parcelas, tal que a soma dessas parcelas resulte no número original? Por exemplo, particionar 6 em 3 parcelas?



Esse tipo de problema corresponde a encontrar o número de soluções (inteiras positivas ou não-negativas, dependendo do problema) da equação:



x + y + z = 6



Para responder essas e outras questões, vamos explorar dois conceitos de análise combinatória: combinações com repetição e distribuição de objetos em caixas. Bem... claro, no desespero você poderia tentar dividir em casos e contar um por um, mas é isso que separa garotos de matemáticos.


Pré-requisitos



Naturalmente, um conhecimento básico de análise combinatória é necessário aqui — em especial, combinações. Dê uma olhada nesta breve introdução para ter alguma base ou refrescar a memória.


Combinações com repetição



Vejamos uma outra versão do primeiro problema apresentado na introdução: consideremos 3 objetos a, b, c. De quantas formas é possível combiná-los, tomando-os em grupos de 3, se pudermos repetir objetos em um mesmo grupo?



Primeiro, vamos estabelecer algumas notações para facilitar o raciocínio. Cada grupo será representado por um monômio na forma ai1bi2ci3, onde ij representa o número de vezes que o j-ésimo elemento aparece no grupo. Algumas representações (note que omitimos os termos com grau zero):
a
i
1
b
i
2
c
i
3
i
j



- a³: O grupo é formado por três objetos "a".
- abc: O grupo é formado por um objeto "a", um objeto "b" e um objeto "c".
- b²c: O grupo é formado por dois objetos "b" e um objeto "c".
- c³: O grupo é formado por três objetos "c".



Além disso, cada grupo também pode ter uma representação binária. Usamos uma fila de uns para mostrar quantas vezes o objeto é repetido no grupo e zeros para dividir os objetos:



- a³: 11100
- abc: 10101
- b²c: 01101
- c³: 00111



Podemos observar algumas coisas interessantes:


  • número de uns não varia, sendo sempre igual a 3. Isso porque, em cada grupo, deve obrigatoriamente haver 3 objetos.
  • número de zeros também não varia, sendo sempre igual a 2. Para dividir os objetos em 3 sub-sequências, precisamos de 2 zeros.
  • O número total de elementos corresponde à soma da quantidade de uns com a quantidade de zeros. Isso resulta em 5 elementos no total.


Assim, vemos que há 5 espaços para serem preenchidos por 3 uns. Os 2 espaços restantes serão preenchidos por zeros.


Podemos posicionar cada um desses 3 uns em qualquer uma das 5 posições.


Exemplo de distribuição:


Posicionamos o primeiro um na primeira posição, o segundo na terceira e o terceiro na quinta. Como consequência, a segunda e quarta posição são ocupadas por zeros.


Generalizando, se tivermos n objetos combinados de p a p, com repetição permitida, entãohá p uns e n - 1 zeros. Logo:


CRnp=Cp+n1p

C
R
n
p
=
C
p+n1
p


Voltando ao nosso exemplo, há  

C3+313= C53=10 

combinações possíveis para os 3 objetos tomados de 3 a 3. Podemos listá-las: {a, a, a}, {a, a, b}, {a, a, c}, {b, b, b}, {b, b, a}, {b, b, c}, {c, c, c}, {c, c, a}, {c, c, b}, {a, b, c}. Sim, contamos todas!

Como exercício, resolva o problema apresentado na introdução.


O que vem por aí



A seguir, vamos explorar o problema de distribuir objetos em caixas — relativamente simples, mas talvez não tão simples quanto se imagina. Clique aqui para continuar!


Fontes




http://www.numerofilia.com.br/2012/01/analise-combinatoria-combinacoes-com.html

Postagens mais visitadas deste blog

Canções para TFM

DEMÔNIOS CAMUFLADOS DEMÔNIOS CAMUFLADOS VÃO SAIR DA ESCURIDÃO,
SENTINELA ENSANGUENTADO VAI ROLANDO PELO CHÃO,
E PERGUNTEM DE ONDE VENHO, VENHO DA ESCURIDÃO,
TRAGO A MORTE, O DESESPERO E A TOTAL DESTRUIÇÃO.
ARMADILHAS CAMUFLADAS, ACIONADORES DE TRAÇÃO,
QUEM VIER ATRAS DE MIM SÓ VAI OUVIR A EXPLOSÃO(CABUM)
SANGUE FRIO EM MINHAS VEIAS CONGELOU MEU CORAÇÃO
NÓS GOSTAMOS DE EXPLOSIVOS NOSSO LEMA É VIBRAÇÃO.
QUEM ÉS TU? QUEM ÉS TU?
QUE DESCE DO CÉU!
COM ASAS DE PRATA POR SOBE O BRASIL!
GUERREIRO ALADO, QUE NÃO SENTE DOR!
PARAQUEDISTA, COMANF, MERGULHADOR!
A SUA MISSÃO É DESTRUIR
A TROPA INIMIGA QUE TENTA INVADIR

CORRIDINHA MIXURUCA CORRIDINHA MIXURUCA,
QUE NÃO DÁ NEM PARA CANÇAR.
NESSE PASSO, NESSE PASSO,
VOLTA AO MUNDO EU VOU DAR.
NESSE PASSO, NESSE PASSO
TODOS JUNTOS VÃO CHEGAR.
E SE ALGUÉM NÃO AGUENTAR,
EU VOU TER QUE ARRASTAR.
E SE O ARRASTO ME MATAR, PODES CRER TU VAI FICA
VAI FICAR NA MÃO DE OUTRO – ATÉ EU ME RECUPERAR.
POIS NESSE PASSO, NESSE PASSO,
MESMO MORTO VOU TE BUSCAR.




SALTITANDO, SALTI…

Canções Militares para o TFM.

Essas canções são usadas durante o Treinamento Físico Militar nas Forças Armadas, das Polícias Militares e Corpos de Bombeiros Militares.
Demônios Camuflados Demônios camuflados vão sair da escuridão,
sentinela ensanguentado vai rolando pelo chão,
e perguntem de onde venho, venho da escuridão,
trago a morte, o desespero e a total destruição.
Armadilhas camufladas, acionadores de tração,
Quem vier atras de mim só vai ouvir a explosão(Cabum)
Sangue frio em minhas veias congelou meu coração
Nós gostamos de explosivos nosso lema é vibração.
Quem és Tu? Quem és tu?
Que desce do céu!
Com asas de prata por sobe o Brasil!
Guerreiro alado, que não sente dor!
Paraquedista, Comanf, Mergulhador!
A sua missão é destruir
A tropa inimiga que tenta invadir

Corridinha Mixuruca Corridinha mixuruca,
que não dá nem para cançar.
Nesse passo, nesse passo,
Volta ao mundo eu vou dar.
Nesse passo, nesse passo
Todos juntos vão chegar.
E se alguém não aguentar,
Eu vou ter que arrastar.
E se o arrasto me matar, podes c…

Termodinâmica

Termodinâmica