combinatoria

A fórmula é simples de se deduzir, a partir do momento que analisamos o fato sob um outro ângulo:

Pense em P= {1; 2; 3}

Queremos fazer grupos de 5 algarismos.

Vamos criar uma notação para raciocinarmos.

Nosso 1º enfoque vai ser distribuir lugares (posições) pelos elementos (grupos).

Para particionarmos as posições por 3 grupos (1; 2; 3) podemos usar 2 barras (n-1):


_ _ _ _ _ // --> 1 1 1 1 1

_ _ /_ _ _ / --> 1 1 2 2 2

_ /_ _ _ /_ --> 1 2 2 2 3

_ /_ _ _ _ / --> 1 2 2 2 2

_ _ /_ _ _ / --> 2 2 3 3 3

/_ _ _ _ _ / --> 2 2 2 2 2

//_ _ _ _ _ --> 3 3 3 3 3


Também podemos enxergar da maneira mais imediata e distribuir os elementos pelos lugares:


////1 2 3 --> 1 1 1 1 1

//1 /2 /3 --> 1 1 1 2 2

/1 //2 3/ --> 1 2 2 2 3

/1 ///2 3 --> 1 2 2 2 2

1 ////2 3 --> 2 2 2 2 2

1 /2 /3 //--> 2 2 3 3 3

1 2 3 ////--> 3 3 3 3 3

...

Agora compreendida qualquer das notações, o problema :

Temos n (3) coisas (algarismos) para fazer grupos (números) com p (5) algarismos.

Ou temos p (5) lugares para oferecer a n (3) elementos (grupos).

Fica simples, ao o transformarmos pela notação num problema trivial:

Temos (n + p -1) (3 + 5 - 1 = 7) coisas para combinar 5 a 5 :

combR(n; p) = comb(n+p-1; p) = comb(n+p-1; n-1)

Ou, completamente equivalente, temos permutações de 7 elementos com 5 e 2 repetições:

combR(n; p) = (n+p-1)!/(p!(n-1)!)

Nesse caso:

combR(3; 5) = comb(7; 5) = comb(7;2) = = 7.6/2 = 21 algarismos crescentes, com repetições.