Segundo semestre de Matematica

INTRODUCCION AL ANALISIS COMBINATORIO

Cuántas veces no hemos querido saber de cuantas formas es posible combinar un número determinado de tenis con un cierto número de pantalones, playeras y demás prendas, cuántas veces hemos querido saber que probabilidad hay de sacarse la lotería si se juegan números de dígitos, todos estos problemas competen a una rama del álgebra que se llama “análisis combinatorio” que a groso modo es la teoría que estudia los diversos arreglos o selecciones que podermos formar con los elementos de un conjunto dado[1] esta teoría parte de un concepto muy fácil de entender (en el campo de los naturales por lo menos) el concepto de factorial que a continuación definiremos.

Definición: Sea talque . Definimos el factorial de () por inducción como sigue:

1.
2.De esta definición podemos concluir que el factorial se puede expresar como:



O bien con un ejemplo, calcularemos el factorial de esto es

Este peculiar número calcula lo que llamamos Permutaciones que por definición es el número de ordenaciones posibles de los elementos de un conjunto finito, esto sin tomar en cuenta las repeticiones. Por ejemplo tenermos una enciclopedia de 5 tomos, y los vamos a acomodar en un estante, nótese que no nos interesa el orden de los tomos, sólo queremos saber de cuántas maneras posibles podemos arreglar los libros. Hacemos el siguiente análisis, en el primer sitio caben cinco libros, colocamos uno, ahora en el segundo sitio nos quedan cuatro libros, y así sucesivamente, entonces tenemos el siguiente arreglo:

Cinco Tomos Cuatro Tomos Tres Tomos Dos Tomos Un tomo
5 4 3 2 1

Donde los números del segundo renglón indican el número de tomos disponibles, así tenemos un total de formas distintas formas de ordenar los libros, esto sin atender al orden.

Qué pasaría si en lugar de tener cinco lugares y cinco elementos, ahora tenemos más elementos que lugares, ¿que pasaría entonces? Bueno entonces pasaría que tendríamos otra clase de problema, en dónde tendríamos que elegir un subconjunto de elementos de uno más grande con elementos, por ejemplo, deseamos saber de cuantas formas es posible formar subconjuntos de 3 elementos en un grupo de 10 elementos. Supongamos que tenemos un grupo de 10 alumnos y queremos saber cuántos equipos de 3 alumnos se pueden formar, una vez más sin atender al orden.

Para atacar este problema debemos visualizar que pasa con el primer elemento, tenemos pues 10 formas de escoger este primer elemento, luego este hará pareja con otro de los nueve, y estos a su vez con cualquiera de los ocho restantes, esto es pero esto es igual a hacer lo siguiente:





En este desarrollo se toma en cuenta el orden para escoger los elementos, porque sólo tomamos en cuenta tres elementos y los fijamos, pero no queremos eso, queremos obtener el número de subconjuntos de tres elementos sin importar el orden, es decir la terna suponiendo que los integrantes del salón tienen nombres como I, II, etc. sería distinto escoger (I, II, III), (II, I, III), (III, II, I), (II, III, I), (III, I, II) y (I, III, II) pero es en sí el mismo conjunto, entonces para solucionar este problema tenemos que quitar también los arreglos sobrantes que en este caso son entonces dividiendo entre este número quitaremos los conjuntos “repetidos” así las cosas queda de esta forma.



De este modo llegamos al coeficiente binomial, defido como:



Dónde nos indica el número de subconjuntos de tamaño tomados de un conjunto de elementos, también llamadas Combinaciones de k elementos tomadas en n. Claramente ya que de ser igual solo habría un posible conjunto, de ser mayor sería cero, porque no podemos escoger un subconjunto de más de elementos.

Por último que pasaría si deseamos ahora, saber de cuantas formas es posible ordenar un conjunto de dígamos elementos en un arreglo de elementos, pero con repetición, este es el caso más sencillo, dado que cuando hay repeticiones podemos pensar en que cada lugar del estante puede albergar elementos, tenemos que las ordenaciones serían:



Por ejemplo pensemos en las placas de un automovil, supongamos que en cierto país las placas de los vehículos tienen tres dígitos y que en cada dígito se puede escoger uno de 24 símbolo, repitiendo los dígitos quedarían (X,Y,Z) dónde X,Y y Z pueden tomar cualquiera de los 24 símbolo posibles, entonces tendríamos un total de placas. De manera más general si queremos saber de cuántas formas podemos ordenar con repetición un conjunto de elementos en espacios disponibles, la formula general está dada por: