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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Número binomial

MAD: Variaciones, permutaciones y combinaciones

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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Variaciones, permutaciones y combinaciones

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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Teoría combinatoria

MAD: Parcial

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

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

MAD: Mapas y coloración de grafos.

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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Mapas y coloración de grafos.

MAD: Matriz de adyacencia de un grafo

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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Matriz de adyacencia de un grafo

MAD: Teoría de Grafos

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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Teoría de Grafos

MAD: Sistema de congruencias

Continuando con las congruencias hoy hemos visto el Teorema chino del resto: Supongamos que n1, n2, …, nk son enteros coprimos dos a dos. Entonces, para enteros dados a1,a2, …, ak, 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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Sistema de congruencias

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$ […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Test de primalidad

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 […]

Posted in: Matemática Discreta by admin Comentarios desactivados en MAD: Ecuación de congruencias