Análisis Combinatorio

La teoría combinatoria toma sus conceptos fundamentales a partir de la teoría de conjuntos y se forma como un estudio sistemático orientado a contar sucesos, o combinaciones de los mismos.
Debemos entonces tener claros dichos conceptos e ideas y formular algunas más que funcionarán como base para la construcción de nuestro conocimiento.

Para poder continuar con nuestro procedimiento se considera necesario introducir el concepto de factorial, el factorial de n notado por n! es el producto de todos los enteros positivos menores o iguales a él, en otras palabras multiplicaremos los números desde 1 hasta n y el resultado será el factorial de n. Vale aclarar que el factorial de 0 es 1. Ésto se explica más adelante para el caso de los arreglos, pues la lógica es similar.
Esta idea surge a partir de uno de los primeros conceptos que trabajaremos, que es el de permutación.

Dado un conjunto N de n elementos llamaremos permutaciones de n elementos a todo conjunto que podemos formar cambiando el orden a los elementos de n. Éste valor se calcula como el factorial de n (n!).

$5! =5.4.3.2.1 $


Arreglo u Orden. (también se le conoce como Variaciones)

Llamaremos arreglo u orden n a todo conjunto ordenado de n elementos.

Observemos que, de acuerdo con esta definición, dos arreglos son iguales cuando tienen los mismos elementos, en el mismo orden y ésto no es menor, pues estamos diciendo que 2 subconjuntos que poseen los mismos elementos en distinto orden, representan arreglos distintos.
Tomemos ahora un conjunto M de m elementos.
Los arreglos de orden n (con n menor o igual a m) que pueden formarse con los elementos de M se llamarán arreglos de m elementos tomados de n, en otras palabras formaremos subconjuntos ordenados de n elementos a partir de los m que posee nuestro conjunto inicial, a éste número es al que nos referimos cuando hablamos de arreglos.

El número de estos arreglos, que no depende del conjunto que se tome sino de los valores de m y n, se indica como A^m_n o en algunos textos A_m, n.
Deberemos ahora realizar algunas especificaciones que nos permitirán calcular este valor.

Arreglos de Orden 0

El único arreglo de orden 0 es el conjunto vacío, por lo tanto A^m_0 = 1, para darle más significado a esto debemos recordar que el conjunto vacío es subconjunto de todos los conjuntos, por tanto podemos formalmente (aunque no resulte tan evidente) hablar de un subconjunto aunque no posee elementos existe y por tanto hay que contarlo como arreglo.

Arreglos de orden n>0

Puede formarse a partir de los de orden anterior (que es lo que se llama un método por recurrencia).
Para demostrarlo, supongamos que se han formado los arreglos de orden n-1, a partir de éstos formaremos los arreglos de orden n, para ello completamos cada arreglo de orden n-1, agregándole como último, cada uno de los elementos del conjunto M, sin repetir ninguno y que son m -(n-1)=m-n+1
Si presentamos como ejemplo m=4, M={a,b,c,d} y n=3, los Arreglos de orden 2 serán:

(agregando el tercer elemento)
________m-n+1
ab         abc      abd
ac         acb        acd
ad       adb      adc
ba       bac      bad
bc       bca      bcd
bd       bda      bdc
ca         cab      cad
cb         cba      cbd
cd         cda      cdb
da         dab      dac
db         dba      dbc
dc         dca      dcb

tenemos así una fórmula por recurrencia, de Esta manera podemos trabajar con una notación más compacta ayudándonos de la notación factorial

$A^4_3 = \frac{4!}{(4-3)!}$

La fórmula se cumple también para n=0 y n=1.

Combinaciones

Llamaremos combinaciones de m elementos tomados de a n (m>=n) a todos los conjuntos de n elementos que pueden formarse eligiendo éstos entre los m.
Esto es los subconjuntos de n elementos sacados de los m posibles. Como estos conjuntos no son ordenados, dos combinaciones son distintas si difieren en al menos un elemento, es útil aclarar que las combinaciones por este mismo hecho son menos que los arreglos.
El número de las combinaciones se indica por $C^m_n$ o (^0_n) y se calcula como $C^m_n = \frac{m!}{(m-n)!n!}$ , lo cual nos indica que las combinaciones son los arreglos sobre las permutaciones (recordemos que en las combinaciones el orden no es tomado en cuenta)

$C^m_n = \frac{A^m_n }{P_n}$

Combinaciones Complementarias

Cada combinación de n elementos deja fuera m-n elementos, con los que puede formarse otra combinación llamada complementaria de la primera.
El número de combinaciones complementarias es igual al número de combinaciones de orden n.

$C^m_{m-n} = C^m_n $