MAD: Particiones

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 B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, …

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

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

Ejercicio: Justificar que $S(n,2)=2^{n-1}-1$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Particiones

MAD: Desarreglos

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

Para vuestra ayuda consultar Derangement.

Ejercicio: Calcular el número de desarreglos de $S_5$.
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Desarreglos

MAD: Principio de inclusión-exclusión

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 A1, …, An 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}$$

Ejercicio: ¿Cuántos números del 1000 a 9999 hay que no sean múltiplos de 3 y/o de 5 y/o de 7?
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Principio de inclusión-exclusión

MAD: Teorema del binomio

El pasado día vimos el número binomial y dejamos las bases puestas 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.

Para el próximo día terminamos la parte de los números binomiales extendiendo 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}}$$

Ejercicio: Calcular el coeficiente de $x^3y^4z^2$ del desarrollo de $(x+y+3z)^9$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Teorema del binomio

MAD: Número binomial

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.

TrianguloPascalC.svg
«TrianguloPascalC» por DriniTrabajo propio. Disponible bajo la licencia CC BY-SA 3.0 vía Wikimedia Commons.

Este “triángulo” surge de cuando expresamos los coeficientes de los desarrollo binómico $(x+y)^n$, que no lleva al Teorema del Binomio:

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

Ejercicio: Calcular el coeficiente de $x^3y^4$ del desarrollo de $(x-2y)^7$
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Número binomial

MAD: Combinaciones

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

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

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 froma, 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á indetificada 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 podemos hacer con las letras de la palabara INFORMATICA?
Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Permutaciones

MAD: Teoría combinatoria

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

  • Conjuntos
  • Aplicaciones
    • Inyectivas,
    • sobreyectivas
    • biyectivas

HContinuamos tratado los principios básicos de conteo:

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

Terminamos introduciéndonos en la primera 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)!}.$$

La variaciones nos permiten definir las Permutaciones, como $$P_n=V_{n,n}=n!.$$
Puede verse que la permutaciones se corresponde con las aplicaciones biyectivas entre dos conjuntos finitos del mismo cardinal.

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: 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: Coloración de grafos y árboles

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$

Terminamos introduciendo los árboles. Un árbol es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino. Un bosque es una unión disjunta de árboles. Un árbol a veces recibe el nombre de árbol libre.

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Coloración de grafos y árboles