sexta-feira, 2 de março de 2012

Combinatória Básica ||

Número de permutações com repetições
Em alguns problemas, precisamos contar o número de maneiras diferentes de permutar um multiset de n elementos e ki são as multiplicidades de cada um dos distintos elementos. Por exemplo, o número de permutações distintas das letras da palavra MISSISSIPPI, que tem 1M,4 Is , 4Ss e 2Ps é

 

Problema 1 :  Contar o número de rotas do canto superior esquerdo para o cantor inferior direito de um grid n x n.Os únicos movimentos permitidos é para lado e para baixo.

No grid 2x2, temos 6 rotas possíveis de um canto superior esquerdo para o inferior direito.

 Este problema aparece no problema 15 do project Euler.

No grid nxn, uma rota é formada por e   . Logo, o número de rotas é dado pelo número de permutações com repetições do multiset com  e   .


Para n = 2, temos rotas possíveis.

Problema 2:  Determinar quantas soluções inteiras não-negativas existem para a equação , onde 

Cada solução dessa equação pode ser escrita como um conjunto com n-1 separações e C bolinhas.
 
Suponha n=5 e C=8, teremos a seguinte solução possível
*|***|*|**|*
X1=1, X2 = 3, X3 = 1, X4 = 2 e X5 = 1
**|**||***|*
X1=2, X2 = 2, X3 = 0, X4 = 3 e X5 = 1

Logo, o número de soluções não-negativas possíveis é dada por 
 

Nenhum comentário: