COMBINATORIA

Concepto o definición:

La combinatoria es una rama de la matemática perteneciente al área de matemáticas discretas que estudia la enumeración, construcción y existencia de propiedades de configuraciones que satisfacen ciertas condiciones establecidas.

Combinatoria enumerativa

La combinatoria enumerativa o enumeración estudia los métodos para contar (enumerar) las distintas configuraciones de los elementos de un conjunto que cumplan ciertos criterios especificados.

Esta fue una de las primeras áreas de la combinatoria en ser desarrollada, y como otras áreas más recientes se estudian sólo en cursos especializados, es común que se haga referencia a esta subárea cuando se menciona combinatoria en entornos escolares.

Ejemplo:

Considérese el conjunto

S = {A, E, I, O, U}

. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.

Un primer problema podría consistir en hallar el número de formas diferentes en que podemos sacar las tarjetas una después de otra (es decir, el número de permutaciones del conjunto).Por ejemplo, dos formas distintas podrían ser: EIAOU o OUAIE.

Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto).En este caso, ejemplos pueden ser IOU, AEI o EAI.

También se puede preguntar sobre cuáles son los posibles grupos de 3 tarjetas que se pueden extraer, sin dar consideración al orden en que salen (en otras palabras, el valor de un coeficiente binomial).Aquí, consideraríamos AOU y UAO como un mismo resultado.

Otro problema consiste en hallar el número de formas en que pueden salir 5 tarjetas, una tras otra, pero en cada momento se regresa la tarjeta escogida al sombrero. En este problema los resultados posibles podrían ser EIOUO, IAOEU o IEAEE.

La combinatoria enumerativa estudia las técnicas y métodos que permiten resolver los problemas anteriores, así como otros más complejos, cuando el número de elementos del conjunto es arbitrario. De esta forma, en el primer ejemplo la generalización correspondiente es determinar el número de formas en que se pueden ordenar todos los elementos de un conjunto con n elementos, siendo la respuesta el factorial de n.

Números combinatorios.

Factorial de un número natural

Para todo entero positivo n, el factorial de n o n factorial se define como el producto de todos los números enteros positivos desde 1 hasta n. Es decir

$n! = 1 \times 2 \times 3 \times 4 \times ... \times (n-1) \times n \,$

La multiplicación anterior se puede simbolizar también como:

n! = n x (n - 1) x (n - 2) x (n - 3) x ..... x 1

En general:

$n! = \prod_{k=1}^n k$

La operación de factorial aparece en muchas áreas de las matemáticas, particularmente en combinatoria y análisis matemático. De manera fundamental, el factorial de n representa el número de formas distintas de ordenar n objetos distintos. Este hecho ha sido conocido desde hace varios siglos, en el s. XII por los estudiosos indios. La notación actual n! fue usada por primera vez por Christian Kramp en 1803.

Cero factorial

La definición indicada de factorial es válida para números positivos. Es posible extender la definición a otros contextos introduciendo conceptos más sofisticados, en especial es posible definirla para cualquier número real excepto para los números enteros negativos y para cualquier número complejo exceptuando de nuevo los números enteros negativos.

Una extensión común, sin embargo, es la definición de factorial de cero. De acuerdo con la convención matemática de producto vacío, el valor de 0! debe definirse como 0!=1.

Es posible, sin embargo, dar un argumento intuitivo para justificar la elección, como sigue:

Para cada número entero positivo n mayor que 1, es posible determinar el valor del factorial anterior mediante el uso de la siguiente identidad:

$(n-1)! = \frac{n!}{n}$ ,

válida para todo número mayor o igual que 1.

Así, si se conoce que 5! es 120, entonces 4! es 24 porque

4!= $\frac{5!}{5} = \frac{120}{5}=24$ ,

y por tanto 3! debe ser necesariamente 6 puesto que

3!= $\frac{4!}{4} = \frac{24}{4} = 6$ .

El mismo proceso justifica el valor de 2! = 2 y 1!=1 ya que

$2!=\frac{3!}{3}=\frac{6}{3}=2,\qquad 1!=\frac{2!}{2} =\frac{2}{2}=1.$

Si aplicamos la misma regla para el caso extremo en que n'=1 tendríamos que 0! corresponde a

$0!=\frac{1!}{1} = \frac{1}{1} = 1$

Aunque el argumento puede resultar convincente, es importante tener en cuenta que no es más que un argumento informal y que la razón real por la cual se toma la convención de 0! = 1 es por ser un caso especial de la convención de producto vacío usada en muchas otras ramas de las matemáticas.

Coeficiente binomial

Los coeficientes binomiales, números combinatorios o combinacionesson números estudiados en combinatoria que corresponden al número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado. Sin embargo, dependiendo del enfoque que tenga la exposición, se pueden usar otras definiciones equivalentes.

Definición combinatoria

Se tiene un conjunto con 6 objetos diferentes {A,B,C,D,E,F}, de los cuales se desea escoger 2 (sin importar el orden de elección). Existen 15 formas de efectuar tal elección:

El número de formas de escoger k elementos a partir de un conjunto de n, puede denotarse de varias formas:

$C(n,k)\,$ , $n\, C\, k\,$ , $C^n_k\,$ , o ${n\choose k}$ .

Así, en el ejemplo anterior se tiene entonces que C(6,2)=15, puesto que hay 15 formas de escoger 2 objetos a partir de un conjunto con 6 elementos.

Los números C(n,k) se conocen como «coeficientes binomiales», pero es frecuente referirse a ellos como «combinaciones de n en k», o simplemente «n en k». Por tanto, la primera definición es:

El coeficiente binomial ${n\choose k}$ es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

Definición algebraica

La definición no permite calcular el valor de los coeficientes binomiales, salvo listando los subconjuntos y contándolos. Sin embargo, existe una fórmula explícita que nos proporciona el valor de C(n,k).

Supongamos que el conjunto original tiene 5 elementos,{A,B,C,D,E}, de los cuales se deben escoger 3. Al momento de escoger el primero, se tiene 5 opciones disponibles, pero una vez fijo el primero, sólo hay 4 opciones para el segundo, y por tanto sólo 3 opciones para el último (pues no se puede repetir los escogidos en los primeros 2 pasos). De este modo, la selección puede hacerse de 5×4×3=60 formas.

Sin embargo, en tal conteo, el orden en que se escogen los elementos hace diferencia. Por ejemplo, tomar C, luego B, luego E, es una selección diferente de tomar B, luego C y luego E. Pero en la definición de coeficiente binomial, no importa el orden en que se eligen los objetos, únicamente cuáles se escogen. Por tanto, las elecciones BCE, BEC, CEB, CBE, ECB y EBC son todas equivalentes. Del mismo modo, las elecciones ABC, ACB, BCA, BAC, CAB y CBA son equivalentes, y así para cualquier terna de letras.

De esta forma, el resultado obtenido (60) no es la cantidad de subconjuntos de 3 elementos de {A,B,C,D,E}, sino que cada subconjunto está contado 6 veces, por lo que la cantidad de subconjuntos es realmente 60/6 = 10.

El argumento presentado para el ejemplo puede generalizarse de la siguiente forma. Si se tiene un conjunto con n elementos, de los cuales se van a escoger k de ellos, la elección (ordenada) puede hacerse de

n × (n-1) × (n-2) ×... × (n-k+1)

ya que en el primer paso se tienen n opciones, en el segundo se tienen n-1, en el tercero n-2, y así sucesivamente, terminando en el paso k que tendrá n-k+1 opciones.

Ahora, hay que dividir el producto anterior entre el número de selecciones «equivalentes». Pero si se tiene k objetos, hay k! formas de permutarlos, es decir, k! formas de listarlos en distinto orden. Recordemos que k! se lee k-factorial y es igual a

k! = 1×2×3×...× k

Concluimos que el número de subconjuntos con k elementos, escogidos de un conjunto con n elementos es

${n\choose k} = \frac{ n(n-1)(n-2)\cdots (n-k+1)}{1\cdot 2\cdot 3 \cdots (k-1)\cdot k}$ .

Multiplicando el numerador y el denominador de la fracción por 1×2×3×···×(n-k)

${n\choose k} = \frac{ 1\cdot 2\cdot 3\cdots (n-k)\cdot (n-k+1)\cdots (n-2)\cdot (n-1)\cdot n}{(1\cdot 2\cdot 3\cdots k)\Big(1\cdot 2 \cdot 3\cdots (n-k)\Big)}$

La expresión anterior puede escribirse de forma más compacta usando factoriales, expresión que es usada en ocasiones como la definición misma de coeficiente binomial (sobre todo en textos elementales que no explican el origen combinatorio de la misma):

El coeficiente binomial ${n \choose k}$ está dado por la fórmula ${n\choose k} = \frac{n!}{k! (n-k)!}$

Binomio de Newton.

El teorema de binomio y coeficientes binomiales

Finalmente, existe una tercera forma de definir los coeficientes binomiales, la cual da origen a su nombre. Sin embargo, esta definición obscurece el significado combinatorio de los números, pues la equivalencia con las definiciones anteriores no es evidente.

El coeficiente binomial ${n \choose k}$ es el coeficiente del término $x^ky^{n-k}\,$ obtenido al desarrollar $(x+y)^n\,$

Por ejemplo, si desarrollamos (x+y)³ obtenemos:

Para ilustrar la equivalencia entre esta definición y la anterior, consideremos un ejemplo con n=3,k=2. Podemos pensar que los factores de (x+y)³=(x+y)(x+y)(x+y) están coloreados de azul, rojo y verde respectivamente.

Por un lado, se sabe que (x+y)³ = x³+3x²y+3xy²+y³, por lo que el coeficiente de x²y es 3. Por otro lado, al desarrollar los factores, aparecerá un término x²y cada vez que se elija dos colores para x (dejando el color restante para y). El número de formas de escoger 2 colores entre 3 posibles opciones es precisamente C(3,2), como se estableció con anterioridad. La conclusión es que el coeficiente de x²y es necesariamente C(3,2).

Para el caso general, se puede imaginar que los n factores de (x+y)ⁿ han sido coloreados con diferentes colores, por lo que el coeficiente de x^ky^n-k será igual al número de formas de escoger k colores para asignarlos a la variable x (dejando los n-k colores restantes para y). El número de formas para escoger k colores entre n posibles opciones es C(n,k), con lo que se termina la prueba.

La afirmación de que esta definición es equivalente a las anteriores se conoce como teorema binomial o teorema de Newton, quien dio una prueba de una versión general del resultado. Sin embargo, la forma de calcular los coeficientes era conocida por diversas culturas con muchos siglos de anticipación.

En contextos más técnicos, suele usarse una forma diferente de expresar el teorema de Newton mediante el uso de sumatorios:

El desarrollo de $(x+y)^n\,$ es $(x+y)^n = \sum_{k=0}^n {n\choose k} x^{n-k}y^k$ .

Esta fórmula se generaliza para más de dos sumandos de la siguiente manera:

$(x_1 + \cdots + x_r)^n = \sum_{n_1 + \cdots + n_r = n}^n {n \choose n_1 \cdots n_r} x_1^{n_1} \cdots x_r^{n_r}$ ,

donde ${n \choose n_1 \cdots n_r}$ es un coeficiente multinomial que se define: ${n \choose n_1 \cdots n_r} \equiv {n! \over n_1! \cdots n_r!}$ . Los coeficientes multinomiales también tienen definición combinatoria. Puesto que

n

no es más que la suma de

n 1

n 2

,... y

n r

, también se emplean notaciones en las que

n

, no aparece, como $(n_1 \cdots n_r)$ . Otras notaciones son $(n; n_1 \cdots n_r)$ ó $(n_1 \cdots n_r)!$

Variaciones ordinarias y con repetición.

Variaciones sin repetición (ordinarias)

Variaciones sin repetición o variaciones ordinarias de m elementos tomados de n en n (n $\le$ m), son los distintos grupos de n elementos no repetidos que se pueden formar, escogidos de entre los m elementos posibles, de forma que en cada grupo haya algún elemento distinto, o tenga los mismos elementos que otro grupo, pero colocados en distinto orden. Cada uno de los posibles grupos es una variación. Se representa por

V m, n

o $V_m^n$ .

Como el primero de los elementos puede ser cualquiera de los m disponibles, el segundo cualquiera de los (m – 1) restantes, el tercero cualquiera de los (m – 2) que quedan y así sucesivamente, aplicando el principio de la multiplicación se obtiene:

$V_{m, n} = \overbrace{m \cdot (m-1) \cdot (m-2) \cdot \cdot \cdot (m-n+1)}^{n \text{ factores}}$

La fòrmula anterior es equivalente a: $V_{m, n} = \frac{m!}{(m-n)!}$

Ejemplo 1: En una carrera de natación participan 8 nadadores. ¿De cuántas formas posibles pueden ocuparse los tres primeros puestos?

Veamos las posibles opciones: Cualquiera de los nadadores participantes podría ser el primero, por lo que el número de opciones para escoger al primero es 8. El segundo puesto lo podría ocupar cualquiera de los nadadores restantes; por tanto, el número de opciones en este caso será 7. Por último, el tercer puesto lo podría ocupar cualquiera de los nadadores que no haya sido primero ni segundo; en este caso las opciones serán 6. Aplicando el principio de la multiplicación, habría 8 · 7 · 6 = 336 posibilidades distintas.

A cada grupo de 3 nadadores, de los 336 posibles, le llamaremos variación de 8 elementos tomados de 3 en 3.

Este resultado se puede verificar utilizando la fòrmula anterior, con m = 8 y n = 3.

Variaciones con repetición

Variaciones con repetición de m elementos tomados de n en n, son los distintos grupos de n elementos repetidos o no que se pueden formar, escogidos de entre los m elementos posibles. En este caso, dos grupos son distintos si tienen algún elemento diferente o si, siendo todos los elementos iguales, están colocados con distinto orden.

Se representa por

V R m, n

ó $VR_m^n$ .

$VR_{m, n} = \overbrace{m \cdot m \cdot \cdot \cdot m}^{n \text{ factores}} = m^n$

Ejemplo 2: ¿Cuántos números de tres cifras se pueden formar con los dígitos 1, 2, 3, 4 y 5?

La primera cifra podrá ser una cualquiera de las 5. La segunda cifra también podrá ser una cualquiera de las cinco ya que puede repetirse, y lo mismo ocurre para la tercera cifra. Aplicando el principio de multiplicación, hay 5 · 5 · 5 = 125 números de tres cifras.

Vemos que en este caso importa el orden, pues aún teniendo las mismas cifras, 123 y 231 son números diferentes. Además se han tomado 3 elementos de entre los 5 posibles, luego son variaciones, pero en este caso se puede elegir un elemento de los 5 más de una vez. A este tipo de variaciones se las llama variaciones con repetición.

Permutaciones ordinarias y con repeticiòn.

Permutaciones sin repetición (ordinarias)

Permutaciones ordinarias de n elementos son las distintas formas de ordenar dichos elementos. Cada forma de ordenarlos es una permutación.

El número de permutaciones de n elementos se representa por

P n

, y su valor es: $P n = n!$

Ejemplo 3: En la tómbola de un juego de lotería, quedan 5 bolas. ¿De cuántas formas podrán salir las cinco bolas?

La primera bola en salir podrá ser cualquiera de las 5. La segunda bola tendrá que ser una cualquiera de las 4 restantes, etc. Si aplicamos a este problema la definición de variación sin repetición que ya hemos visto, se obtiene que las formas posibles de salir las bolas son:

$V_{5, 5} = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$

En este caso, vemos que en todas las variaciones intervienen todos los elementos, y que la única diferencia entre una variación y otra está en el orden de dichos elementos. A las variaciones de n elementos tomados de n en n, se las llama permutaciones de n elementos.

Permutaciones con repetición

Dados n elementos, de los cuales el primer elemento se repite a veces, el segundo b veces, ..., el último r veces (a + b + ..... + r = n), llamaremos permutaciones con repetición de esos n elementos a los distintos grupos que se pueden formar, de forma que en cada grupo de n elementos, el primer elemento esté repetido a veces, el segundo b veces, ..., el último r veces. La única diferencia entre los grupos está en el orden de colocación de sus elementos distinguibles.

El número de permutaciones con repetición de n elementos se representa por $P_n^{\, a, b, ..., r}$

$P_n^{\, a, b, ..., r} = \frac{n!}{a! \cdot b! \cdot \cdot \cdot r!}$

Ejemplo 4: ¿Cuántas palabras de 5 letras, con sentido o sin él, se pueden formar con tres A y dos B?

Se trata en este caso de obtener las distintas ordenaciones posibles de AAABB. Si las A fuesen distinguibles entre sí, y lo mismo ocurriera con las B, se trataría de ordenar 5 elementos distintos y estaríamos ante el caso de las permutaciones sin repetición visto anteriormente.

Al ser indistinguibles, muchas de las permutaciones consideradas serán idénticas. Veamos, por ejemplo, el caso en que las 3 A aparezcan al principio de la palabra; la diferencia entre los casos en que las letras sean distinguibles e indistinguibles se recogen en la tabla siguiente (las hemos hecho distinguibles dotándolas de un subíndice).

Indistinguibles	Distinguibles
$A A A B B$	$A 1 A 2 A 3 B 1 B 2$
	$A 1 A 3 A 2 B 1 B 2$
	$A 2 A 1 A 3 B 1 B 2$
	$A 2 A 3 A 1 B 1 B 2$
	$A 3 A 2 A 1 B 1 B 2$
	$A 3 A 1 A 2 B 1 B 2$
	$A 1 A 2 A 3 B 2 B 1$
	$A 1 A 3 A 2 B 2 B 1$
	$A 2 A 1 A 3 B 2 B 1$
	$A 2 A 3 A 1 B 2 B 1$
	$A 3 A 2 A 1 B 2 B 1$
	$A 3 A 1 A 2 B 2 B 1$

Vemos que para el caso de las letras distinguibles, el número de palabras resulta de multiplicar las permutaciones de

A 1 A 2 A 3

por las de

B 1 B 2

, obteniéndose que el número de permutaciones es 3! · 2! = 12 , de las cuales sólo tenemos que considerar 1. Hemos considerado el caso en que las 3 A aparezcan al principio de la palabra; considerando todos los demás casos obtendremos que el número de palabras es

Número de palabras $= \frac{5!}{2! \cdot 3!} = \frac{5 \cdot 4 \cdot 3!}{2! \cdot 3!} = \frac{5 \cdot 4}{2} = 10$

Combinaciones ordinarias.

Combinaciones sin repetición (ordinarias)

Combinaciones ordinarias o combinaciones sin repetición de m elementos tomados de n en n (n $\le$ m) son los distintos grupos que se pueden formar con los m elementos disponibles, de modo que en cada grupo haya n elementos distintos. En este caso para que dos grupos sean distintos, han de tener algún elemento diferente; no basta con que tengan distinto orden de colocación. Se representa por

C m, n

o $C_m^n$ y su valor viene dado por:

$C{m, n} = \frac{V_{m, n}}{P_n} = \frac{m \cdot (m-1) \cdot (m-2) \cdot \cdot \cdot (m-n+1)}{n!} = \frac{m!}{n! (m-n)!}$

Ejemplo 5: A un concursante en un programa de televisión, le dejan elegir 3 regalos entre los siguientes: lavadora, frigorífico, lavavajillas, motocicleta, televisor y viaje. ¿Cuántas posibilidades de elección tiene el concursante?

Se podría pensar en un principio, que se trata de las variaciones de 6 elementos tomados de 3 en 3, pero hay que tener en cuenta que hay distintas variaciones que dan lugar a la misma elección del concursante.

Considérese el caso en que el concursante elige la motocicleta, el televisor y el viaje. Dentro del conjunto de todas las variaciones, dicha elección estaría repetida 3! = 6 veces, que son las distintas formas de ordenar dichos regalos. Por tanto, tendríamos que dividir el número de variaciones, entre el número de ordenaciones posibles de los regalos elegidos. En este caso:

$\frac{V_{6, 3}}{P_3} = \frac{6 \cdot 5 \cdot 4}{3!} = 20$

Procedimiento para resolver problemas de combinatoria

Figura no. 1.

El algoritmo representado en la figura 1 puede resultar de ayuda en la resolución de problemas de combinatoria. Partiremos del símbolo con la leyenda Inicio y seguiremos un camino que será función de las respuestas que demos a las preguntas de los rombos por los que pasemos. El camino concluye al llegar a uno de los rectángulos que nos indican el tipo de agrupamiento.

Ejemplo 6: Utilizaremos el procedimiento de la figura 1 para resolver el problema del ejemplo 4.

Partimos del inicio y descendemos a la primera pregunta: ¿Importa el orden? La respuesta en este caso es Sí, puesto que no es lo mismo AAABB que ABAAB.

Seguimos la flecha correspondiente a la respuesta Sí y llegamos a la segunda pregunta: ¿Hay que utilizar todos los elementos?La respuesta vuelve a ser Sí, pues así nos lo indicaban en el enunciado del ejemplo 4.

Seguimos de nuevo la flecha correspondiente a la respuesta Sí y llegamos a la tercera pregunta: ¿Hay elementos indistinguibles? La respuesta es de nuevo Sí, como ya se vió en el ejemplo 4.

Siguiendo por último la flecha correspondiente a la respuesta Sí, llegamos al rectángulo que nos indica que se trata de Permutaciones con repetición.

Ejemplo 7: Utilizaremos el procedimiento de la figura 1 con el problema del ejemplo 5.

Partimos del inicio y descendemos a la primera pregunta: ¿Importa el orden? La respuesta en este caso es No, puesto que cuando el concursante elige tres regalos, pongamos por caso que sean lavadora, frigorífico y lavavajillas, el conjunto de premios que se llevará el concursante será el mismo, idependientemente de la forma en que se ordenen dichos premios.

Siguiendo la flecha correspondiente a la respuesta No, llegamos al rectángulo que nos indica que se trata de Combinaciones.

Ejercicios resueltos.

1. ¿Cuántos números de 3 cifras distintas se pueden formar con 1,2,3,4,5,6?.

Es una variaciòn sin repeticiòn.

Vamos a formar subconjuntos de tres elementos distintos, en los que nos importa el orden, 123 es distinto de 321.
Se van a formar

2. En la final de unas olimpiadas corren la final de 100m 8 atletas. ¿De cuántas formas se puede configurar el podium?

Tambien es una variaciòn sin repeticiòn.

, luego hay 336 posibles podium

3. ¿Cuántos números de 8 cifras que empiecen por 6 se pueden formar con los 10 dìgitos del sistema decimal?

Se trata de una variaciòn con repeticiòn.

4. Ocho vecinas hacen fila en una panadería para comprar pan. ¿De cuántas formas distintas se pueden colocar en la fila?

El orden importa, los elementos son diferentes, se trata de una permutaciòn ordinaria.

P₈ = 8! = 8x7x6x5x4x3x2x1 = 40320.

5. En una urna hay 9 bolas, 3 blancas, 2 rojas y 4 negras. ¿De cuantas formas distintas se pueden extraer todas las bolas de la urna?

Se trata de una permutaciòn con repeticiòn.

Minaya - CCR

Datos personales

Unidad no. 5: Combinatoria.