licenciada

COMBINATORIA


Definición:
Una permutación es un arreglo en un orden particular de los objetos que forman un conjunto, y la cantidad de permutaciones posibles de robjetos de un conjunto de tamaño n viene dado por:

P(n, r) = n! / (n – r)! = n (n – 1) .......(n – r + 1)

Otras notaciones: nPr , , (n)r .

Definición:
Unacombinación de los objetos de un conjunto es una selección de éstos sin importar el orden y la cantidad de las mismas viene dado por:

= P(n, r) / r! = n! / [(n – r)!r!]



Otras notaciones: C(n, r) , nCr , , Cn,r .


Teorema.
Con m elementos a1, a2, ......, am y n elementos b1, b2, ......, bm es posible formar m∙npares distintos que contienen un elemento de cada grupo.

Teorema.
El número de formas en las que se pueden asignar n objetos distintos en k grupos diferentes quecontienen n1, n2, ......, nk objetos respectivamente es:

N = n! / (n1! n2! ...... nk!) , ∑i=1,k ni = n ,

también se denota por:

n

n1 n2 ...... nkPermutaciones y combinaciones con reemplazo.

Se habla de permutaciones y combinaciones con reemplazo cuando el mismo elemento puede ser tomado más de una vez, ylas respectivas expresiones son:

P(n ,k) = nk

C(n, k) = C(n + k – 1, k)


Algunas Igualdades Importantes

I.1.- C(n, k) = C(n, n – k)

I.2.- C(n+1,k) = C(n, k) + C(n, k – 1)

I.3.- ∑i=k, n C(i, k) = C(n + 1, k + 1)

I.4.- ∑j=0, n C(n, j) = 2ⁿ

I.5.- ∑j=0, n C(a, j) C(b, n-j) = C(a + b, n)

I.6.- C(n, k) =(n/k) C(n-1, k-1)

C(n, k) = ((n-k+1)/k) C(n, k-1)

C(n, k) = (n/(n-k)) C(n-1, k)

I.7.- C(n, 0) = C(n, n) = 1

I.8.- C(n, 1) = C(n, n - 1) = n