Diario de clases

Terminamos los contenidos de la Teoría Combinatoria con la inclusión del estudios de las particiones.

Una partición del conjunto A es una familia P de subconjuntos no vacíos de A, disjuntos dos a dos, cuya unión es A. Es decir, $P= \{A_i: i\in I\}$, donde se cumple:

• Para cada $i\in I, A_i\subseteq A y A_i\neq\varnothing $
• Para cada par $i\neq j$, $A_i\cap A_j = \varnothing $
• $\cup_{i\in I} A_i = A$

El número de particiones posibles para un conjunto finito sólo depende de su cardinal $n$, y se llama el número de Bell, $B_n$. Los primeros números de Bell son B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, B₆ = 203, …

Los números de Bell cumplen una relación de recurrencia muy interesante:
$$B_n=\sum_{k=0}^{n-1}B_k\binom{n-1}{k}$$

Un caso particular de contar particiones son los números de Stirling de segunda especie:
$$S(n,k)=\frac{1}{k!}\sum_{i=0}^k(-1)^i\binom{k}{i}(k-i)^n.$$

Los números de Stirling de segunda especie $S(n,k)$ cuenta en número de maneras que existen de hacer una partición de un conjunto de $n$ elementos en $k$ subconjuntos. De este modo:

$$B_{n}=\sum _{k=1}^{n}S(n,k).$$

Otra notación para los números de Stirling de segunda especie es:
$$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}:=S(n,k),$$

que nos permite la siguiente relación de recurrencia

$${\displaystyle \left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left\{{\begin{matrix}n-1\\k-1\end{matrix}}\right\}+k\left\{{\begin{matrix}n-1\\k\end{matrix}}\right\}}$$

con

$${\displaystyle \left\{{\begin{matrix}n\\1\end{matrix}}\right\}=1\quad {\mbox{ y }}\quad \left\{{\begin{matrix}n\\n\end{matrix}}\right\}=1.}$$

Este resultado nos da pie a contar las aplicaciones suprayecivas entre dos conjuntos finitos.

Teorema: Sean $A$ y $B$ dos conjuntos finitos de cardinal $n$ y $m$ respectivamente. El número de aplicaciones suprayectivas de $A$ en $B$ es de $$m!S(n,m).$$

Hoy hemos recordado la definición del conjunto de las permutaciones $S_n$, donde un elemento será de la forma:
$$\displaystyle \left(\begin{array}{cccccccc}1 & 2 & 3 & 4 & 5 \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 \cdots & \sigma_n \end{array}\right) .$$
Siendo $\sigma_i\in I=\{1,2,3,4,…,n\}$ y de modo que $\sigma_i\neq \sigma_j\forall i\neq j$.
Hemos visto que $S_n$ con la operación composición de permutaciones, $\circ$, le confiere una estructura de grupo; $(S_n,\circ)$ es un grupo.

Definimos un desarreglo como una permutación $\sigma\in S_n$ talque $\sigma_i\neq i\forall i\in I$. El propósito de la clase de hoy ha sido contar el número de desarreglos que podemos encontrar en el conjunto $S_n$.

El número de desarreglos de $n$ elementos también se conoce como subfatorial, a veces escrito como $!n$, que resulta
$${\displaystyle !n=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}.$$

Teniendo en cuenta que el sumatorio anterior se puede expresar como el número $e$, puede verse que

$${\displaystyle !n=\left[{\frac {n!}{e}}\right]\qquad {\mbox{para }}n\geq 1}$$
donde $[\,]$ denota la función parte entera más cercana.

Imaginemos que ahora pretendemos dejar fijo $k$ elementos y los restantes se desarreglen; es decir, queremos contar el número de permutaciones de $n$ elementos que dejan fijos $k$ de ellos, este número será:
$$R(n,k)=\binom{n}{k}\,!(n-k)$$

Para vuestra ayuda consultar Derangement.

El principio de inclusión-exclusión permite calcular el cardinal de la unión de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones.
Si consideramos que tenemos dos conjuntos finitos $A$ y $B$, resultará:
$$|A \cup B| = |A| + |B| – |A \cap B|.$$

Imaginemos que tenemos tres conjuntos finitos:
$$|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|.$$

Esto lo podemos generalizar. Si A₁, …, A_n son conjuntos finitos entonces:

$$\begin{align}\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n+1} \left|A_1\cap\cdots\cap A_n\right|\end{align}$$

Comenzamos definiendo el número binomial ${n\choose k}$, como el número de subconjuntos con k elementos, escogidos de un conjunto con n. Esta definición coincide con la combinaciones, por ese motivo la fórmula de calcularlo debe ser la misma
$$
{n\choose k} = \frac{ n(n-1)(n-2)\cdots (n-k+1)}{1\cdot 2\cdot 3 \cdots (k-1)\cdot k}
$$
Los coeficientes binomiales cumple propiedades muy interesantes como
$$
\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad \mbox{para todos los números enteros }n,k>0.
$$
Esta propiedad es muy importante y aparece en el El teorema de Pascal.

Con esto hemos sentados las bases para enunciar el Teorema del Binomio:

$$(x+y)^n=\sum_{k=0}^n {n \choose k}x^{n-k} y^k$$

Con este teorema podemos hacer fáciles ejercicios que resultan difíciles en su planteamiento.

Un resultado interesante es el siguiente. Utilizando el teorema del binomio podemos ver que

$$(1+x)^n=\sum_{k=0}^n {n \choose k}x^{k}$$

Podemos extender el teorema del binomio al conocido resultado de la fórmula de Leibniz: Dados $m$ enteros y un natural $n$, se tiene
$$(x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m} \prod_{1\le t\le m}x_{t}^{k_{t}}$$

Aquí definimos los coeficientes multinomiales como
$$
{n \choose k_1, k_2, \ldots, k_m} =\frac{n!}{k_1!· k_2! \cdots k_m!}
$$
donde $k_1+ k_2+ \ldots+ k_m=n$. Recordad que esto era equivalente a las permutaciones con repetición donde se repetían determinados elementos un determinado numero de veces.

Otro equivalente que podemos encontrar son los coeficientes $\left(\!\!{n \choose m}\!\!\right)$ que hacen referencia a las combinaciones con repetición:
$$\left(\!\!\!\!{n \choose m}\!\!\!\!\right)={n+m-1 \choose m}$$

Esto nos da pie a deducir que el número de coeficientes multinomiales de la fórmula de Leibniz es
$${n+m-1 \choose m-1}$$ que es coincidente con
$${n+m-1 \choose m-1}=\left(\!\!\!\!{m \choose n}\!\!\!\!\right)={m+n-1 \choose n},$$
ya que se corresponde con todos los posibles monomios $x_1^{k_1} \cdot x_2^{k_2} \cdots x_m^{k_m}$
Otra deducción observamos si consideramos $x_1 = x_2 = \cdots = x_m=1$, en tal caso la suma de los coeficientes multinomiales de la fórmula de Leibniz es
$$\sum_{k_1+k_2+\cdots+k_m=n} {n \choose k_1, k_2, \ldots, k_m}=m^n$$

Las combinaciones las introducimos para determinar en número de subconjuntos que podemos hacer con los elementos de un conjunto. Sabemos que el total serían el cardinal de las partes de un conjunto, pero en este caso queremos conocer los subconjuntos con un determinado cardinal. Así definimos las combinaciones de n elementos tomados de $m$ en $m$, con $m<n$, como los subconjuntos de $m$ elementos que podemos hacer con los $n$ elementos de un conjunto.

Como hemos visto hoy 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$.

Dos aplicaciones 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}$$

Sean $k,n\in\mathbb{N}$. El número de soluciones naturales (es decir, $x_i> 0 $) de la ecuación $$x_1+x_2+\ldots+x_n=k$$ es $$C_{k-1,k-n}$$

Introducimos las primeras de las técnicas básicas de conteo: la 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. 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 siposició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!}.$$

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

Lectura recomendada: ÁLGEBRA BÁSICA, Conjuntos y Estructuras Algebraicas, Juan De Burgos Román, Ingebook.

Además hemos tratado los principios básicos de conteo:

• Principio de adición
• Principio de multiplicación
• Principio de distribución

Ejercicio: Dado el grafo se puede afirmar que

a) no es plano b) tiene cinco regiones c) tiene seis regiones d) Ninguna de las anteriores.

Recordemos que en días pasados hablamos de grafos conexos e introducimos los grafos planos, mapas y la coloración de grafos.

La coloración de grafos es una forma de asignar etiquetas, llamadas colores, a elementos del grafo. En una coloración los vértices de un grafo cumplen que ningún vértice adyacente comparte el mismo color. Un caso particular es la coloración de las aristas: asigna colores a cada arista tal que aristas adyacentes no compartan el mismo color. El proceso lo podemos repetir con las caras de un grafo plano, asignando un color a cada cara o región tal que caras que compartan una frontera común tengan colores diferentes. En este caso se trata de un grafo plano.

Un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce. Un mapa es un grafo plano en el que nos interesan las caras entre las aristas.

Un de los resultado más interesante de los grafos planos es el Teorema de Euler:

Si un grafo simple plano conexo tiene $v$ vértices, $a$ aristas y $c$ caras, entonces $v − a + c = 2$

Para terminar os dejo unos enlaces de interés

• La conjetura de Steinberg es falsa.
• De rama en rama, pero por el camino más corto

Ejercicio: Dado el grafo se puede afirmar que tiene un

a) camino euleriano b) camino hamiltoniano c) circuito hamiltoniano d) Ninguna de las anteriores.

Si tenemos un grafo $G=(V,E)$ donde $V=\{v_1,…,v_n\}$, llamamos matriz de adyacencia del grafo a la matriz cuadrada nxn, $A=[a_{ij}]$, donde
$$a_{ij}=\left\{\begin{matrix}1 & \mbox{si } \{v_i,v_j\}\in E\\ 0 & \mbox{si } \{v_i,v_j\}\not\in E\end{matrix}\right.$$
En caso de que hubiera un bucle en $v_i$ $a_{ii}=1$. Si es el multigrafo $a_{ij}$ seríe en número de arcos que conecten los vértices.

La matriz de adyacencia de un grafo es simétrica, pues la arista une dos vértices independiente del comienzo y el final, pero si el grafo es un digrafo entonces los arcos sólo van en una dirección y $a_{ij}$ no tiene por qué coincidir con $a_{ji}$.

Del mismo modo podemos construir la matriz de incidencia, donde las columnas de la matriz representan las aristas del grafo y las filas representan a los distintos nodos. Por cada nodo unido por una arista, ponemos un uno 1 en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros 0. Un lazo cuenta doble. Si es un digrafo atenderemos como 1 si es un vértice de salida y -1 si es de entrada.

Grafos Eulerianos y Hamiltonianos.

Un camino euleriano es un camino que pasa por cada arista una y solo una vez. Un ciclo o circuito euleriano es un camino cerrado que recorre cada arista exactamente una vez. Un grafo se denomina grafo euleriano si un circuito euleriano.

Propiedades de los grafo eulerianos:

• Un grafo conexo y no dirigido se dice que es euleriano si cada vértice tiene un grado par.
• Un grafo no dirigido es euleriano si es conexo y si se puede descomponer en uno con los vértices disjuntos.
• Si un grafo no dirigido G es euleriano entonces su gráfo-línea L(G) se dice que es también euleriano.
• Un grafo dirigido es euleriano si es conexo y cada vértice tiene grados internos iguales a los externos.
• Un grafo no dirigido se dice que es susceptible de ser recorrido si es conexo y dos vértices en el grafo tienen grado impar.

El siguiente resultado nos sirve para determinar si un grafo contiene un camino euleriano o un ciclo:

Dado un grafo conexo (no existen nodos aislados) y no dirigido G, si G tiene exactamente dos vértices de grado impar, entonces G tiene un camino euleriano no cerrado. En caso de que todos los vértices tengan grado par, G tiene un ciclo euleriano.

Un camino hamiltoniano es un camino de un grafo que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano.

Ejempos de grafos Hamiltonianos:

• Todos los grafos ciclos son hamiltonianos.
• Todos los sólidos platónicos, (tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.) considerados como grafos, son hamiltonianos

Hay que tener en cuenta que cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano si se elimina cualquiera de sus aristas, pero un camino hamiltoniano puede ser extendido en ciclo sólo si los vértices de los extremos son adyacentes.

Un resultado que puede ayudarnos a distinguirlos es el siguiente:

Un grafo con n vértices (n > 3) es hamiltoniano si cada vértice tiene grado mayor o igual a n/2.

$\quad$

Ejercicio: Dados los grafos se puede afirmar que:

a) G’ no es conexo b) G no es bipartido. c) No son isomorfos d) Ninguna de las anteriores.

Comenzamos con la teoría de grafos. Para adentrarnos en este tema hablamos de dos ejemplos que nos ilustran perfectamente nuestro contenido:

• El problema de los puentes de Königsberg
• El problema matemático que nació en un campo de trabajo de la Segunda Guerra Mundial

Hoy hemos trabajado las diferentes definiciones que utilizaremos: grafos, digrafos y multigrafos y otras más, siguiendo la bibliografía recomendada. Además hemos visto algunas de sus propiedades.

Bibliografía recomendada

• Capítulo 2 de Números y Grafos, Juan de Burgos, ingebook
• Temas 7 y 9 de Matemática Discreta, Félix García, Edt. Thomson

También os recomiendo el visionado de este vídeo:

• Euler: una superestrella