Ir al contenido principal

Tarea 6, Matemáticas discretas

Fecha de entrega: 11 de junio


Problema 1


Sean $latex 2n$ puntos en un círculo. Muestra que el número de formas en que podemos unir estos puntos en pares, de tal manera que los $latex n$ segmentos no se crucen, es igual al número de Catalan $latex C_n$.

Problema 2


Muestra que el número de arreglos de $latex 2\times n$

$latex \begin{pmatrix}x_{11}& x_{12}&\ldots& x_{1n}\\x_{21}& x_{22}&\ldots& x_{2n}\end{pmatrix}$


con los números $latex 1, 2, \ldots, 2n$ de tal forma que cada renglón y cada columna es creciente, es igual a $latex C_n$.

Problema 3


Determina la división en diagonales del polígono convexo que corresponde a las siguientes multiplicaciones.

  1. $latex a_1\times(((a_2\times a_3)\times(a_4\times a_5))\times a_6)$

  2. $latex ((a_1\times a_2)\times (a_3\times (a_4\times a_5)))\times((a_6\times a_7)\times a_8)$


Problema 4



  1. Calcula la tabla de diferencias para la sucesión $latex x_n = 2n^2-n+3$, y encuentra una fórmula para $latex \sum_{k=0}^n x_k$.

  2. Si la sucesión $latex x_n$ está determinada por un polinomio cúbico, y los primeros términos del renglón 0 de su tabla de diferencias son 1, -1, 3, 10, determina $latex x_n$ y encuentra una fórmula para $latex \sum_{k=0}^n x_k$.

  3. Encuentra la suma $latex 1^5 + 2^5 + \ldots + n^5$.


Problema 5


Muestra las siguientes identidades de los números de Stirling del segundo tipo.

  1. $latex S(n,1) = 1, \quad n\ge1$

  2. $latex S(n,2) = 2^{n-1}-1, \quad n\ge 2$

  3. $latex S(n,n-1) = \binom{n}{2}, \quad n\ge1$

  4. $latex S(n,n-2) = \binom{n}{3} + 3\binom{n}{4}, \quad n\ge 2$.


Problema 6


Sea $latex A$ un conjunto con $latex n$ elementos y $latex B$ un conjuntos de $latex k$ elementos. Muestra que el número de de funciones $latex f:A\to B$ sobreyectivas es

$latex k!S(n,k)$.



Problema 7


Muestra las siguientes identidades de los números de Stirling del primer tipo.

  1. $latex s(n,1) = (n-1)!,\quad n\ge1$

  2. $latex s(n,n-1) = \binom{n}{2}, \quad n\ge1$


Problema 8


Verifica que $latex [n]_n = n!$, y escribe $latex n!$ como un polinomio en $latex n$ utilizando los números de Stirling del primer tipo. Hazlo de manera explícita para $latex n=3, 6$.

Comentarios