Problema de combinatória

3 respostas
E

Supondo o caso geral:
Temos um seqüência de N posições. Cada posição contém um valor, que pode variar entre a0 e an ([a0,an]). Quantas seqüências distintas que apresentem Y elementos de um mesmo valor previamente fixado consecutivos eu posso obter?

Uma particularização do caso:
Temos um cadeia de 7 bits. Cada bit, como sabemos, pode assumir o valor 0 ou o valor 1. Quantas seqüências distintas com três zeros consecutivos eu posso obter?

Gostaria de saber como posso resolver uma questão do tipo…O caso que me deparei foi o particular, tentei encontrar o caso geral para já tentar bolar alguma função que me devolva o resultado.

Agradeço desde já.

3 Respostas

ramonchiara

Olha, acredito que o que eu vou falar precise de alguns refinamentos (não é a resposta definitiva, mas sim um início de pensamento).

Algumas definições:

  • N = tamanho da sequência
  • Y = tamanho da cadeia de número consecutivos
  • 2 <= Y <= N (não faz sentido Y = 1)
  • N >= 2 (consequência de cima)
  • Z = número fixado
  • [a0, an] = domínio utilizado (base?)

Vamos pegar N = 4. Poderíamos ter:
Para Y = 2:

  1. Z Z _ _
  2. _ Z Z _
  3. _ _ Z Z
    Para Y = 3:
  4. Z Z Z _
  5. _ Z Z Z
    Para Y =4:
  6. Z Z Z Z

ou seja, a quantidade de sequências = N - Y + 1

Agora, precisa pensar mais um pouco… rsrsrsrs

ramonchiara

Pensei no seguinte caso:

N = 7
Y = 3

Como você considera o seguinte caso:
Z Z Z _ Z Z Z
???

maquiavelbona

Isso sem considerar as permutações e as combinações internas.
ZZZZ_ _ _ são 2 combinações ZZZ diferentes.

Eu tava tentando formalizar isso ontem a noite, mas deixei de lado. Hoje se conseguir lembrar algo ou conseguir formalizar, coloco aqui.

Até!

Criado 24 de julho de 2008
Ultima resposta 25 de jul. de 2008
Respostas 3
Participantes 3