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