5.4: El Principio de Inclusión y Exclusión (Ejercicios)

Última actualización
Guardar como PDF

Page ID: 112571

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

1. A cada persona que asiste a una fiesta se le ha pedido que traiga un premio. La persona que planea la fiesta ha arreglado para entregar exactamente tantos premios como invitados haya, pero cualquier persona puede ganar cualquier cantidad de premios. Si hay\(n\) invitados, ¿de cuántas formas se pueden entregar los premios para que nadie obtenga el premio que trajo?

2. Hay\(m\) alumnos que asisten a un seminario en una sala con\(n\) asientos. El seminario es largo, y en el medio el grupo toma un descanso. ¿De cuántas maneras pueden regresar los alumnos a la sala y sentarse para que nadie esté en el mismo asiento que antes?

3. ¿Cuál es el número de formas de repartir\(k\) piezas de dulces de un suministro ilimitado de dulces idénticos a\(n\) los niños (dónde\(n\) se fija) para que cada niño obtenga entre tres y seis piezas de caramelo (inclusive)? Si has hecho el Problema Suplementario 1 en el Capítulo 4 compara tu respuesta en ese problema con la tuya en este.

4. ¿De cuántas maneras se pueden disponer libros\(k\) distintos en\(n\) estantes para que ninguna estantería obtenga más que\(m\) libros?

5. Supongamos que\(n\) los niños se unen en círculo para un juego en la guardería. El juego involucra a todos cayendo (y soltando). ¿De cuántas maneras pueden volver a unir las manos en círculo para que nadie tenga a la misma persona inmediatamente a la derecha las dos veces que el grupo se una de las manos?

\(*\)6. Supongamos que la\(n\) gente se une de brazos en una danza folclórica y baila en círculo. Posteriormente, soltaron y bailan un poco más, después de lo cual vuelven a unir los brazos en círculo. ¿De cuántas maneras pueden unir los brazos la segunda vez para que nadie se vincule con una persona con la que antes se vinculó de brazos?

\(*\)7. (Un reto; ¡el autor no ha tratado de resolver éste!) Rehacer Problema 6 en el caso de que haya\(n\) hombres y\(n\) mujeres y cuando las personas se arreglen en círculo lo hacen alternando género.

8. Supongamos que tomamos dos gráficas\(G_1\) y\(G_2\) con conjuntos de vértices disjuntos, elegimos un vértice en cada gráfica, y conectamos estos dos vértices por un borde\(e\) para obtener una gráfica\(G_{12}\). ¿Cómo se\(G_{12}\) relaciona el polinomio cromático de con los de\(G_1\) y\(G_2\)?