Número de carroséis possíveis

O Sr. Epaminondas deseja confeccionar um carrossel. Para isso, ele dispõe de 10 cavalinhos manchados e 10 cavalinhos pardos. Sabendo que ele pretende dispor os cavalinhos em vértices de icoságono regular, determine quantos são os carrossséis distintos que podem ser criados.

Suponho que trate-se de uma permutação circular e com elementos repetidos. Alguém propõe alguma saída para resolver sem ser enumerando cada caso?

Gabarito: 9252

Basta escolher 10 vértices para colocar os cavalos de um tipo e os outros estarão determinados. Logo há C20,10 maneiras distintas.

Rory Gilmore escreveu:Basta escolher 10 vértices para colocar os cavalos de um tipo e os outros estarão determinados. Logo há C20,10 maneiras distintas.

Não acho que seja isso, visto que tem as rotações. 

Reduzindo o número de cavalos para 4 para simplificar: 

Ficaria C(4,2) = 6 casos. São eles (1100, 1010, 1001, 0110, 0101, 0011). Observe que se tirarmos as rotações sobram 2 casos (1100, 1010).

Agora como resolve é outros 500

Oi Rory. Obrigado por responder!

Rory Gilmore escreveu:Basta escolher 10 vértices para colocar os cavalos de um tipo e os outros estarão determinados. Logo há C20,10 maneiras distintas.

Sim, eu imaginei algo do tipo, mas esse enunciado está na secção de permutações circulares do material que estou utilizando. No caso, nessas C20,10 combinações seriam gerados carrosséis iguais obtidos por rotação.

Eu vou pegar o gabarito às 18:00 h, acho que com ele talvez de para ter uma ideia.

Usando a ideia da Rory, junto com o que o Tales disse, são C(19, 10) maneiras distintas. 
Se você descartar as permutações circulares, só existe apenas 1 possibilidade para o primeiro cavalinho.

Boa noite colegas!
Aparentemente a solução é 9252.

O meu erro no comentário que fiz acima foi considerar que não existe sobreposição entre as permutações circulares. Por exemplo, 1010 (1a) 0101 (2a) 1010 (3a) 0101 (4a).

Dito isso, uma boa aproximação para o numero de permutações é (20 choose 10)/20 = 9237,8. Deve existir outro método mais viável.

Boa noite;
Eu vou apresentar uma solução, mas para entende-lá é necessário o conhecimento de dois tópicos "Número de soluções inteiras não negativas de uma soma de variáveis" e "Simetria de rotação"

Imagine que você posicione invariavelmente todos os cavalinhos pardos sobre uma circunferência em 10 pontos distintos. Com isso você gerará 10 arcos de circunferência delimitados cada um por dois pontos consecutivos na circunferência. Observe que conforme faz-se a distribuição dos 10 cavalinhos manchados sobre esses arcos, terá-se como resultado diferentes tipos de carrosséis. Em linhas gerais, como cada cavalinho manchado é para todos os fins indistinguível, podemos apenas considerar que os carrosséis serão analisáveis pela quantidade de cavalinhos que cada arco possuirá.

Numeremos cada um dos dez arcos de 1,2,3,4,5,6,7,8,9 e 10.
Defina-se [latex]x_i[/latex] o número de cavalinhos manchados para um dado arco de numeração i.

Por definição conclui-se que:

[latex]x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10[/latex]

A princípio representaremos cada carrossel como uma 10-upla ordenada da forma [latex](x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9, x_{10})[/latex]

Em tése, para cada carrossel representável por [latex](a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10})[/latex] existem dez permutações circulares, que podem ser idênticas ou diferentes numericamente falando(com isso eu digo a igualdade entre 10-uplas). Somente as 10-uplas distintas serão contabilizadas como soluções de [latex]x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10[/latex].

Se um carrossel [latex](a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10})[/latex] não apresentar simetria de rotação ele terá 10 permutações equivalentes e distintas, portanto ele será contabilizado 10 vezes nas soluções de [latex]x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10[/latex].

[latex]\scriptsize{(a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10}) \rightarrow( a_{10},a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9)\rightarrow

(a_9, a_{10}, a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8 )\rightarrow}[/latex]

[latex]\scriptsize{(a_8, a_9, a_{10}, a_1, a_2, a_3, a_4, a_5, a_6, a_7) \rightarrow

(a_7, a_8, a_9, a_{10}, a_1, a_2, a_3, a_4, a_5, a_6) \rightarrow

(a_6, a_7, a_8, a_9, a_{10}, a_1, a_2, a_3, a_4, a_5) \rightarrow}[/latex]

[latex](a_5, a_6, a_7, a_8, a_9, a_{10}, a_1, a_2, a_3, a_4) \rightarrow(a_4, a_5, a_6, a_7, a_8, a_9, a_{10}, a_1, a_2, a_3) \rightarrow(a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10}, a_1, a_2) \rightarrow[/latex]

[latex]\scriptsize{ (a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10}, a_1) \rightarrow (a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10}) \rightarrow ...}[/latex]


Se um carrossel [latex](a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8, a_9, a_{10})[/latex] apresentar simetria de rotação C_n, n>1 ele será contabilizado [latex]\frac{10}{n}[/latex] vezes nas soluções de [latex]x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10[/latex], note que n só pode assumir os valores 2, 5 e 10( divisores de 10, pois temos 10 arcos). Se ficou confuso dá uma olhada nos exemplos abaixo, creio que dê para clarear a ideia.

Exemplificação de cada simetria:
carrossel de simetria C₂ (a,b,c,d,e, a,b,c,d,e) repete em grupos de (a,b,c,d,e) 2 vezes
(3,2,0,0,0, 3,2,0,0,0) -->(0,3,2,0,0,0, 3,2,0, 0) --> (0,0, 3,2,0,0,0, 3,2,0) -->(0, 0,0, 3,2,0,0,0, 3,2) --> (2, 0, 0,0, 3,2,0,0,0, 3) --> ( 3, 2, 0, 0,0, 3,2,0,0,0) ... Observe que devido a simetria esse carrossel só admite cinco soluções distintas.

carrossel de simetria C₅ (a,b,a,b,a,b,a,b,a,b) repete em gupos de (a,b) 5 vezes:
(0,2,0,2,0,2,0,2,0,2) --> (2,0,2,0,2,0,2,0,2,0) --> (0,2,0,2,0,2,0,2,0,2) ... Observe que devido a simetria esse carrossel só admite duas soluções distintas

carrossel de simetria C₁₀ (a,a,a,a,a,a,a,a,a,a) repete em unidades de (a) 10 vezes:
(1,1,1,1,1,1,1,1,1,1) --> (1,1,1,1,1,1,1,1,1,1) --> .... Observe que devido a simetria esse carrossel só admite uma solução distinta

Por sua vez, permita-se que comecem os cálculos:

Os carrosséis que possuem simetria de rotação C₁₀:

Por hipótese:
[latex]\scriptsize{x_1= x_2 = x_3 =x_4 = x_5 = x_6 =x_7 =x_8 =x_9 =x_{10}\text{ }, \text{ } x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10 \implies }

\scriptsize{ 10x_1 = 10 \implies x_1 = 1 \implies x_1= x_2 = x_3 =x_4 = x_5 = x_6 =x_7 =x_8 =x_9 =x_{10} =1}[/latex]

Como os carrosséis do tipo C₁₀ são contabilizados 1 única vez temos um único carrossel com esse tipo de simetria.


Os carrosséis que possuem simetria de rotação C₅:

por hipótese [latex]x_1 = x_3 = x_5 = x_7 = x_9[/latex] e [latex]x_2 = x_4 = x_6 = x_8 = x_{10}[/latex]. Portanto:

[latex]\scriptsize{x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10 \implies 5(x_1 + x_2) = 10 \implies x_1 + x_2 = 2}[/latex]

Existem 3 soluções inteiras não negativas para a equação acima, destas uma é a solução de simetria C₁₀, portanto existem 2 soluções de simetria C₅.Cada carrossel do tipo C₅ é contabilizado duas vezes( [latex]\frac{10}{5} =2[/latex]), portanto temos um único carrossel com esse tipo de simetria.

Carrosséis com simetria C₂:

por hipótese [latex]x_1 = x_6 [/latex] e [latex]x_2 =x_7[/latex] e [latex]x_3 = x_8[/latex] e [latex]x_4 = x_9[/latex] e [latex]x_5 = x_{10}[/latex]. Portanto:
[latex]\scriptsize{x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10 \implies 2(x_1 + x_2 +x_3 +x_4 +x_5) = 10 \implies }[/latex]

[latex] x_1 + x_2 +x_3 +x_4 +x_5 = 5[/latex]

Existem [latex]\binom{9}{4} = 126 [/latex] soluções inteiras não negativas para a equação acima das quais uma é a solução de simetria C₁₀. Portanto, existem 125 soluções de simetria C₂, cada carrossel com esse tipo de simetria é contabilizado 5 vezes([latex]\frac{10}{2} = 5[/latex]). Portanto existem 25 carrosséis distintos com simetria C₂.

Carroséis sem simetria C₂, C₅ e C₁₀.

A equação [latex]x_1 + x_2 +x_3 +x_4 +x_5 +x_6 +x_7 +x_8 +x_9 +x_{10} = 10[/latex] possui [latex]\binom{19}{9} = 92378[/latex] soluções destas:
uma possui simetria C₁₀
duas possuem simetria C₅
cento e vinte e cinco possuem simetria C₂

Portanto existem [latex]\binom{19}{9}- 1- 2 - 125 = 92250 [/latex] soluções sem as tais simetrias, cada uma delas pelo que já foi dito é contabilizada 10 vezes. Portanto existem [latex]9225[/latex] carrosséis distintos desse tipo.

Somando todos os carrosséis obtidos [latex]9225 + 25 + 1 + 1 = 9252[/latex]

Creio que seja isso.
Bons estudos a todos

Oi João!

Obrigado pela ajuda! Consegui entender!

Eu quebrei a cabeça, mas consegui visualizar a situação.

Eu sei que você já ajudou bastante, mas eu fiquei com uma dúvida. Se eu quisesse replicar essa ideia com 20-upla's usando 0's pros cavalos manchados e 1's para os pardos. Ao invés de soluções inteiras, eu teria um certo número de permutações com elementos repetidos, certo? Como que ficaria a simetria olhando a partir dessas permutações? Pelo que entendi os carrosséis sem simetria de rotação iram gerar 20 permutações diferentes, mas como ficariam os simétricos?