2.E: Inclusión-Exclusión (Ejercicios)

Última actualización
Guardar como PDF

Page ID: 117108

\( \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}}\)

2.1: La fórmula de inclusión-exclusión

Ejercicio\(\PageIndex{1.1}\)

Enumere las 6 soluciones a la ecuación restringida en el Ejemplo 2.1.1 y enumere los 6 submulticonjuntos correspondientes.

Ejercicio\(\PageIndex{1.2}\)

Encuentre el número de soluciones enteras a\(x_1+x_2+x_3+x_4=25\),\(1\le x_1\le6\),\(2\le x_2\le 8\),\(0\le x_3\le8\),\(5\le x_4\le9\).

Ejercicio\(\PageIndex{1.3}\)

Encuentra el número de submulticonjuntos\(\{25\cdot a,25\cdot b,25\cdot c,25\cdot d\}\) de tamaño 80.

Ejercicio\(\PageIndex{1.4}\)

Recordemos que\(\left\{\begin{array}{c}n\\k\end{array}\right\}\) es un número Stirling del segundo tipo (Definición 1.9.1). \(n\ge k\ge 0\)Demuéstralo para,\[ \left\{\begin{array}{c}n\\k\end{array}\right\}={1\over k!}\sum_{i=0}^k (-1)^{k-i}i^n{k\choose i}. \nonumber\] Haz\(n=0\) como un caso especial, luego usa inclusión-exclusión para el resto. Se puede asumir, por convención, eso\(0^0=1\).

2.2: Permutaciones de posición prohibida

Ejercicio\(\PageIndex{2.1}\)

Demostrar que\( D_n=nD_{n-1}+(-1)^n\) cuando\(n\ge2\).

Ejercicio\(\PageIndex{2.2}\)

Demostrar que\(D_n\) es par si y sólo si\(n\) es impar.

Ejercicio\(\PageIndex{2.3}\)

Proporcione los detalles que faltan para el Ejemplo 2.2.1. ¿Qué es\(\lim_{n\to\infty} {Q_n\over n!}\)?

Ejercicio\(\PageIndex{2.4}\)

Encuentra el número de permutaciones de las\(1,2,\ldots,8\) que no tienen número impar en la posición correcta.

Ejercicio\(\PageIndex{2.5}\)

Encuentra el número de permutaciones de\(1,2,\ldots,8\) que tengan al menos un número impar en la posición correcta.

Ejercicio\(\PageIndex{2.6}\)

¿Cuántas permutaciones de\([n]\) tienen exactamente\(k\) números en sus posiciones correctas?

Ejercicio\(\PageIndex{2.7}\)

Dar una prueba combinatoria de que\[n!=\sum_{k=0}^n {n\choose k}D_{n-k}.\nonumber\]

Ejercicio\(\PageIndex{2.8}\)

Un pequeño tiovivo tiene 8 asientos ocupados por 8 niños. ¿De cuántas maneras pueden los niños cambiar de lugar para que ningún niño se siente detrás del mismo niño que en el primer viaje? Los asientos no importan, sólo las posiciones relativas de los niños.

Ejercicio\(\PageIndex{2.9}\)

En el camino a una fiesta todos comprueban un abrigo y una bolsa en la puerta. Al salir, el asistente reparte abrigos y bolsas al azar. ¿De cuántas maneras se puede hacer esto si

¿Nadie consigue ni su propio abrigo ni su propia bolsa?
Uno puede conseguir su propio abrigo, o bolsa, pero no ambos.

Ejercicio\(\PageIndex{2.10}\)

Supongamos que la\(n\) gente está sentada en\(m\ge n\) sillas en una habitación. En algún momento hay un descanso, y todos salen de la habitación. Cuando regresen, ¿de cuántas maneras pueden estar sentados para que ninguna persona ocupe la misma silla que antes del descanso?