Teoría de la Combinatoria

	Aprender y divertirse con la Hoja de Cálculo Página personal de Antonio Roldán Martínez	Inicio Sin decimales Aritmética Divisibilidad Combinatoria Congruencias Juegos Diccionario general Estadística
	Combinatoria Teoría Propuestas Diccionario Herramientas Páginas de interés
Estás en Inicio > Sin decimales > Combinatoria > Teoría

	Combinatoria	Breve esquema teórico

El producto cartesiano de dos conjuntos A y B es otro conjunto cuyos elementos son todos los pares posibles formados por un elemento de A y otro de B en ese orden. Se representa como A´B

Una correspondencia entre dos conjuntos es cualquier subconjunto de su producto cartesiano. En la práctica consiste en asignar una pareja o varias a todos o algunos elementos del conjunto.

Una aplicación es una correspondencia en la que cada elemento del primer conjunto le corresponde un elemento del segundo conjunto y solo uno

Según esta definición podremos asignar un nombre (por ejemplo G) a la aplicación y usar la notación G(A)=1, en la que expresamos que al elemento A del primer conjunto le asignamos el elemento 1 del segundo. En este caso, a A la llamaremos origen y al 1, imagen. Así, en el diagrama de la figura, se puede afirmar que G(A)=1 G(B)=3 G(C)=2 G(D)=2.

Como se ve, la definición permite que dos orígenes compartan la misma imagen. Al conjunto de todas las imágenes le llamaremos Recorrido, Rango o Conjunto Imagen de la aplicación G. Al conjunto de todos los orígenes, que según la definición es todo el primer conjunto, le llamaremos Dominio de la aplicación.

Llamaremos factorial de un número natural n (o el cero) a otro número natural n! definido por

a) Si n=0 su factorial se define como 1: 0! = 1
b) Si n=1 definiremos su factorial como 1: 1! = 1
c) Si n>1 su factorial viene dado por la expresión n! = 2.3.4.....(n-1).n

Igualmente, llamaremos semifactorial de un número natural n al producto n(n-2)(n-4)(n-6).... terminando el producto en 2 o 1, según la paridad de n y lo representaremos así: n!!

Llamaremos arreglo en un conjunto finito a cualquier sucesión también finita formada por elementos de ese conjunto. Al ser el arreglo una sucesión, intervendrá en él el orden, y se podrán repetir elementos. Estas dos características distinguen los arreglos de los subconjuntos.

En los textos de Combinatoria encontrarás varias formas de nombrar estas sucesiones:

Se puede caracterizar cada arreglo como una aplicación de un conjunto finito de números naturales del tipo {1, 2, 3, 4, ... } sobre elementos del conjunto.

Este concepto permite desarrollar las definiciones clásicas de variaciones y permutaciones.

Llamaremos variaciones con repetición de m elementos tomados de n en n, (simbolizadas por VRm,n) a todos los arreglos de n elementos que se pueden formar en un conjunto de m elementos, si se permite la repetición de los mismos.

El arreglo de la imagen anterior es un ejemplo de variación con repetición de 5 elementos tomados de 5 en 5.

El número total de variaciones de este tipo viene dado por la fórmula VRm,n = mⁿ

Otro ejemplo: el número total de posibles quinielas de 14 partidos será 3¹⁴ = 4.782.969

Llamaremos variaciones sin repetición de m elementos tomados de n en n, (simbolizadas por Vm,n) a todos los arreglos de n elementos que se pueden formar en un conjunto de m elementos, si no se permite la repetición de los mismos.

Se pueden considerar otras interpretaciones de las variaciones:
- Formas de elegir ordenadamente n elementos distintos de un conjunto de m elementos
- Órdenes totales posibles definidos en todos los subconjuntos de orden n.

El número total de variaciones de este tipo viene dado por la fórmula Vm,n = m(m-1)(m-2)...(m-n+1) = m! /(m-n)!

Según la notación explicada más arriba, esta expresión también se puede escribir como m⁽ⁿ

Dos variaciones se pueden distinguir entre sí o por los elementos que contienen o por su orden. Esta es la caracterización clásica de las variaciones.

Si en una carrera intervienen 9 atletas, la composición del podio puede presentar V9,3=9*8*7 = 504 resultados distintos.

Se llaman permutaciones ordinarias o sin repetición ( Pn) a las variaciones sin repetición en las que m=n, es decir, que en cada arreglo entran todos los elementos del conjunto.

Dos permutaciones sobre un conjunto se distinguen sólo por el orden de los elementos. Por ello se pueden identificar con los distintos órdenes que se pueden establecer en los elementos de un conjunto.

También se llaman permutaciones a las aplicaciones biyectivas de un conjunto en sí mismo. Es el concepto tradicional de sustitución en un conjunto. Más adelante trataremos este concepto de permutación como aplicación biyectiva interna en un conjunto.

El número de permutaciones formadas con un conjunto de n elementos coincide con su factorial: Pn = n!

Un caso especial de permutaciones es el de las circulares, que son las distintas formas de ordenar unos objetos en círculo (por ejemplo, invitados a una cena). Su número es (n-1)!

En los distintos órdenes posibles quizás se desee admitir la repetición de algunos elementos un número determinado de veces. Por ejemplo, en la palabra CATAPULTA, si quisiéramos ordenar sus letras, deberíamos admitir que la A se repitiera tres veces y la T dos. Llamaremos permutaciones con repetición a estas ordenaciones.

Para calcular el número de permutaciones de este tipo bastará dividir el factorial del número total de símbolos, contando sus repeticiones, entre el número de veces que se repite cada uno.

En el ejemplo, el número de permutaciones de la palabra CATAPULTA sería de 11!/(3!*2!) =3.326.400

Llamaremos combinaciones de m elementos tomados de n en n, (simbolizadas por Cm,n) a todos los subconjuntos de n elementos que se pueden formar en un conjunto de m elementos.

Por su propia definición se deduce que el orden no interviene para distinguir unas combinaciones de otras.

Las combinaciones con repetición CRm,n de m elementos tomados de n en n admiten varias definiciones. Se usan todas porque es un concepto más difícil que los anteriores y para abrir aplicaciones diversas de este tipo de arreglos.

(1) Son los distintos arreglos que se pueden formar en un conjunto de m elementos de forma que en cada uno se elijan n elementos que pueden ser repetidos y se diferencien unos arreglos de otros sólo en los elementos que los forman y no por el orden elegido.
(2) Son aplicaciones del conjunto (1,2,3...n) en el conjunto dado que sean crecientes en sentido amplio.
(3) Las CRm,n equivalen a un reparto de m objetos en n cajas.
(4) Las CRm,n equivalen al conjunto de todas las soluciones enteras positivas de la ecuación x₁ + x₂ + ... + x_n = m

Casi todos los problemas combinatorios elementales se pueden resolver con las definiciones y fórmulas anteriores, el concepto de Producto Cartesiano y los principios fundamentales que se explican a continuación.

Representaremos por Card(A) el cardinal de un conjunto A, es decir, su número de elementos si es finito.

Es decir, que para contar los elementos de la unión de varios conjuntos disjuntos, deberemos sumar.

Esta fórmula se generaliza fácilmente a varios conjuntos, con la particularidad de que las intersecciones aparecerán con signos más o menos según el número de conjuntos que abarquen.

Podemos traducir este principio a la idea de que al combinar mediante pares, ternas, etc. varios conjuntos, el número total de elementos resultantes equivale al producto de los cardinales de los conjuntos que se combinaron.

Como consecuencia, el número de aplicaciones que se pueden construir entre un conjunto A de cardinal n y otro B de cardinal m viene dado por

^{Este principio también se aplica cuando un arreglo se
construye en varias etapas y las posibilidades de cada una son independientes de
los resultados anteriores, por ejemplo en una tirada de tres dados.}

^{También es útil al combinar dos conjuntos de arreglos
distintos, como el las matrículas de los coches D - 1234 - AZ, en las que
se combinan tres variaciones distintas.}

Este principio se conoce también como Principio de las cajas, del palomar o de Dirichlet

(a) Si repartimos m objetos en n cajas, y m>n, entonces, al menos una caja deberá contener 2 objetos o más.

(b) Si se reparten np+m objetos en n cajas, entonces alguna caja deberá contener al menos p+1 objetos.

Ambos principios, que resuelven muchas cuestiones combinatorias, los damos sin demostración.

Según ellos, en una clase con 35 alumnos, habrá al menos dos que compartan el mismo número de día del mes como cumpleaños. "Ambos nacieron un 12, pero de distinto mes". Si en un centro de enseñanza hay más de 366 alumnos, habrá al menos dos que compartan la misma fecha de cumpleaños. Lo que no sabemos es qué fecha será esa.

y a su generalización para más de dos conjuntos. Por ejemplo, para tres sería

Card(AÈBÈC) =Card(A) + Card(B) + Card(C) - Card(AÇB) - Card(AÇC) - Card(BÇC) + Card(AÇBÇC)

En el caso de varios conjuntos aparecerían signos - en las intersecciones de un número par de conjuntos y signo + en las de número impar:

Card(ÈS_i) = ∑Card(S_i) - ∑Card(S_iÇS_j) + ∑Card(S_iÇS_jÇS_k) + ... + (-1)ⁿ∑Card(S_iÇ...ÇS_n)

Equivalen al número de combinaciones sin repetición de n elementos tomados de r en r.

Su conjunto ordenado en forma de triángulo toma el nombre de Triángulo de Pascal, de Tartaglia o Aritmético

Es clásica la fórmula del Binomio de Newton, que expresa la potencia de un binomio en términos de números combinatorios. Su desarrollo es

Mediante la sustitución de a y b por valores adecuados (1, -1,...) se pueden demostrar bastantes propiedades, como algunas de las contenidas en párrafos anteriores.

Como una permutación equivale a una aplicación biyectiva de un conjunto en sí mismo, al igual que estas, formará un grupo ( el grupo simétrico del conjunto ) para la operación de componer aplicaciones. Es trivial considerar que se cumple la propiedad asociativa, que existe una permutación identidad (en la que no se altera el orden existente) y una permutación inversa.

Este grupo no posee la propiedad conmutativa. En general S*S' produce un resultado distinto a S'*S, pero sí existirán sustituciones permutables entre sí, como por ejemplo una sustitución y su inversa.

Para destacar el carácter de aplicación biyectivas, las permutaciones las podemos escribir así:

(1 2 3 4 5 6 7 8)
(2 1 8 4 6 7 5 3) en las que el conjunto de arriba sería el origen y el de abajo la imagen. Al conjunto de arriba le podemos llamar numerador y al de abajo denominador. Si aplicamos una misma permutación a ambos no se altera la correspondencia entre orígenes e imágenes, por lo que podemos escribir el numerador siempre en el mismo orden, al que llamaremos principal. Así, con números, podemos usar el orden creciente1, 2, 3, 4...

A este grupo le llamaremos Grupo de Sustituciones S_ndel conjunto. Su número de elementos será n!

Si en una permutación vamos recorriendo los transformados de cada elemento de forma consecutiva, pudiera ser que uno de ellos coincidiera con el primero, con lo que se habría cerrado un ciclo o permutación circular. Así, la permutación

(1 2 3 4 5 6 7 8)
(2 1 8 4 6 7 5 3) contiene un ciclo que recorre 5 - 6 - 7 - 5, otro formado por el 3 y el 8, otro por el 1 y el 2 y un último que forma 4 consigo mismo.

Toda permutación se puede descomponer en ciclos. Si prescindimos de escribir el conjunto origen, podríamos expresar este hecho de la siguiente forma:

Como cada ciclo opera sobre elementos distintos, dos ciclos de una misma descomposición serán siempre permutables.

La potenciación de sustituciones se define como su composición reiterada: Sⁿ = S*S*S...*S (n veces). Es también trivial demostrar que el conjunto de potencias de una sustitución S forma un subgrupo, llamado cíclico o monógeno engendrado por S

Si recordamos la definición de orden de un elemento a en un grupo G, como el menor exponente natural (en notación multiplicativa) para el que aⁿ = I (identidad). Esto también es válido para sustituciones, y los grupos cíclicos engendrados por S, que tendrá cada uno un orden, que coincide con su número de elementos. Según la teoría de grupos, todos los órdenes serán divisores de n!.

Si una permutación se descompone en ciclos, su orden coincidirá con el M.C.M de los órdenes de dichos ciclos.

Un caso particular de ciclo es el compuesto sólo por dos elementos. En este caso lo llamaremos transposición, y consiste en la permutación entre esos dos elementos, por ejemplo (3 8)

Todo ciclo se descompone en transposiciones, pero no de forma única. Así, tenemos que (1 2 3 ) = (1 2)(1 3) = (1 3)(2 3).

Lo que sí se conserva la paridad: todas las descomposiciones en ciclos de una misma permutación comparten el tener un número par o bien impar de transposiciones. Llamaremos permutación par a aquella que se puede descomponer en un número par de transposiciones, e igualmente definiremos la permutación impar.

Es fácil ver que transponiendo dos elementos de una permutación se añade o se quita una transposición, con lo que todas las permutaciones pares se pueden convertir de esta forma en pares, y viceversa. Por tanto.

En todo conjunto de n elementos se pueden definir n!/2 permutaciones pares y n!/2 impares

También es fácil demostrar que las pares forman un semigrupo, llamado grupo alternado del conjunto sobre el que actúan. No así las impares, que al componerse entre sí producen una par.

Se puede definir la signatura de una permutación como el número +1 si es par y el -1 si es impar.

Dado el grupo de permutaciones S_n sobre un conjunto de n elementos, se podría plantear la cuestión de cuántas permutaciones se pueden descomponer exactamente en k ciclos. A este número S1(n,k) así definido lo llamaremos Número de Stirling de primera clase.

Por ejemplo, el número S1(4,3) = 6 significa que hay seis permutaciones de 4 elementos (por ejemplo. en el conjunto 1234) que se pueden descomponer en 3 ciclos. Serían estas: (1)(2)(34), (1)(3)(24), (1)(4)(23), (2)(3)(14), (2)(4)(13) y (3)(4)(12).

Se puede definir S1(n,0) con n>0 como 0, y aceptaremos que S1(0,0)=1 y que S1(0,n)=0.

Es claro que se cumple que S1(n,n)=1 pues sólo obtendríamos la permutación identidad, y es fácil demostrar que S1(n,1)=(n-1)!

La propiedad fundamental de estos números, y que permite generarlos en una tabla, es la siguiente:

Dentro del grupo de permutaciones son interesantes aquellas llamadas desarreglos, en las que la imagen de cada elemento es distinta del mismo. Por ejemplo, S=3412, es un desarreglo, pues S(1)=2, S(2)=4, S(3)=1, S(4)=2. Un ejemplo clásico es el de las cartas a las que se asignan sobres con la dirección ya escrita, y si se emparejan al azar, los desarreglos se producirían cuando todas las cartas se metieran en un sobre inadecuado (Problema de los sobres o de Montmort)

Si llamamos S a un desarreglo, se deberá cumplir que S(i) sea distinta de i para todo i del conjunto.

Para conseguir su fórmula es mejor contar las permutaciones contrarias F, es decir, en la que existe algún elemento fijo S(i)=i. Basta considerar que las que dejan fijo un sólo elemento son en total (n-1)¡, las que dejan 2, (n-2)¡, etc... pero cada una deberá ser multiplicada por las formas de elegir un elemento, o dos, o tres, etc., es decir las combinaciones de los elementos que son fijos. Por el principio de inclusión-exclusión quedará:

El número de desarreglos D equivaldrá a la diferencia de F con el número total de permutaciones, luego quedará:

El resultado de esta fórmula recibe también el nombre de subfactorial, y se representa por !n.

El paréntesis es el desarrollo del número 1/e truncado por los términos que dan cocientes enteros con n! Por ello podemos interpretar esta fórmula como "el número entero más cercano a n!/e"

Una propiedad importante de D_n , derivada de la fórmula anterior, es que tiende al límite (1/e)n! = 0,36787944n! cuando n tiende a infinito. Por tanto, para valores grandes de n podemos suponer que un 37% de las permutaciones de un conjunto de n elementos son desarreglos.

D_n también se calcula mediante recurrencias. Se puede demostrar que D_n = nD_n-1+(-1)ⁿ, lo que unido a que D₁=0 y D₂=1 nos da la lista de los primeros subfactoriales: 0, 1, 2, 9, 44, 265, 1854...

El numero 148,349 es el único numero en que es igual a la suma de los subfactoriales de sus digitos:

Una partición de un conjunto C es una familia Xi de subconjuntos, disjuntos dos a dos, cuya unión coincide con el conjunto total. Es decir:

Es interesante preguntarse cuántas particiones distintas de k conjuntos se pueden definir en un conjunto de n elementos. El resultado se denomina como número de Stirling de segunda clase y lo representaremos por S2(n,k). Así, el número S2(5,4) representará el número de particiones distintas en cuatro conjuntos disjuntos que se pueden definir en un conjunto de 5 elementos. Por ejemplo, en el conjunto {1,2,3,4,5} se pueden definir estas particiones de 4: {1}{2}{3}{45}, {1}{2}{4}{35}, {1}{2}{5}{34}, {1}{3}{4}{25}, {1}{3}{5}{24}, {1}{4}{5}{23}, {2}{3}{4}{15}, {2}{3}{5}{14}, {2}{4}{5}{13}, {3}{4}{5}{12}. En total 10, como se puede comprobar en la tabla de abajo.

Es claro que S2(n,0)=0 y que S2(n,1)=S2(n,n)=1 porque sólo hay una forma de partir un conjunto de n elementos en conjuntos de n elementos (él mismo) y también una sola forma de partirlo en n subconjuntos (los de un solo elemento).

Puedes comprobar esta propiedad en la siguiente tabla de números de Stirling de segunda clase:

El número total de particiones que admite un conjunto, independientemente de su estructura, se llama número de Bell del conjunto y se representa por B(n). Es evidente que se pueden deducir de los anteriores sumando toda una fila. Los primeros números de Bell son, por tanto:

	0	1	2	3	4	5	6	7	8
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1
8	0	5040	13068	13132	6769	1960	322	28	1

	0	1	2	3	4	5	6	7	8	9
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1
8	0	1	127	966	1701	1050	266	28	1
9	0	1	255	3025	7770	6951	2646	462	36	1

0	1	2	3	4	5	6	7	8	9	10
1	1	2	5	15	52	203	877	4140	21147	115975


	que aplicándola reiteradamente nos lleva a esta otra