Tarea 7, Matemáticas discretas

Fecha de entrega: 23 de marzo

Problema 1

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 2

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 3

Formula y demuestra el siguiente enunciado como un teorema de grafos: "En un grupo de personas existen dos de ellas que conocen al mismo número de personas cada uno".

Problema 4

1. Por medio de un ejemplo, muestra que si eliminamos una arista de un grafo conexo G, el resultado puede ser un grafo disconexo.


2. Muestra que, si la arista eliminada pertenece a un ciclo subgrafo de G, entonces el resultado es conexo.

Problema 5

Sea G un grafo y u, v dos vértices de G.

1. Muestra que, si existe una caminata de u a v, entonces existe una trayectoria de u a v.


2. Utiliza el inciso anterior para dar una demostración distinta a la vista en clase para el siguiente enunciado: si p, q, y r son vértices de G tales que existe una trayectoria de p a q y una trayectoria de q a r, entonces existe una trayectoria de p a r.

Problema 6

Muestra que si el grafo G con n vértices tiene más de $latex \binom{n-1}{2}$ aristas, entonces es conexo.