Combinação

De quantas formas podemos colocar 15 bolas em 5 caixas?

Sei que é um problema simples, mas não estou conseguindo fazer. Se eu fizer C15,5, estará errado?

Acredito que sim, Gabriel. Pois eu posso deixar caixas vazias, colocar 15 bolas em uma das caixas e as outras 4 ficam vazias. O problema não coloca nenhuma restrição quanto à caixas sem bolas, então acredito que poderemos tê-las.

Você concorda que o problema é o mesmo que o seguinte: Qual o número de soluções inteiras não negativas da equação x1 + x2 + x3 + x4 + x5 = 15 ?

Veja, pois, que as soluções são todas as 5-uplas ordenadas (x1, x2, x3, x4, x5) que obedecem a equação e tais que cada um dos xi ( 1 <= i <= 5) está entre 0 e 15.

Bom, o problema se resume a contarmos essas soluções. E como fazemos isso?

Imagine que temos 15 bolinhas e 4 divisórias:

o o o o o o o o o o o o o o o | | | |

Essas divisórias são o numero de sinais de + que temos naquela equação.

Eu vou colocar essas divisórias entre as bolinhas. Por exemplo

o o o | o o o o | o o o | o o o o| o

Concorda que o número de bolinhas que contamos entre as divisórias é uma solução daquela equação? 

Temos: 3 | 4 | 3 | 4 | 1

Ótimo. Podemos usar esse raciocínio para encontrarmos as soluções dessa equação.

Permutamos as 15 bolinhas e as 4 divisórias entre si: Em princípio, há 19! maneiras de permutá-las. Mas, temos 15 bolinhas repetidas e 4 divisórias iguais. Então é permutação com repetição:

Há 19! /(15! 4!) maneiras de colocar as bolinhas nas 15 caixas.

Isso se chama combinações completas. Há uma fórmula para isso, você pode achar no livro do Morgado.

O exercício não é fácil, não se preocupe. Basta ler mais sobre isso.

Se não entender, pode avisar que eu explico novamente,

Até

Um bom exercício para treinar, se quiser: De quantas maneiras podemos colocar 15 bolas em 5 caixas de maneira que nenhuma das caixas fiquem vazias (ou seja, cada uma das caixas deve ter pelo menos 1 bola).?

Giovana, sua resolução foi muito didática, excelente!

Entendi sim o princípio... creio que esse exercício seja sobre permutações com elementos repetidos, o qual ainda não tinha estudado. 
Acredito que as "combinações completas", pela expressão que você colocou, tenha a ver com o caso geral de permutações de elementos repetidos:

n! / (n1! . n2! . n3!....nr!), 

sendo n o número de elementos do conjunto em questão e n1 elementos iguais entre si, n2 elementos iguais entre si,..., nr elementos iguais entre si. 

No caso em questão, creio que n1=15 (bolinhas indistinguíveis) e n2=4 (barras também indistinguíveis duas a duas). Então, como você colocou na resolução, o número de permutações de 19 elementos, com 15 iguais entre si e 4 iguais entre si (esse termo "iguais entre si" deve ser rigorosamente incorreto, mas tudo bem) é:

19! / (15!.4!)

Deve ser algo assim. E obrigado pelo exercício, vou dar mais uma olhada sobre o assunto (que também tem no FME 5, do S. Hazzan) e posto a resolução aqui para você avaliá-la, se não for incômodo!

Obrigado outra vez 

Pode postar, sem problemas  Sim, tem a ver com permutações com repetições e combinações em que não devemos "escolher necessariamente com um número de elementos fixos". Essa solução das bolinhas e divisórias é ótima para entender isso, provavelmente você verá na escola. É bem capaz que veja.

E sim, é exatamente isso, 15 bolinhas identicas e 4 barras identicas. No fme a teoria é muito boa, mas os exercícios do morgado são bem mais desafiadores nessa parte.

Fico esperando sua resolução, o raciocínio é análogo e você vai fazer do mesmo jeito, apenas com um pequeno detalhe que eu ressaltei la em cima. Se não conseguir fazer, me avise

Até

Oi, eu tenho uma dúvida. Quando fazemos os cálculos do número de combinações bola-barra, estamos considerando aquela em que as duas (ou uma) barras ficam nas extremidades? Como ficariam as soluções da equação linear, nesse caso (sem estar entre duas bolas)?
Na expressão (n+r-1)/[r!(n-1)!], que define o número de soluções inteiras não negativas de uma equação de n variáveis de soma r, esse tipo de combinação não é considerada?

Obrigado 

Oi Gabriel,

Sim, as permutações em que as barras ficam nas extremidades são contadas. Ou seja, estamos contando o número de soluções naturais dessa equação (inteiras não negativas).

Colocar barras nas extremidades seria como
++8+7 = 15

Entre esses +, seriam 0's. Ou seja?
0+0+8+7 = 15

Podemos considerar até as 4 barras nas extremidades, não é? (0,0,0,15) é uma solução possível formada por inteiros não negativos.

Basta lembrar que as soluções são 4-uplas ordenadas.

Então, na expressão de combinações completas (que eu nem sei se é essa que você colocou ai em cima, pois considero a fórmula desnecessária para mim no momento), essas soluções são contadas.

Mas existe um jeito de contar somente soluções inteiras positivas, ou seja, em que as barras nunca ficam nas extremidades. Nenhuma delas.

O que podemos fazer para garantir que tenhamos pelo menos 1 bola dentro de cada caixa? O que podemos fazer para garantir que as soluções são sempre positivas? Pode pensar diretamente na combinatória:

Se fomos colocar 19 elementos em 19 posições, o que fazer para que nenhuma das barras fique nas posições 1 ou 19, ou que nenhuma barra fique seguida da outra. Mas acho melhor pensar na dica de cima.

Pense nisso :)Ainda estou esperando a solução daquele problema, hein

Até

Meu primeiro raciocínio é contar o número de formas de distribuir as bolas (sem restrições) e subtrair das combinações em que há pelo menos uma solução nula. 
(não dê a resposta ainda, vou tentar fazer dessa forma)

(não esqueci do problema não, tá? Só que sou extremamente lento, mesmo   )

Pode dar certo  Go ahead.

Oi, 

vou arriscar uma resolução. 

Dispomos as 15 bolas, as quais determinam 16 espaços. 
Para que todas as "gavetas" contenham ao menos uma bola, as 4 barras não podem ficar nas extremidades e não podem ser consecutivas (isto é, deve haver uma e somente uma barra entre duas bolas). 

Para isso, podemos delimitar 14 espaços para as 4 barras, as quais determinarão 5 compartimentos. Essa condição é suficiente para evitar que duas barras ocupem o mesmo espaço entre duas bolas (já que 14 espaços contam exatamente um espaço entre cada bola) ou que elas fiquem nas extremidades (já que os 2 espaços das extremidades foram "descontados").
O problema se resume, então, em colocar as 4 barras nesses 14 espaços, o que pode ser feito de C14,4. 
Não precisamos permutá-las (e nem devemos), pois são indistinguíveis. 

Para todos os efeitos, minha resposta fica em C14,4. 

Aguardo um sinal verde/vermelho.