Comenzamos la parte de Teoría combinatoria, recordando las definiciones de
- Conjuntos, cardinalidad, partes de un conjunto.
- Unión e intersección de conjuntos.
- Aplicaciones entre conjuntos finitos
- Dominio, rango e imagen.
- Inyectivas,
- sobreyectivas
- biyectivas
Estas aplicaciones nos dan resultados interesante:
Propiedad: Si \(A\) y \(B\) son conjuntos finitos con \(\vert A\vert > \vert B\vert\) entonces no existe ninguna aplicación inyectiva de \(A\) en \(B\).
Propiedad: Si \(A\) y \(B\) son conjuntos finitos con \(\vert A\vert < \vert B\vert \) entonces no existe ninguna aplicación sobreyectiva de \(A\) en \(B\).
Además hemos tratado los principios básicos de conteo:
- Principio de adición
- Principio de multiplicación
- Principio de distribución
El Principio de distribución es muy intuitivo:
Principio de distribución, del palomar o del cajón de la paloma de Dirichlet: Sean \(m\), \(n\) y \(p\) tres números naturales. Si se desean colocar \(np + m\) palomas en \(n\) cajas, alguna caja debe contener al menos \(p + 1\) palomas.
Una ilustración de este resultado es el teorema de la amistad: Supóngase que en una fiesta hay 6 personas. Considérese a dos cualquiera de ellos. Puede ser que se reúnan por primera vez, en cuyo caso son mutuamente extraños, o puede ser que se hayan conocido antes, en cuyo caso se les llamará mutuamente conocidos. Entonces,
En cualquier grupo de seis personas, existen tres personas que son mutuamente conocidas o mutuamente desconocidas.
Su demostración se puede a hacer mediante un grafo. Supóngase un grafo de 6 vértices y cada par de vértices está unido por una arista, es decir, \(K_6\). Sean las 6 personas de la fiesta representadas por los 6 vértices. \(K_6\) es un grafo completo con 15 aristas, e imaginemos las aristas son coloreadas con los colores rojo o azul dependiendo de si las dos personas representadas por los vértices incidentes a la arista son mutuamente conocidos o desconocidos, respectivamente. Probar el teorema de la amistad es equivalente a probar que:
No importa cómo se ha coloreado las aristas de \(K_{6}\) con los colores rojo o azul, no se puede evitar que exista un triángulo rojo, es decir, un triángulo que tenga sus tres lados de color rojo, lo que representa tres personas mutuamente extrañas o un triángulo azul, que representan tres personas mutuamente conocidos.
Lecturas recomendadas:
- ÁLGEBRA BÁSICA, Conjuntos y Estructuras Algebraicas, Juan De Burgos Román, Ingebook.
- Reytor Rodríguez, R. (2008). Lo esencial en combinatoria. Editorial Universitaria. https://elibro.net/es/lc/bucam/titulos/71362(https://elibro.net/es/ereader/bucam/71362)
Variaciones
Llamaremos variaciones de \(n\) elementos tomados de \(m\) en \(m\), al número de aplicaciones inyectivas que podemos hacer del conjunto \(A\), de cardinal \(m\), en el conjunto \(B\), de cardinal \(n\), \(m\leq n\). Para calcular las variaciones utilizaremos:
\[V_{n,m}=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}.\]
Imaginemos que deseamos contar el total de aplicaciones posibles, entonces se plantean las variaciones con repetición. Llamaremos variaciones con repetición de \(m\) (0<\(m\)) elementos de un conjunto de \(n\) elementos (0<\(n\)) al número \[VR_{n,m}=n^m,\] y se corresponde con las aplicaciones de un conjunto de \(m\) elementos de un conjunto de \(n\) elementos.
Permutaciones
Llamaremos permutaciones de un conjunto de \(n\) elementos (0<\(n\)) al número \[P_n=n!,\] y se corresponde con las aplicaciones biyectivas de un conjunto de \(n\) elementos sobre un subconjunto de \(\mathbb{N}\) del mismo cardinal. Otra forma de definir la permutación de un conjunto de \(n\) elementos es como una disposición ordenada de los elementos \(n\) elementos. Esa disposición la podemos representar como una \(n\)-tupla. Si una \(n\)-tupla circular la entendemos como la \(n\)-tupla donde hemos unido el inicio con el fin, podemos considerar una permutación circualr como una \(n\)-tupla circular, donde dos permutaciones circulares son iguales si cada elemento tiene a derecha e izquierda los mismos compañeros. De esta forma, En número de permutaciones circulares que podemos hacer con un conjunto de \(n>0\) elementos es \[PC_n=P_{n-1}=(n-1)!.\]
Por último podemos considerar una permutación de los elementos de un conjunto donde se repiten alguno de ellos. Una permutación con repetición de un conjunto \(A=\{x_i;i=1,…,n\}\), quedará identificada por una disposición de la forma
\[(x_1,\overset{\underbrace{r_1}}{\ldots},x_1,x_2,\overset{\underbrace{r_2}}{\ldots} ,x_2, \ldots, x_n, \overset{\underbrace{r_n}}{\ldots},x_n)\]
donde \(r_1+r_2+\ldots+r_n\in\mathbb{N}\) determina el número de elementos totales. En ese caso el número total de permutación con repetición del conjunto \(A\), donde cada elemento \(x_i\in A\) sae repite \(r_i\mathbb{N}\) veces es
\[PR_{r_1+r_2+\ldots+r_n}^{r_1,r_2,\ldots,r_n}=\frac{(r_1+r_2+\ldots+r_n)!}{r_1!\,r_2!\,\ldots\,r_n!}.\]
Combinaciones
Las combinaciones podemos definir como las variaciones donde no importa el orden que elijamos los elementos. De este modo ese número será \[C_{n,m}=\frac{V_{n,m}}{P_m}=\frac{n!}{m!\,(n-m)!}\]
Otra variación que podemos hacer es un número determinado de objetos elegidos entre varios conjuntos de objetos. Por ejemplo, tenemos limones, naranjas y peras suficientes para repartir un pieza a cada uno de nuestros once alumnos. ¿De cuantas formas podríamos hacerlo? Esta manera de repartir, en la que como se aprecia podemos repetir alguno de los objetos, es lo que denominamos combinaciones con repetición. Y el cómputo total será \[CR_{n,m}=C_{n+m-1,m}\] Observar que en este tipo de recuento es común que \(n<m\).
Veamos una aplicación prácticas donde utilizamos las combinaciones:
Sean \(k,n\in\mathbb{N}\). El número de soluciones enteras no negativas(es decir, \(x_i\geq 0 \)) de la ecuación \[x_1+x_2+\ldots+x_n=k\] es \[CR_{n,k}=C_{n+k-1,k}\]
Ejercicio: Dado el grafo se puede afirmar que |