¿Se puede usar el principio de inclusión/exclusión para contar elementos en la intersección de una secuencia de conjuntos?

Question

¿Se puede usar el principio de inclusión/exclusión para contar elementos en la intersección de una secuencia de conjuntos?

recursión
Matemáticas
combinatoria
exclusión inclusión

mística griega

El principio de inclusión-exclusión (PIE) se usa a menudo para contar el número de elementos en una unión de $n$ conjuntos en términos de una suma alterna de sus diversas intersecciones:

| ⋃_{i \in [norte]} A_{i} | = \sum_{j \subseteq [norte]} (- 1)^{| j | - 1} | ⋂_{j \in j} A_{j} |

$\left |\bigcup_{i \in [n]} A_i \right| =\sum_{J \subseteq [n]}(-1)^{\left|J\right|-1}\left|\bigcap_{j \in J}A_j\right|$

dónde $[n] = \{1,...n\}$ . Estoy realizando un experimento de psicología que requiere que los sujetos cuenten la cantidad de elementos en varios conjuntos y en varias uniones de estos conjuntos. Me gustaría poder calcular a partir de los datos de comportamiento el $implied$ número de elementos en cualquier intersección arbitraria de estos conjuntos. Parece que esto se puede realizar escribiendo el PIE en la siguiente forma recursiva:

| ⋂_{j \in j \subseteq [norte]} A_{j} | = [| ⋃_{i \in j} A_{i} | - \sum_{S ⊊ j} (- 1)^{| S | - 1} | ⋂_{s \in S} A_{s} |] (- 1)^{| j | - 1}

$\left|\bigcap_{j \in J \subseteq [n]}A_j\right| = \left[\left|\bigcup_{i \in J}A_i\right| - \sum_{S \subsetneq J}(-1)^{\left|S\right|-1}\left|\bigcap_{s \in S}A_s\right|\right](-1)^{\left|J\right|-1}$

Dos preguntas: (1) ¿Es correcta esta declaración alternativa (recursiva) del PIE? (2) Si es así, ¿alguien ha visto (o puede proporcionar) una solución no recursiva que exprese la intersección de la $A_j's$ en términos de uniones explícitas solamente?

Respuestas (1)

¿Se puede usar el principio de inclusión/exclusión para contar elementos en la intersección de una secuencia de conjuntos?

joriki · Answer 1

Debe excluir el conjunto vacío en su suma.

Debido a la dualidad entre unión e intersección, el principio de inclusión-exclusión puede enunciarse alternativamente en términos de uniones o intersecciones. Sustituyendo los complementos $\overline{A_i}$ Para el $A_i$ en tu primera ecuación se obtiene

| ⋃_{i \in [norte]} \bar{A_{i}} | = \sum_{\emptyset \neq j \subseteq [norte]} (- 1)^{| j | - 1} | ⋂_{j \in j} \bar{A_{j}} |

$\left |\bigcup_{i \in [n]} \overline{A_i} \right| =\sum_{\emptyset\ne J \subseteq [n]}(-1)^{\left|J\right|-1}\left|\bigcap_{j \in J}\overline{A_j}\right|$

y por lo tanto

| \bar{⋂_{i \in [norte]} A_{i}} | = \sum_{\emptyset \neq j \subseteq [norte]} (- 1)^{| j | - 1} | \bar{⋃_{j \in j} A_{j}} | .

$\left |\overline{\bigcap_{i \in [n]} A_i} \right| =\sum_{\emptyset\ne J \subseteq [n]}(-1)^{\left|J\right|-1}\left|\overline{\bigcup_{j \in J}A_j}\right|\;.$

Desde $|\overline{S}|=N-|S|$ , con $N$ el número total de elementos, esto produce

norte - | ⋂_{i \in [norte]} A_{i} | = \sum_{\emptyset \neq j \subseteq [norte]} (- 1)^{| j | - 1} (norte - | ⋃_{j \in j} A_{j} |) .

$N-\left |\bigcap_{i \in [n]} A_i \right| =\sum_{\emptyset\ne J \subseteq [n]}(-1)^{\left|J\right|-1}\left(N-\left|\bigcup_{j \in J}A_j\right|\right)\;.$

la suma termina $N$ a la derecha seria $0$ si $J=\emptyset$ fueron incluidos, por lo que cancela el $N$ a la izquierda. De este modo

| ⋂_{i \in [norte]} A_{i} | = \sum_{\emptyset \neq j \subseteq [norte]} (- 1)^{| j | - 1} | ⋃_{j \in j} A_{j} |,

$\left |\bigcap_{i \in [n]} A_i \right| =\sum_{\emptyset\ne J \subseteq [n]}(-1)^{\left|J\right|-1}\left|\bigcup_{j \in J}A_j\right|\;,$

la forma dual del principio que necesitas.

¿Se puede usar el principio de inclusión/exclusión para contar elementos en la intersección de una secuencia de conjuntos?

mística griega

Respuestas (1)

joriki

¿Cuántas permutaciones de {1,2,3,...,n}{1,2,3,...,n}\{1,2,3,...,n\} hay sin 2 ¿numeros consecutivos?

Error lógico en problema de probabilidad sobre cartero entregando cartas para que cada casa reciba una carta equivocada

Problema de Combinatoria (Bajar de un ascensor)

Número de arreglos de asientos circulares si cada persona no puede sentarse junto a otras dos personas

Formulación de una suma alterna de combinaciones de productos

¿Inclusión/exclusión, al menos y exactamente arreglos?

nnn invitados, cada invitado trae un premio, ¿de cuántas maneras se pueden repartir los premios para que nadie reciba el premio que trajeron?

¿Cuántos enteros positivos por debajo de 201201201 son múltiplos de 444 pero no múltiplos de 101010?

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

4 parejas y 4 personas solas sentadas en 3 mesas redondas