Artículos

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


Ej 2.1.1 Enumere las 6 soluciones de la ecuación restringida en el ejemplo 2.1.1y enumere los 6 submultisets correspondientes.

Ej 2.1.2 Encuentra el número de soluciones enteras para (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 ).

Ej 2.1.3 Encuentre el número de submultisets de ( {25 cdot a, 25 cdot b, 25 cdot c, 25 cdot d } ) de tamaño 80.

Ej 2.1.4 Recuerde que ( stwo {n} {k} ) es un número de Stirling del segundo tipo (definición 1.8.1). Demuestre que para (n ge k ge 0 ), () stwo {n} {k} = {1 over k!} Sum_ {i = 0} ^ k (-1) ^ { ki} i ^ n {k elija i}. () Haga (n = 0 ) como un caso especial, luego use inclusión-exclusión para el resto. Puede asumir, por convención, que (0 ^ 0 = 1 ).

2.2: Permutaciones de posición prohibidas

Ej 2.2.1 Demuestre que $ ds D_n = nD_ {n-1} + (- 1) ^ n $ cuando $ n ge2 $.

Ej 2.2.2 Demuestre que $ D_n $ es par si y solo si $ n $ es impar.

Ej 2.2.3 Proporcione los detalles que faltan, por ejemplo 2.2.1. ¿Qué es $ ds lim_ {n to infty} {Q_n over n!} $?

Ej 2.2.4 Encuentra el número de permutaciones de $ 1,2, ldots, 8 $ que no tienen un número impar en la posición correcta.

Ej 2.2.5 Encuentra el número de permutaciones de $ 1,2, ldots, 8 $ que tienen al menos un número impar en la posición correcta.

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

Ej 2.2.7 Da una prueba combinatoria de que $$ n! = Sum_ {k = 0} ^ n {n elige k} D_ {n-k}. $$

Ej 2.2.8 Un pequeño tiovivo tiene 8 asientos ocupados por 8 niños. ¿De cuántas formas 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? No importan los asientos, solo las posiciones relativas de los niños.

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

(a) ¿Nadie recibe su propio abrigo ni su propio bolso?

(b) Uno puede conseguir su propio abrigo o bolso, pero no ambos.

Ej 2.2.10 Suponga que $ n $ personas están sentadas 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 formas se pueden sentar para que ninguna persona ocupe la misma silla que antes del receso?


Ver el vídeo: Ejercicio desafío números. Divisibilidad. Resuelto a través de técnica inclusiónexclusión. (Enero 2022).