Diario de Clases

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$$

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!}.$$

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

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

Hoy hemos tenido el parcial correspondiente a la 1º Unidad.

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$

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: Determinar la matriz de adyacencia y de incidencia del grafo

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

Continuando con las congruencias hoy hemos visto el Teorema chino del resto:

Supongamos que n₁, n₂, …, n_k son enteros coprimos dos a dos. Entonces, para enteros dados a₁,a₂, …, a_k, existe un entero x que resuelve el sistema de congruencias simultáneas

Más aún, todas las soluciones x de este sistema son congruentes módulo el producto N = n₁n₂…n_k.

En la última clase vimos el teorema de Euler que nos determina el inverso, cuando existe, de un elemento en $\mathbb{Z}_n$. Este teorema tenía un antecedente, que se conoce como el Teorema pequeño de Fermat:

Si $a,p\in\mathbb{Z}$ con $p$ primo y $p$ no divide a $a$, entonces $$a^{p-1}\equiv 1(p)$$

Consecuentemente si dado un número $n$ que no divida a $a$ se cumple $$a^{n-1}\not\equiv 1(n)$$
implicaría que $n$ no es primo, pues de lo contrario incumpliría el Teorema pequeño de Fermat.

Pues bien, este resultado lo podemos utilizar para chequear si un número es primo. Este test se denomina test de primalidad de Fermat.

Disponemos de un resultado que nos garantiza si un número es primo, el Teorema de Wilson:

El número $n\in\mathbb{Z},\, n>1$ es primo si, y sólo, si $$(n-1)!\equiv -1(n)$$

El problema es el cómputo del factorial que es treméndamente costoso para número muy grandes. Por ese motivo utilizamos los test de primalidad.

Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada $n$, no consigue verificar la hipótesis de un teorema cuya conclusión es que $n$ es compuesto.

El test de Fermat nos propone buscar si un número es compuesto probando las igualdades $$2^{n-1}\equiv 1(n),$$ $$3^{n-1}\equiv 1(n),$$ $$5^{n-1}\equiv 1(n),…$$ $$a^{n-1}\equiv 1(n),$$ hasta encontrar un valor de $1<a<n$ para el que no se cumpla.

Lo que ocurre es que podemos encontrar valores que verifican la igualdad siempre y no por ello son primos: son los conocidos números de Carmichael, o pseudoprimos.

Hay más test de este tipo, son conocidos como test probabilísticos de primalidad, pues no nos garantizan que es primo; más bien ofrecen una probabilidad de que sea primo.

El test de Fermat puede mejorarse utilizando el criterio de Euler:

Si $p\in\mathbb{Z}$ es primo y $p$ no divide a $a$, entonces $$a^\frac{p-1}{2}\equiv 1(p)\, \mbox{ ó, } a^\frac{p-1}{2}\equiv -1(p)$$

El test probabilístico de primalidad más utilizado es el de Rabin-Miller, basado en el resultado:

Sea $p\in\mathbb{Z},\, p>1$ primo impar y $k,m\in\mathbb{Z}$, tales que $p-1=2^km$, com $m$ impar. Entonces, para todo entero positivo $a$, menor que $p$, se cumple al menos una de los siguientes resultados:

• Algún número de la serie $a^{2^km},a^{2^{k-1}m},…,a^{m}$ es congruente con -1 módulo $p$.
• $a^m\equiv 1(p)$

Los pasados días hemos trabajado en los cimientos para abordar la ecuación de congruencias $$aX\equiv b (n)$$

Ahora podemos establecer los criterios que nos permitirán conocer cuándo existe solución:

La ecuación $aX \equiv b (n)$ tiene solución si, y sólo si, el $mcd(a,n)|b$

El procedimiento más sencillo es cuando $mcd(a,n)=1$, que en cuyo caso siempre tiene solución y esta se obtiene buscando el inverso de $a$ en $\mathbb{Z}_n$.

¿Qué ocurre si $mcd(a,n)=d$ y $d|b$? En tal caso la solución que buscamos dependerá de la solución de

$$\frac{a}{d}X_0 \equiv \frac{b}{d} \left(\frac{n}{d}\right)$$

En tal caso, las soluciones será varias y vendrás dadas por:

$$X\equiv \left[X_0+\frac{n}{d}k\right](n), $$

donde $k\in \{0,1,2,\ldots,d-1\}$.