Tarea 3, Matemáticas discretas

Fecha de entrega: 19 de febrero

Problema 1

Demuestra la identidad

$latex \displaystyle\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \binom{n}{3} +\cdots + (-1)^n\binom{n}{n} = 0$

utilizando el principio de inclusión-exclusión.

Problema 2

1. ¿De cuántas formas puedes acodomodar 8 torres (iguales) en un tablero de ajedrez de tal forma que no se ataquen entre sí?


2. Responde la pregunta anterior, pero si tenemos 4 torres blancas y 4 torres negras.


3. Repite la pregunta, pero en el caso en que las 8 torres son distintas.

Problema 3

Las palabras ERRATA y BARBAS tienen el mismo número de anagramas, porque tienen el mismo número de letras con las mismas repeticiones (6 = 2 + 2+ 1 + 1). En ese caso decimos que las palabras son "esencialmente iguales". Por ejemplo, SANTAS es esencialmente igual a ellas, también, pero HERRAJE no lo es (también tiene dos pares de letras repetidas, pero tiene 7 en total). Si dos palabras no son esencialmente iguales, entonces son "esencialmente distintas".

1. ¿Cuántas palabras distintas de 6 letras hay? (El afabeto tiene 27 letras.)


2. ¿Cuántas palabras esencialmente iguales a BARBAS hay?


3. ¿Cuántas palabras esencialmente distintas entre sí, de 6 letras, hay?


4. ¿Cuántas palabras esencialmente distintas de n letras hay?

Problema 4

1. ¿De cuántas formas podemos repartir n regalos entre k niños, si cada uno debe recibir al menos 2 regalos?


2. ¿De cuántas formas podemos repartir n regalos entre 2k niños, si los primeros k de ellos debe recibir al menos 1 regalo? (El resto puede no recibir regalo.)

Problema 5

Demuestra las identidades

1. $latex \displaystyle\binom{n}{0}\binom{m}{k} + \binom{n}{1}\binom{m}{k-1} + \cdots + \binom{n}{k-1}\binom{m}{1} + \binom{n}{k}\binom{m}{0} = \binom{n+m}{k}.$


2. $latex \displaystyle\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - \binom{n}{3} + \cdots + (-1)^m \binom{n}{m} = (-1)^m\binom{n-1}{m}.$


3. $latex \displaystyle\binom{n}{0}\binom{0}{m} + \binom{n}{1}\binom{1}{m} + \binom{n}{2}\binom{2}{m} + \binom{n}{3}\binom{3}{m} + \cdots + \binom{n}{n}\binom{n}{m} = \binom{n}{m} 2^{n-m}.$

En 3, suponemos que $latex m\le n$ y, en caso que $latex k<m$, entonces

$latex \displaystyle\binom{k}{m} = 0$.

Problema 6

Demuestra combinatóricamente que

$latex \displaystyle\binom{n}{0} + \binom{n}{1}2 + \binom{n}{2}4 + \cdots + \binom{n}{n-1} + \binom{n}{n}2^n = 3^n.$

Problema 7

Para seleccionar 2k + 1 elementos del conjunto {1,2,...,n}, escogemos primero el elemento central, luego k elementos a su izquierda, y finalmente k elementos a su derecha. Enuncia una identidad combinatórica describiendo este proceso.

Problema 8

Utiliza la fórmula de Stirling para aproximar el valor de

$latex \displaystyle \binom{n}{n/3},$

donde n es un múltiplo de 3.