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 cualesquiera 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 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 conocidas o desconocidas, respectivamente. Probar el teorema de la amistad es equivalente a probar que:
No importa cómo se hayan 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 representa tres personas mutuamente conocidas.
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)!}.\]
Ejercicio: En una carrera con 10 atletas, ¿de cuántas formas distintas podrían repartirse las medallas de oro, plata y bronce?
Ejercicio: Crea una función recursiva que nos permita calcular \(V_{n,m}\)
Variaciones con repetición
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<\(k\)) elementos de un conjunto de \(n\) elementos (0<\(n\)) al número \[VR_{n,k}=n^k,\] y se corresponde con las aplicaciones de un conjunto de \(m\) elementos de un conjunto de \(n\) elementos.
Ejercicio: ¿Cuántos números de 6 cifras se escriben usando solamente las cifras 1, 5 y 8 ?
Ejercicio: Crea una función recursiva que nos permita calcular \(VR_{n,k}\)
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.
Ejercicio: ¿Cuántos números de 4 cifras distintas pueden escribirse con los dígitos 2, 3, 5 y 8?
Ejercicio: Crea una función recursiva que nos permita calcular \(P_{n}\).
Permutaciones circulares
Otra forma de definir la permutación de un conjunto de \(n\) elementos es como una disposición ordenada de los \(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 circular 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, el número de permutaciones circulares que podemos hacer con un conjunto de \(n>0\) elementos es \[PC_n=P_{n-1}=(n-1)!.\]
Ejercicio: ¿De cuántas formas distintas se podían sentar a la mesa los caballeros de la Mesa Redonda?
Permutaciones con repetición
Por último, podemos considerar una permutación de los elementos de un conjunto donde se repite 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 permutaciones 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!}.\]
Ejercicio: ¿Cuántos números distintos de 6 cifras se pueden escribir usando tres unos, dos cincos y un ocho?
Ejercicio: Dado el grafo  se puede afirmar que |