Combinatoria

Tema
4

Combinatoria y recurrencia

Principio de inclusión exclusión. Permutaciones con y sin repetición. Combinaciones con y sin repetición. Fórmulas combinatorias. Teorema binomial. – ENTRA HASTA AQUÍ – Sucesiones definidas por recurrencia. Resolución de ecuaciones recurrentes por iteración. Relaciones de recurrencia de orden superior concoeficientes constantes. Funciones definidas recurrentemente.

Principios fundamentales del conteo

Principio de la adicción
Si se puede realizar una primera tarea de m maneras, mientras que una segunda se puede efectuar de n maneras, y no se pueden realizar las dos a la vez, entonces tenemos un repertorio de m+n maneras de realizar una tarea.

Principio de la multiplicación
Si un procedimientose puede separar en las etapas primera y segunda, y si hay m posibles resultados para la primera etapa y n para la segunda, entonces el procedimiento total se puede realizar, en el orden designado, de m·n maneras.

Principio de la distribución
Sean m,n,p números naturales ((0). Si se distribuyen np+m objetos en n cajas entonces alguna caja deberá contener, al menos, p+1 objetos.Demostración: Supongamos que contienen menos de p+1, por ejemplo, p objetos; entonces, el número total de objetos contenidos en las n cajas será como máximo np0. Por tanto, al menos una de las cajas debe contener, como mínimo, p+1 objetos.

Corolario
Dados n números enteros positivos m1, m2, ..., mn tal que
[pic]
entonces para algún 1 ( i ( n se tiene que mi>p.
Demostración: Observemos enprimer lugar que el resultado es obvio para n=1, ya que si (m1/1)>p entonces m1>p.
La desigualdad del enunciado puede escribirse como [pic]. Así, existe m>0 tal que [pic]
Supongamos que disponemos de n cajas y que mi es el número de elementos de cada caja, por el principio de la distribución alguno de los mi debe ser estrictamente mayor que p.

Permutaciones, variaciones, combinaciones

Paraun entero n ( 0, n factorial, expresado n!, se define por:
0! = 1,
n! = (n)·(n–1)·(n–2)·...·3·2·1, para n (1

Según la regla del producto, las maneras de escoger n elementos de entre un total de N según un determinado orden, son igual al producto de n operandos de la forma
N·(N-1)·(N-2)·...·(N-n+1)
Esta expresión se conoce como Variaciones de N tomadas de n en n, y se representacomo VN , n.

Para llegar a una versión simplificada se opera así[1]:
N(N–1)(N–2) ... (N–n+1)·[pic]

En el caso especial en que N=n, se llama permutaciones de N, y se representa PN. [pic]

En general, si hay N objetos con n1 de un primer tipo, n2 de un segundo tipo, ..., y nr de un r–ésimo tipo,
donde n1 +n2 +...+nr = N, entonces hay [pic] permutaciones de los objetos dados.

Si setratase de escoger n elementos pudiendose repetir cualquiera, el repertorio donde escoger no disminuiría y la expresión sería el producto de n veces N:
N·N·...·N = Nn
Esta expresión se conoce como Variaciones con repetición y se representa como [pic].

Notese que cuando calculabamos VN,n estabamos hallando el número de grupos de n elementos distintos, multiplicado por el número deposibilidades de ordenar internamente esos grupos de n elementos (PN).
Si quisieramos hallar el número de maneras de escoger n de entre N elementos distintos sin repetición y sin orden tendríamos la expresión
[pic], que se llama combinanciones de N tomadas de n en n y se representa CN,n ó [pic].

En general, dados N objetos distintos de los cuales se quiere tomar n objetos con repetición, sunúmero sera [pic].
En consecuencia, el número de combinaciones con repetición de N objetos, tomados de n en n, es C(N+n–1,n).

Resumen

Variación es el número de ordenaciones de n elementos tomados de un total de N.
Permutación es el número de ordenaciones de los N elementos de un conjunto.
Variación con repetición es el número de ordenaciones de n elementos, tomados repetidos o no,...