MAD: Combinaciones con repetición

El pasado día definimos la combinaciones de elementos tomados de $m$ en $m$, con $m<n$, como el número de subconjuntos de $m$ elementos que podemos hacer con los $n$ elementos de un conjunto: $$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$.

Ejercicio: ¿Cuántas soluciones enteras positivas admite la ecuación $x+y+z=7$.
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Combinaciones con repetición

MAD: Combinaciones

Hasta hoy hemos visto:

  • 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$. $V_{n,m}=\frac{n!}{(n-m)!}.$
  • Permutaciones de $n$ elemento, al número de aplicaciones biyectivas que podemos hacer del conjunto $A$, de cardinal $n$, en el conjunto $B$, de cardinal $n$, o en él misno.. $P_{n}=n!$.
  • Variaciones con repetición de $m$ (0<$m$) elementos de un conjunto de $n$ elementos (0<$n$), a las aplicaciones de un conjunto de $m$ elementos de un conjunto de $n$ elementos, $VR_{n,m}=n^m$
  • Permutación circular, aquella permutación que no importa por donde comience, $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)!}$$

Ejercicio:¿Cuántas palabras distintas podemos hacer con las letras de la palabara INFORMATICA?
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Combinaciones

MAD: Permutaciones

El pasado día terminamos introduciéndo las variaciones. Hoy comenzamos con 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)!.$$

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 Comentarios desactivados en MAD: Permutaciones

MAD: Principios básicos

Hoy hemos tratado los principios básicos de conteo:

  • Principio de adición
  • Principio de multiplicación
  • Principio de distribució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)!}.$$

Ejercicio: Si C es un conjunto finito de n elementos,|C|=n, ¿cuántos elementos contiene las partes de C,℘(C)?
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Principios básicos

MAD: Teoría combinatoria

Comenzamos la parte de Teoría combinatoria, recordando las definiciones de

  • Conjuntos, cardinalidad, partes de un conjunto.
  • Aplicaciones entre conjuntos finitos
    • Inyectivas,
    • sobreyectivas
    • biyectivas

 

Ejercicio: ¿Cuántas aplicaciones inyectivas podemos hacer entre los conjuntos A={1,2,3} y B={a,b,c,d}?
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Teoría combinatoria

MAD: Parcial

Hemos realizado el parcial con la Primera Unidad de la asignatura.

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Parcial

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{ \’o, } 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 Comentarios desactivados en MAD: Test de primalidad

MAD: La función φ de Euler.

Hemos estado viendo que resolver la ecuación $aX \equiv b (n)$ implicaba encontrar el inverso de $a$ en $\mathbb{Z}_n$. La pregunta que nos planteamos es cómo hacerlo de forma sencilla. Primero nos enfrentamos a saber cuántos elementos de $\mathbb{Z}_n$ tienen inverso. Respuesta que nos la dará la conocida 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)$

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 18X≡ 33 (105)
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: La función φ de Euler.

MAD: Ecuación de congruencias II

El pasado día vimos que

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

Siendo el caso más sencillo cuando $mcd(a,n)=1$. Pero 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)$$

Ejercicio: Resolver 12X≡ 22 (70)
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Ecuación de congruencias II

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

Ejercicio: Resolver 6X≡ 11 (35)
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Ecuación de congruencias