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:
Postar um comentário