Marathoncode: Combinatória Básica ||

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 é

$\binom {11} {1,4,4,2} = \frac{11!}{4!4!2!} = 34650$

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 $n \rightarrow$ e $n \downarrow$ . Logo, o número de rotas é dado pelo número de permutações com repetições do multiset com $n \rightarrow$ e $n \downarrow$ .

$\binom {2n} {n,n} = \frac{2n!}{n!n!}$

Para n = 2, temos $\binom {4} {2,2} = \frac{4!}{2!2!} = \frac{24}{4} = 6$ rotas possíveis.

Problema 2: Determinar quantas soluções inteiras não-negativas existem para a equação $x_1 + x_2 + ... + x_n = C$ , onde $0 \leq x_i \leq C , \forall i = 1 \ldots n$

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

$\binom {n-1+C} {n-1,C} = \frac{(n-1+C)!}{(n-1)!C!}$

Nenhum comentário:

Postar um comentário