Cálculo combinatorio
Definiciones y Notación
Empezaremos introduciendo los nombres y notación de los conceptos que estaremos usando en esta sección.
Recordamos que nuestra definición informal de número natural es que todo natural es la colección de naturales anteriores a él. De esta forma tenemos que \(0=\emptyset\), \(1=\{0\}\), \(2=\{0,1\}\) y en general
\[n=\{0,\dots,n-1\}.\]Además, cuando usemos conjuntos \(A\), \(B\), … estaremos suponiendo que estos conjuntos son finitos.
Ordenaciones con repetición
Dado un conjunto con \(n\) elementos primero consideramos cómo tomar \(m\) elementos de ese conjunto de tal forma que es posible repetir elementos. Otra forma de decirlo es que vamos a hacer una lista de longitud \(m\) de elementos de un conjunto de tamaño \(n\), donde es posible repetir elementos del conjunto en la lista.
Por ejemplo, si tomamos \(A=\{a,b,c\}\), que tiene tres elementos, y hacemos listas de longitud dos, entonces algunos ejemplos de lista son:
\[\begin{array}{ccccc} 1. & a && 1. & c\\ 2. & b && 2. & c \end{array}\]Estas listas de elementos de \(A\) se pueden pensar como funciones de la forma \(f\colon 2\to A\). Para la primera lista del ejemplo de arriba definimos \(f\) como \(f(0)=a\) y \(f(1)=b\). Notemos que estas listas generan funciones sin ninguna propiedad adicional. Por ejemplo, en la función \(f\) de antes tenemos que no es suprayectiva. Si hacemos una función \(g:\colon 2\to A\) para capturar la segunda lista de arriba, entonces \(g\) no sería inyectiva.
Por lo anterior, las ordenaciones con repetición son funciones arbitrarias de algún natural hacia un conjunto (finito). Introducimos la siguiente notación:
\[B^A = \{f\colon A\to B\mid f\text{ es función}\}.\]Definición
\(OR_{m}^{n}\) es el número de formas de elegir \(m\) elementos de un conjunto de tamaño \(n\), donde se admiten repeticiones. Esto es,
\[OR_{m}^{n} = |n^m|.\]
Ordenaciones
Las ordenaciones (sin repetición) son bastante similares a las ordenaciones con repetición. La diferencia, como el nombre lo índica, es que ahora no se admiten repeticiones. En los ejemplos de listas de ordenaciones con repetición tenemos que el primer ejemplo, la columna de la izquierda, sí es un ejemplo de ordenación, mientras que el segundo, la columna de la derecha, no lo es.
No es difícil notar que el concepto matemático que captura la idea de hacer listas donde no se admiten repeticiones es el de función inyectiva.
Definición
\(O_{m}^{n}\) es el número de formas de elegir \(m\) elementos de un conjunto de tamaño \(n\), donde no se admiten repeticiones. Esto es,
\[O_{m}^{n} = |\{f\colon m\to n\mid f\text{ es inyectiva}\}|.\]
Permutaciones
Como vimos en la sección de cardinalidad toda función \(f\colon n\to n\) es inyectiva si y sólo si es suprayectiva. Así, si tenemos una función \(f\colon n\to n\) inyectiva, entonces \(f\) es biyectiva.
Podemos hacer un caso particular de ordenación, en el que elegimos \(n\) elementos de un conjunto de tamaño \(n\), sin admitir repeticiones. Por la observación anterior, esto es lo mismo que tomar funciones biyectivas de \(n\) en \(n\).
Definición
\(P_{n}\) es el número de formas de elegir \(n\) elementos de un conjunto de tamaño \(n\), donde no se admiten repeticiones. Esto es,
\[P_{n} = O_{n}^{n} = |\{f\colon m\to n\mid f\text{ es biyectiva}\}|.\]
Combinaciones
Finalmente, podemos pensar en obtener subconjuntos de tamaño \(m\) de un conjunto de tamaño \(n\). Esta es una idea similar a la de las ordenaciones, ya que cada función inyectiva \(f\colon m\to n\) genera, mediante la imagen, un subconjunto de tamaño \(m\) del conjunto \(n\). Sin embargo, hay muchas funciones inyectivas que generan al mismo subconjunto. Por ejemplo, si \(f,g\colon 2\to 3\) están definidas como \(f(0)=1\), \(f(1)=2\), \(g(0)=2\) y \(g(1)=1\), entonces tienen la misma imagen, por lo que generan al mismo subconjunto de \(3\). Más adelante veremos que implican las observaciones que acabamos de hacer.
Definición
Las combinaciones de \(m\) en \(n\) es el conjunto de subconjuntos de \(n\) de tamaño \(m\). Además,
\[C_{m}^{n} = |\{S\subseteq n\mid S\text{ tiene tamaño }m\}|.\]
¿Cuántos hay?
Ahora que ya tenemos todos los conceptos que nos interesan, lo siguiente es encontrar fórmulas que nos permitan calcular cuántos elementos tiene cada uno de los anteriores.
En general, el cálculo se puede hacer con conjuntos finitos \(A\) y \(B\). Aquí veremos primero cómo se hace con números naturales y luego veremos cómo hacer cálculos con conjuntos finitos arbitrarios.
Ordenaciones con repetición
Teorema
\(OR_{m}^{n} = n^m\).
La demostración del teorema es por inducción sobre \(m\). Para \(m=0\) tenemos, por un lado, que \(n^0=1\) y, por otro, que la única función de \(0\to n\) es la función vacía, por lo que \(OR_{0}^{n}=1\).
Supongamos que el teorema es cierto para \(m=k\). Entonces, para \(m=k+1\) tenemos que toda función \(f\colon k+1\to n\) es la extensión de una función \(g\colon k\to n\). De esta manera es suficiente contar cuántas funciones de la forma \(g\colon k\to n\) hay y cuántas extensiones distintas tiene cada una de ellas.
Por hipótesis de inducción, hay \(n^k\) funciones de la forma \(g\colon k\to n\). Así, sólo falta contar cuántas extensiones tiene cada una. Sea \(g\colon k\to n\) una función. Para obtener una extensión de \(g\) de la forma \(f\colon k+1\to n\), tenemos que elegir un elemento de \(n\) para que sea la imagen de \(k+1\). Como hay \(n\) elementos en \(n\), entonces hay \(n\) formas de extender \(g\) a una función \(f\colon k+1\to n\). Por lo tanto,
\[OR_{k+1}^{n} = n^k\cdot n = n^{k+1}.\]Ordenaciones
Teorema
\(O_{m}^{n} = \frac{n!}{(n-m)!}\).
De nuevo la demostración es por inducción. Para \(m=0\) tenemos que la única función inyectiva de \(0\to n\) es la función vacía, por lo que \(O_{0}^{n}=1\). Además, \(n!/(n-0)! = n!/n! =1\).
Supongamos que el teorema es cierto para \(m=k\). Además, supongamos que \(n>k\) para que el dominio sea chico respecto al codominio y sí haya funciones inyectivas. Ahora, notemos que toda función inyectiva \(g\colon k\to n\) sólo ha usado \(k\) elementos de \(n\). Así, hay \(n-k\) elementos de \(n\) que no han sido usados por \(g\). Por lo tanto, hay \(n-k\) maneras de extender \(g\) a una función inyectiva \(f\colon k+1\to n\). Por lo tanto,
\[O_{k+1}^{n} = O_{k+1}^{n} \cdot (n-k) = \frac{n!}{(n-k)!}\cdot (n-k) = \frac{n!}{(n-(k+1))!}.\]Permutaciones
Como vimos antes, las permutaciones son un caso particular de ordenaciones. Por lo tanto, demostrar que \(P_{n} = n!\) es inmediato,
\[P_{n} = O_{n}^{n} = \frac{n!}{(n-n)!} = n!.\]Combinaciones
Teorema
\(C_{m}^{n} = \frac{n!}{m!(n-m)!}\).
Este resultado se puede deducir de los anteriores. Para ello, notemos que toda función inyectiva \(f\colon m\to n\) genera un subconjunto de tamaño \(m\) de \(n\), dado por la imagen de \(f\). Sin embargo, hay muchas funciones inyectivas que generan el mismo subconjunto, como vimos arriba. Así, para contar cuántos subconjuntos de tamaño \(m\) hay en \(n\), es suficiente contar cuántas funciones inyectivas \(m\to n\) hay y cuántas funciones inyectivas generan el mismo subconjunto. Ya sabemos que hay \(O_{m}^{n}\) funciones inyectivas. Dos funciones inyectivas \(g,h\colon m\to n\) generan el mismo subconjunto si y sólo si el conjunto \(\{g(0),\dots,g(m-1)\}\) es una permutación del conjunto \(\{h(0),\dots,h(m-1)\}\). Por lo tanto, hay \(m!\) funciones inyectivas que generan el mismo subconjunto. Por lo tanto,
\[C_{m}^{n} = O_{m}^{n}/m! = \frac{n!}{m!(n-m)!}.\]Con conjuntos finitos
Todos los cálculos que hemos hecho han usado conjuntos finitos muy particulares, números naturales. Sin embargo, la naturaleza de los conjuntos nos permite generalizar a conjuntos finitos arbitrarios. Para ello, basta con notar que si \(A\) y \(B\) son conjuntos finitos, entonces existen \(n,m\in\mathbb{N}\) y funciones biyectivas \(f\colon n\to A\) y \(g\colon m\to B\). Por ejemplo, para calcular \(|A^B|\) definimos una biyección
\[h\colon A^B\to n^m\]como sigue. Dada una función \(k\colon B\to A\), definimos \(h(k) = f^{-1}\circ k\circ g\), es decir, \(h(k)\colon m\to n\) es la siguiente composición de funciones:
\[\begin{CD} m @>g>> B @>k>> A @>f^{-1}>> n. \end{CD}\]Es fácil ver que la inversa de esta función es \(h'\colon n^m\to A^B\) que a cada \(k'\colon m\to n\) le asigna la función \(f\circ k'\circ g^{-1}\).
| Por lo tanto, podemos concluir que $$ | A^B | = | n^m | $$ y con esto tenemos | ||
| $$ | A^B | = n^m = | A | ^{ | B | }$$. |
De la misma manera, componiendo con biyecciones y sus inversas, se pueden calcular las ordenaciones con repetición, permutaciones y combinaciones con conjuntos finitos arbitrarios.