Combinatoria

TEMA 8. COMBINATORIA


8.1. Principios básicos:

Principio de adició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, este es el fundamento del principio de la adición o regla de la suma, formalmente diremosque:
“El cardinal de la unión de conjuntos disjuntos es la suma de los cardinales de dichos conjuntos”.
Notación: cardinal de S = | S | = #S = card(S)
Por convenio se considera que |  | = 0.

Sean A1, A2, ..., An conjuntos finitos tales que Ai  Aj =   i  j, entonces:
= |A1| + |A2| +  + |An|
Demostración por inducción.

Principio de multiplicación:
Si un procedimiento se puedeseparar 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, este es el fundamento del principio de la multiplicación o regla del producto, formalmente:
Sean A1, A2, ..., An conjuntos finitos no vacíos, entonces:
| A1·A2·....·An | = | A1 |·| A2|·....·| An |
En el principio de la multiplicación no se tiene en consideración si los conjuntos son o no disjuntos ya que el producto viene dado por un vector cuyas coordenadas, lógicamente, no son necesariamente diferentes. En el caso particular del producto de dos conjuntos A, B, los pares obtenidos son pares ordenados, (a, b)  (b, a).
Demostración por inducción.

Principio de distribución:Este principio también es conocido como principio del Cajón de Dirichlet, principio de las casillas o del palomar.

Sean m, n, p tres números naturales dados. Si se distribuyen (n·p + m) objetos en n cajas, entonces alguna caja deberá contener al menos (p + 1) objetos.

Corolario: Dados n números positivos cuya suma sea m tales que > p, entonces al menos uno de ellos es, necesariamente, mayorque p.
> p   i, 1  i  n / mi > p

Es decir, si se efectúa una partición en n partes de un conjunto T finito, entonces al menos una de las partes posee o más elementos.

Este principio se utiliza con frecuencia, una de sus principales aplicaciones es que dados (p + 1) números enteros al menos dos de ellos han de ser congruentes módulo p.


8.2. Permutaciones:

Sea A un conjuntofinito no vacío. Una permutación de A es una biyección de A en A. Dos permutaciones son diferentes si lo son las biyecciones a las que corresponden.
: A  A
Una permutación de A se puede considerar una ordenación de A.

Sean 1, 2 dos permutaciones de A, llamamos producto de 1 y 2 a la permutación (a) = 2(1(a)), a  A.
El conjunto de todas las permutaciones de A con la operaciónproducto tiene estructura de grupo, se denomina grupo simétrico de A. (SA)

Teorema:
Sean A y B conjuntos de n elementos cada uno, entonces el número de biyecciones distintas de A en B es n!
Si A = B la biyección se denomina permutación.
El número de permutaciones de n elementos es:
Pn = P(n) = n!
El producto de permutaciones no es conmutativo.

En la práctica las permutaciones nospermiten calcular el número de ordenaciones que se pueden obtener con n objetos diferentes entre sí.
Ejemplo: cómo colocar en un estante todos los tomos de una enciclopedia.


8.3. Variaciones:

Sea A un conjunto finito con n elementos y r  n  N.
Una variación de orden r de A es una lista ordenada de r elementos de A.
Dos variaciones son diferentes si algún elemento de las dos listases diferente o algún elemento se encuentra en distinto orden.
Vn,r = V(n, r) = variaciones de n elementos tomados de r en r.
Una variación es una aplicación inyectiva.
: 1,2,...,r  A
Una permutación es una variación de n elementos tomados de n en n. P(n) = V(n, n)

Teorema:
Sean A, B distintos del vacío, con |A| = r, |B| = n, r  n. El número de aplicaciones inyectivas de A en...