1.4: ¿Qué es Combinatoria? (Ejercicios)

\(\rightarrow\)1. Recuerda que podemos escribir\(n\) como suma de\(n\) unos. ¿Cuántos signos más usamos? ¿De cuántas maneras podemos escribir\(n\) como suma de una lista de números\(k\) positivos? Tal lista se llama una composición de\(n\) en\(k\) partes.

2. En el Problema 1 definimos una composición de\(n\) en\(k\) partes. ¿Cuál es el número total de composiciones de\(n\) (en cualquier número de partes)?

\(\cdot\)3. Anote una lista de todas las secuencias\(16\) cero-uno de longitud cuatro comenzando con de tal\(0000\) manera que cada entrada difiera de la anterior cambiando solo un dígito. Esto se llama un Código Gris. Es decir, un Código Gris para\(0\) -\(1\) secuencias de longitud\(n\) es una lista de las secuencias para que cada entrada difiera de la anterior exactamente en un solo lugar. ¿Puedes describir cómo obtener un Código Gris para\(0\) -\(1\) secuencias de longitud cinco a partir del que encontraste para secuencias de longitud\(4\)? ¿Se puede describir cómo probar que existe un código Gray para secuencias de longitud\(n\)?

\(\rightarrow\)4. Use la idea de un código gris del problema 3 para probar bijectivamente que el número de subconjuntos de tamaño par de un conjunto de\(n\) elementos es igual al número de subconjuntos de tamaño impar de un conjunto\(n\) de elementos.

\(\rightarrow\)5. Se dice que una lista de paréntesis está equilibrada si hay el mismo número de paréntesis izquierdos que derecho, y como contamos de izquierda a derecha siempre encontramos al menos tantos paréntesis izquierdos como paréntesis de derecha. Por ejemplo, (((() ())) () está equilibrado y (()) y (() () ())) (() no lo son. ¿Cuántas listas equilibradas de paréntesis\(n\) izquierdo y\(n\) derecho hay?

* 6. Supongamos que planeamos poner seis computadoras distintas en una red como se muestra en la Figura 1.4.1 Las líneas muestran qué computadoras pueden comunicarse directamente con qué otras. Considera dos formas de asignar computadoras a los nodos de la red diferentes si hay dos computadoras que se comunican directamente en una asignación y que no se comunican directamente en la otra. ¿De cuántas maneras diferentes podemos asignar computadoras a la red?

Figura\(\PageIndex{1}\): Una red informática. (Copyright; autor vía fuente)

\(\rightarrow\)7. En una heladería circular, vamos a poner cuatro bolas de helado de cuatro sabores distintos elegidos de entre doce sabores. Suponiendo que colocamos cuatro bolas del mismo tamaño como si estuvieran en las esquinas de un cuadrado, y reconociendo que mover el platillo no cambia la forma en que hemos puesto el helado en el platillo, ¿de cuántas maneras podemos elegir el helado y ponerlo en el platillo?

\(\rightarrow\)8. En todas las formas que puedas, demuéstralo\(\binom{n}{k} \binom{n-k}{m} = \binom{n}{m} \binom{n-m}{k}\).

\(\rightarrow\)9. Un club de tenis tiene\(4n\) miembros. Para especificar un partido de dobles, elegimos dos equipos de dos personas. ¿De cuántas maneras podemos organizar a los miembros en partidos de dobles para que cada jugador esté en un partido de dobles? ¿De cuántas maneras podemos hacerlo si especificamos además quién sirve primero en cada equipo?

10. Un pueblo tiene\(n\) farolas que recorren el lado norte de Main Street. Los postes en los que están montados necesitan ser pintados para que no se oxiden. ¿De cuántas maneras se pueden pintar con rojo, blanco, azul y verde si un número par de ellos se va a pintar de verde?

* 11. Tenemos bolas de ping-pong\(n\) idénticas. ¿De cuántas maneras podemos pintarlas de rojo, blanco, azul y verde?

* 12. Tenemos bolas de ping-pong\(n\) idénticas. ¿De cuántas maneras podemos pintarlas de rojo, blanco, azul y verde si usamos pintura verde en un número par de ellas?