MAD: Variaciones y Permutaciones

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

Ejercicio:¿Cuántas palabras distintas de cinco letras, podemos hacer con las letras de {a,b,c,d,e}?
Posted in: Matemática Discreta by admin No Comments

MAD: Teoría combinatoria

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: Encontrar el cardinal del conjunto de las partes de un conjunto finito de n elementos.
Posted in: Matemática Discreta by admin No Comments

MAD: Test de primalidad

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)$
Ejercicio: Verificar que 561 es un número de Carmichael
Posted in: Matemática Discreta by admin No Comments

MAD: Ecuación de congruencias

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

Ejercicio: Resolver 6X≡ 11 (35)
Posted in: Matemática Discreta by admin No Comments

MAD: Función φ de Euler

En el día de hoy hemos visto la función $\varphi $ de Euler. Esta función se define como

$$\varphi (n)=|\{m\in\mathbb{Z}^+|m<n, mcd(n,m)=1\}|.$$

Esta función cumple propiedades muy interesantes, como

  • Si $p$ es primo, $\varphi (p)=p-1$
  • Si $p$ es primo, $\varphi (p^\alpha)=p^{\alpha -1}(p-1)$
  • Si $mcd(n,m)=1$ es $\varphi (nm)=\varphi (n)\varphi (m)$

Estos resultados nos sirven para exponer el Teorema de Euler:

Si $a,n\in\mathbb{Z}$ con $mcd(n,a)=1$, entonces $a^{\varphi (n)}\equiv 1(n)$

Este resultado ofrece además una forma de obtener el inverso de un número en $\mathbb{Z}_n$, siempre que este exista.

La descomposición de un numero entero en sus factores primos nos permite formular un resultado práctico para calcular la función $\varphi$

Si $n\in\mathbb{Z}$ es ${\displaystyle n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}}$, entonces $$\varphi (n)=n\sum_{i=1}^r\left(1-\frac{1}{p_i}\right)$$

$\quad $

Ejercicio: Resolver $123321^{123}\equiv X(36)$
Posted in: Matemática Discreta by admin No Comments

MAD: Restos potenciales

Uno de nuestros cometido será resolver la ecuación de congruencias $$aX\equiv b (m)$$

Para comenzar trataremos los restos potenciales; es decir, $$a^i\equiv r_i(n).$$
Estos restos cumplen las siguientes propiedades:
$$\begin{align*}
a^0 &\equiv 1(n) \\
a &\equiv a(n) \\
a^k&\equiv r_k(n)\Rightarrow a^{k+1}\equiv a\cdot r_k(n)
\end{align*}$$

Además a partir de un resto que se repiten, se repiten todos en forma ciclica.

La utilización de los restos potenciales nos sirve para establecer un criterio de divisibilidad que permite saber las propiedades de un número para que sea divisible por otro:

Sea dados $m,n\in\mathbb{Z}^+$ para todo entero $$a=a_kn^k+a_{k-1}n^{k-1}+…+a_1n+a_0$$ si $n^i\equiv r_i(m)$ entonces $$a\equiv a_kr_k+…+a_0r_0(m)$$

Esto nos permite justificar, por ejemplo, que un número es divisible por 3 si la suma de sus dígitos es divisible por 3.

Ejercicio: Resolver 1²+2²+3²+4²+…+99²+100²≡ X (4)
Posted in: Matemática Discreta by admin No Comments

MAD: Congruencias

Utilicemos wiki para definir que entendemos por congruencia:

un término usado en la teoría de números, para designar que dos números enteros $a$ y $b$ tienen el mismo resto al dividirlos por un número natural $m\neq 0$, llamado el módulo; esto se expresa utilizando la notación $$a \equiv b (m).$$

Esta definición nos permitía construir clases de equivalencia de números enteros, también llamadas clases de congruencia, que puede ser dotadas de un sistema aritmético. Los conjuntos de estas clases son los conocidos $\mathbb{Z}_n$, que poseen estructura de anillo.

Recordemos que estos conjuntos también puede ser cuerpos, pero solo si $n$ es primo.

$\mathbb{Z}_p$ es un cuerpo si, y solo si, $p$ es primo

En la clase de hoy hemos recordados estos conjuntos y establecido alguna de sus propiedades. Como ejemplo os dejo estos enlaces:

Ejercicio: Probad que si $an \equiv bn (m)$ y $mcd(m,n)=1$, entonces $a \equiv b (m)$
Posted in: Matemática Discreta by admin No Comments

MAD: Ecuaciones diofánticas de tres variables

El pasado día introducimos las ecuaciones lineales diofánticas. En particular, abordamos la solución de la ecuación $$ax+by=c.$$ Hoy nos centramos en la ecuación $$ax+by+cz=n.$$
Como comentamos el día anterior, esta ecuación tiene solución si $m.c.d(a,b,c)|n$. En caso de tener solución podemos calcularla dependiendo de dos casos. El más sencillo es el que plantea cuando dos de los coeficientes de la ecuacion son coprimos. En tal caso, la ecuación plantea una solución parámetrica cuyo parámetro es la variable del coeficiente no coprimo. Es decir, si $m.c.d(a,b)=1$, planteamos la ecuación
$$ax+by=n-c\lambda,$$
donde desginamos $z=\lambda$, la resolvemos como ya conocemos.

Ejercicio: Resolver la ecuación diofántica 3x+2y+6z=7.
Posted in: Matemática Discreta by admin No Comments

MAD: Sistema de ecuaciones diofánticas

Consideremos que tenemos un sistema de dos ecuaciones diofánticas de tres variables Con lo que hemos visto cada ecuación define una plano, que puede o no tener soluciones enteras, así el sistema dado por dos planos es una recta. Resolverlo es afrontar la ecuación diofántica de dos variables resultado de simplificar el sistema.

Por ejemplo: sea el sistema
$$
\left\{\begin{array}{ll}
a_1x+b_1y+c_1z=n_1 \\ a_2x+b_2y+c_2z=n_2
\end{array}\right.
$$
Podemos simplificar la variable $x$, multiplicando la primera por $a_2$, la segunda por $-a_1$ y sumando ambas igualdades:
$$
\left\{\begin{array}{ll}
a_2a_1x+a_2b_1y+a_2c_1z=a_2n_1 \\ -a_1a_2x-a_1b_2y-a_1c_2z=-a_1n_2
\end{array}\right. \to (a_2b_1-a_1b_2)y+(a_2c_1-a_1c_2)z=a_2n_1-a_1n_2
$$
El resultado es una ecuación diofántica de dos variables. Notar que convendría la elección de una variable a simplificar que facilite la ecuación resultante.

Ejercicio: Resolver el sistema de ecuaciones diofánticas
$$
\left\{\begin{array}{ll}
2x+3y-z=9 \\ -x+2y+3z=-2
\end{array}\right.
$$
Posted in: Matemática Discreta by admin No Comments

MAD: Ecuaciones diofánticas

Comenzamos con el tema de ecuaciones diofánticas. Recordad que llamamos ecuación diofántica a cualquier ecuación algebraica, generalmente de varias variables, planteada sobre el conjunto de los números enteros $\mathbb{Z}$; es decir, se trata de ecuaciones cuyas soluciones son números enteros.

Nosotros solo trataremos las ecuaciones diofántica lineal; es decir, la ecuación $$a_1x_1 + a_2x_2 + … + a_nx_n = C,$$ y, en concreto, solo de dos o tres variables.

Hemos visto el teorema que nos afirma que

$$a_1x_1 + a_2x_2 + … + a_nx_n = C,$$

tiene solución sii $d=mcd(a_1,a_2,…,a_n)$ divide a $C$.

Primero tratamos la ecuación diofántica de dos variables, $$ax+by=c$$ aprendiendo a resolverla en el caso de que pueda resolverse. Recordad que para ello necesitamos que $mcd(a,b)|c$. Nos apoyamos en el hecho de que la existencia de una solución particular, $$ax_0+by_0=mcd(a,b),$$ dada por el Teorema de Bezout, permitirá encontrar las infinitas soluciones.

Ejercicio: Resolver la ecuación diofántica $$4x+15y=37.$$
Posted in: Matemática Discreta by admin No Comments