Elementos em fila (alguns separados) [Por responder]

[dininis]

Boas!
Este tipo de exercicio ainda nao percebi muito bem a logica por detras do mesmo... nem tao pouco como se chega a solucao...

Exercicio: 10 elementos em fila (a,a,b,b,b,c,c,c,c,d)
- De quantas maneiras diferentes se pode dispor estes elementos em fila sem que:
a) os elementos 'b' fiquem juntos
b) os elementos 'c' fiquem juntos

Cumprimentos!

[Fraol]

Oi,

Vamos pensar sobre o item a) (sem que) os elementos 'b' fiquem juntos.

Uma maneira de resolver isso é contar quantas maneiras podemos dispor os 10 elementos em fila ( \(= 10!\) ) e subtrair desse resultado a quantidade de maneiras nas quais os 'b' ficam juntos \(( = 8! )\).

Concorda?

[dininis]

(Estive para responder ontem mas pelos vistos existe um limite de 2 mensagens por dia...)

Esqueci-me de mencionar um pormenor... Todos os elementos b devem ficar separados... ou seja, "bb" tambem devera ser descartado.

Penso que seria 10! - 8! - 9! mas o livro da-me um resultado completamente diferente.

8!: Tres elementos "b" juntos
9!: Dois elementos "b" juntos

[jorgeluis]

dininis,
veja se o resultado é este:

a)

\(\frac{10!}{2!3!4!} - \frac{8!}{2!4!} =
12600 - 840 =
11760\)

b)

\(\frac{10!}{2!3!4!} - \frac{7!}{2!3!} =
12600 - 420 =
12180\)

[dininis]

dininis,
veja se o resultado é este:

a)

\(\frac{10!}{2!3!4!} - \frac{8!}{2!4!} =
12600 - 840 =
11760\)

b)

\(\frac{10!}{2!3!4!} - \frac{7!}{2!3!} =
12600 - 420 =
12180\)

O que pretendo com esta questao e verificar se existe alguma forma de solucionar este tipo de problema. O espaco amostral que forneci e aleatorio

Tenho dois problemas desse genero:
S={M1,M2,M3,M4,F1,F2,B1,B2,B3} ou seja, 4 livros de matematica, 2 de fisica e 3 de biologia
Pergunta: de quantas formas se podem arrumar os livros, em fila, de modo que todos os livros de biologia fiquem separados.
Solucao dada pelo livro: 151'200

S={A,K,Q,J,10,9,8} Sao cartas de jogo
Pergunta: Em quantas filas diferentes se podem dispor as cartas de modo que nao fiquem duas cartas com numeros seguidas?
Solucao dada pelo livro: 1440
Esse numero pode ser obtido por 2!*6! (numero de formas que existem de duas cartas estarem juntas, vezes o numero de formas que as mesmas podem trocar entre si)
Nao consigo, de forma alguma, que saiba, de aplicar isso ao primeiro exercicio... Coloquei aqui a questao, para saber se, de facto, as solucoes estao erradas.

OBS: Nao tenho acentuacao neste teclado... Sorry :/

[Fraol]

Boa noite dininis,

Estava pensando neste problema e percebi minhas limitações em problemas de contagem. Como não consegui uma regra mais prática até então, resolvi abordar a análise de casos. Por motivos óbvios, trabalhei agora há pouco no caso das cartas

S={A,K,Q,J,10,9,8} Sao cartas de jogo
Pergunta: Em quantas filas diferentes se podem dispor as cartas de modo que nao fiquem duas cartas com numeros seguidas?

.

Montei uma tabela com os possíveis casos em não se tem dois números juntos:

Na tabela acima, \(N\) indica que um número ocupará aquela posição. Pelas restrições do problema, as posições vizinhas serão ocupadas por cartas não numéricas.

Nesse caso discreto, 7 elementos, é relativamente rápido montar a tabela pensando em cada caso possível. Para problemas com mais elementos, dependendo dos arranjos pretendidos, pode não ser viável.

[dininis]

Hmm... Dará para fazer algum tipo de função para calcular esse número de linhas?
Raciocinio:

Spoiler:

Pela ultima posição dá para ver o seguinte: 5+4+3+2+1+4+3+2+1+3+2+1+2+1+1 = 35
ou seja, (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + (1)

A meu ver, isso parece-me um padrão qualquer... Deve existir alguma fórmula para isso...
E = Numero de Elementos = 3
P = Numero de Posições = 9
n = P que o primeiro elemento pode tomar = P-2(E-1)
\(T_{n} = n+(T_{n-1})\), \(T_{0} = 0\)
\(T_{1} = 1\) - - - - - \(T_{2} = 2 + T_{1}\) - - - - - \(T_{3} = 3 + T_{2}\) - - - - - \(T_{4} = 4 + T_{3}\) - - - - - \(T_{5} = 5 + T_{4}\)
Ou seja,
\(T_{5} = 5 + 4 + 3 + 2 + 1\) - - - - - \(T_{4} = 4 + 3 + 2 + 1\) - - - - - \(T_{3} = 3 + 2 + 1\) - - - - - \(T_{2} = 2 + 1\) - - - - - \(T_{1} = 1\)

Solução:
\(L_{5}\) = Número de Linhas = \(T_{5}\) + \(T_{4}\) + \(T_{3}\) + \(T_{2}\) + \(T_{1}\)

Na prática... Acho que Funciona (nestes dois exercícios, pelo menos)
1º Exercício

Spoiler:

E = 3
P = 9
n = P-2(E-1)=9-4=5

\(L_{5}\) = \(T_{5}\) + \(T_{4}\) + \(T_{3}\) + \(T_{2}\) + \(T_{1}\)
\(L_{5}\) = (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + (1) = 35
35*(3!*6!)=35*4320=151200

2º Exercício

Spoiler:

E = 3
P = 7
n = P-2(E-1)=7-4=3

\(L_{3}\) = \(T_{3}\) + \(T_{2}\) + \(T_{1}\)
\(L_{3}\) = (3+2+1) + (2+1) + (1) = 10

10*(3!*4!)=1440

A - B - A - B
E=2 ----- P=4 ----- n=4-2=2
\(L_{2}\) = 2+1 + 1 = 4
4*2!*2! = 16

Parece-me bem...

Anexos

Screenshot_1.png (30.11 KiB) Visualizado 3811 vezes

[Fraol]

Boas,

O raciocínio é interessante, parabéns. Acho que é um caminho analisar o padrão. Eu testei para E=3 e P=5 e deu Ok. Para E=2 e P=6 parece que falhou.

[dininis]

Para E=2 e P=6 parece que falhou.

Estive a analisar melhor e verifiquei que o "n" apenas funciona com 3 Elementos...

Voltando ao inicio, então.
n = Número de Elementos (Superior ou igual a 1)
p = Número de Posições (Superior ou igual a 2n-1)
\(^{n}\textrm{L}_{p}\) = Número de Linhas
\(^{n}\textrm{C}_{p}\) = Número de Casos = \(^{n}\textrm{L}_{p}\) x n! x (p-n)!

\(^{1}\textrm{L}_{p}\;=\;p\)
\(^{2}\textrm{L}_{p}\;=\;^{1}\textrm{L}_{p-2-0}\;+\;^{1}\textrm{L}_{p-2-1}\;+\;...\;+\;^{1}\textrm{L}_{2n-1}\)
\(^{3}\textrm{L}_{p}\;=\;^{2}\textrm{L}_{p-2-0}\;+\;^{2}\textrm{L}_{p-2-1}\;+\;...\;+\;^{2}\textrm{L}_{2n-1}\)
\(^{4}\textrm{L}_{p}\;=\;^{3}\textrm{L}_{p-2-0}\;+\;^{3}\textrm{L}_{p-2-1}\;+\;...\;+\;^{3}\textrm{L}_{2n-1}\)
\(^{5}\textrm{L}_{p}\;=\;^{4}\textrm{L}_{p-2-0}\;+\;^{4}\textrm{L}_{p-2-1}\;+\;...\;+\;^{4}\textrm{L}_{2n-1}\)

Ou seja,
\(^{n}\textrm{L}_{p}\;=\;^{n-1}\textrm{L}_{p-2-0}\;+\;^{n-1}\textrm{L}_{p-2-1}\;+\;...\;+\;^{n-1}\textrm{L}_{1}\)

Vamos ver se funciona assim...

Spoiler:

1) n=1 ----- p=4
\(^{1}\textrm{L}_{5}\;=\;4\)

2) n=2 ----- p=6
\(^{2}\textrm{L}_{6}\;=\;^{1}\textrm{L}_{4}\;+\;^{1}\textrm{L}_{3}\;+\;^{1}\textrm{L}_{2}\;+\;^{1}\textrm{L}_{1}\;\Leftrightarrow \;
\Leftrightarrow \;^{2}\textrm{L}_{6}\;=\;4\;+\;3\;+\;2\;+\;1\)

3) n=3 ----- p=8
\(^{3}\textrm{L}_{8}\;=\;^{2}\textrm{L}_{6}\;+\;^{2}\textrm{L}_{5}\;+\;^{2}\textrm{L}_{4}\;+\;^{2}\textrm{L}_{3}\;\Leftrightarrow
\Leftrightarrow \;^{3}\textrm{L}_{8}\;=\;4+3+2+1\;+\;3+2+1\;+\;2+1\;+\;1\)

4) n=4 ----- p=10
\(^{4}\textrm{L}_{10}\;=\;^{3}\textrm{L}_{8}\;+\;^{3}\textrm{L}_{7}

\;\;\;\;\;^{3}\textrm{L}_{8}\;=\;^{2}\textrm{L}_{6}\;+\;^{2}\textrm{L}_{5}\;+\;^{2}\textrm{L}_{4}\;+\;^{2}\textrm{L}_{3}\;=\;4+3+2+1\;+\;3+2+1\;+\;2+1\;+\;1
\;\;\;\;\;^{3}\textrm{L}_{7}\;=\;^{2}\textrm{L}_{5}\;+\;^{2}\textrm{L}_{4}\;+\;^{2}\textrm{L}_{3}\;=\;3+2+1\;+\;2+1\;+\;1

^{4}\textrm{L}_{10}\;=\;4+3+2+1\;+\;3+2+1\;+\;2+1\;+\;1\;\;\;+\;\;\;3+2+1\;+\;2+1\;+\;1\)

Resumidamente, sim! Com um pouco mais de análise deve dar para simplificar isso bastante (Segue em anexo o exercício 4). Dá para verificar o seguinte:
se n=3 e p=8; L=4(1)+3(2)+2(3)+1(4)
se n=4 e p=10; L=10(1)+6(2)+3(3)+1(4)
se n=5 e p=12; L=20(1)+10(2)+4(3)+1(4)
se n=6 e p=14; L=35(1)+15(2)+5(3)+1(4)

Provavelmente em exame este tipo de exercício apenas deverá sair com n=2 ou n=3. Vou prosseguir com a matéria

[dininis]

(esqueci-me do anexo... Aí vai!)

OBS: Estou a assumir que não é possível editar mensagens já enviadas!

Anexos