20 votos

Inclusión-exclusión-como fraccionario de la suma es positiva?

Deje $A_1,A_2,\ldots,A_n$ ser finito no vacío de conjuntos. Es cierto que $$\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}$$ es siempre positivo?

Para $n=1$ esto es obvio. Para $n=2$ esto es cierto porque los $\frac{1}{|A_1|}\geq\frac{1}{|A_1\cup A_2|}$ $\frac{1}{|A_2|}>0.$

Para $n=3$ es cierto porque $\frac{1}{|A_1|}\geq\frac{1}{|A_1\cup A_2|}$, $\frac{1}{|A_2|}\geq\frac{1}{|A_2\cup A_3|}$, $\frac{1}{|A_3|}\geq\frac{1}{|A_3\cup A_1|}$, y $\frac{1}{|A_1\cup A_2\cup A_3|}>0$.

Pero para $n=4$ este razonamiento deja de mantener.

6voto

jlleblanc Puntos 2957

Aquí está una analítica de la prueba inspirado por el uno en la respuesta a la pregunta #1343375 (gracias a kubek789 por el enlace!).

Podemos arreglar un entero positivo $n$. Dejamos $\left[ n\right] $ denota el conjunto $\left\{ 1,2,\ldots,n\right\} $.

Primero mostramos un auxiliar resultado:

Teorema 1. Deje $A_{1},A_{2},\ldots,A_{n}$ $n$ finito no vacío de conjuntos. Vamos $x\in\left( 0,1\right) $. A continuación,

$0<\sum\limits_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }<1$.

La prueba del Teorema 1. Deje $A$ el conjunto $A_{1}\cup A_{2}\cup\cdots\copa A_{n} $. Let $X$ be the set of all maps $\rightarrow\left\{ 0,1\right\} $. Nosotros hacer $X$ en un espacio de probabilidad mediante la asignación de un mapa de $f:A\rightarrow \left\{ 0,1\right\} $ the probability $x^{\left\vert f^{-1}\left( 1\right) \right\vert }\left( 1-x\right) ^{\left\vert f^{-1}\left( 0\right) \right\vert }$. This probability space $X$ is precisely the $\left\vert Un\right\vert $-th Cartesian power of the probability space $\left\{ 0,1\right\} $ where $1$ has probability $x$ and $0$ has probability $1-x$. En términos más simples, muestreo al azar un punto en $X$ es equivalente a la construcción de un mapa de $A\rightarrow\left\{ 0,1\right\} $ por voltear un $x$-moneda por cada $a\in A$ (de forma independiente), y dejar que el mapa de $\rightarrow\left\{ 0,1\right\} $ send $un$ to $1$ if the $x$-coin has brought up heads and to $0$ si ha traído hasta la cola. Aquí, un "$x$-moneda" significa una visión sesgada de la moneda que lleva hasta la cabeza con probabilidad de $x$.

Ahora, vamos a $Y\subseteq X$ ser el conjunto de todos los mapas de $f:A\rightarrow\left\{ 0,1\right\} $ such that every $i\en\left\{ 1,2,\ldots,n\right\} $ satisface $0\in f\left( A_{i}\right) $. A continuación, $Y$ es el conjunto de todos los mapas $f:A\rightarrow\left\{ 0,1\right\} $ son tales que no $i\in\left\{ 1,2,\ldots,n\right\} $ satisfies $A_{i}\subseteq f^{-1}\left( 1\right) $. Por lo tanto, la probabilidad de $Y$ (como un evento en el que la probabilidad de espacio $X$) puede ser calculado por el principio de inclusión y exclusión en $\sum\límites _{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$. Pero esta probabilidad es $>0$ (desde el "constante-$0$" mapa pertenece a $Y$ y tiene un valor distinto de cero probabilidad) y $<1$ (desde el "constante-$1$" mapa no pertenecen a $Y$, y todavía tiene distinto de cero probabilidad). Por lo tanto, el Teorema 1 de la siguiente manera.

(Por favor, corrija todos los estocásticos de la terminología que he masacrado. No he utiliza probabilidad de espacios desde que pasé la probabilidad de 101 a unos 9 años).

Teorema 2. Deje $A_{1},A_{2},\ldots,A_{n}$ $n$ finito no vacío de conjuntos. Vamos $x\in\left( 0,1\right) $. A continuación,

$\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0$.

La prueba del Teorema 2. Teorema 1 se muestra que todos los $x\in\left( 0,1\right) $ satisface

$1>\sum\limits_{I\subseteq\left[ n\right] }\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$

$=1+\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert }x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }$ (here, we have split the $I=\varnothing$ término de la suma)

$=1-\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }$.

En otras palabras, todos los $x\in\left( 0,1\right) $ satisface

$\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}x^{\left\vert \bigcup_{i\in I} A_{i}\right\vert }>0$.

Se denota el lado izquierdo de esta desigualdad por $f\left( x\right) $. Entonces, por lo tanto, han demostrado que todos los $x\in\left( 0,1\right) $ satisface $f\left( x\right) >0$. Por lo tanto, $\int_{0}^{1}\dfrac{f\left( x\right) } {x}dx>0$. But the definition of $f$ (and the rule that $\int_{0}^{1} \dfrac{x^{m}}{x}dx=\dfrac{1}{m}$ for every $m\geq1$) yields $\int_{0} ^{1}\dfrac{f\left( x\right) }{x}dx=\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }$. Por lo tanto, $\sum\limits_{\substack{I\subseteq\left[ n\right] ;\\I\neq\varnothing}}\left( -1\right) ^{\left\vert I\right\vert -1}\dfrac{1}{\left\vert \bigcup_{i\in I}A_{i}\right\vert }>0$, y el Teorema 2 es probada.

0voto

mjqxxxx Puntos 22955

No entiendo su justificación de por qué esto es cierto incluso para $n=2$ (con más fuerza, creo que es falso). Es sin duda el caso de que $\left|A_1\right|^{-1} \ge \left|A_1 \cup A_2\right|^{-1}$, pero hay más términos en la suma de los pares de conjuntos que en la suma sobre los conjuntos, por lo que la comparación de términos individuales no garantiza nada sobre el signo del resultado. Por ejemplo, vamos a $A_1=\{1,2,3\}$, $A_2=\{1,2,4\}$, $A_3=\{1,3,4\}$, y $A_4=\{2,3,4\}$. A continuación, todos los $\left|A_i\right|=3$, y cada una de las $\left|A_i\cup A_j\right|=4$, por lo que $$ \sum_{i=1}^{4}\frac{1}{\left|A_i\right|} - \sum_{1\le i<j\le 4}\frac{1}{\left|A_i\copa A_j\right|}=4\times\frac{1}{3}-6\times\frac{1}{4}=-\frac{1}{6} < 0.$$ Me estoy perdiendo algo?

0voto

bburGsamohT Puntos 2820

Aquí es un comentario extendido:

Parece verdad para $n$ impar, por razones similares a las proporcionadas en el $n=3$ de los casos. Para ver esto, debemos considerar en primer lugar la primera $n-1$ sumandos y suma par $i$, $1\leq i<n/2$, con suma $n-i$. Tenga en cuenta que hay un número igual de los términos de estos pares, como $$ \binom{n}{i}=\binom{n}{n-i} $$ Ahora tenemos el par de elementos de cada suma. Es decir, tenemos que encontrar un bijection tomar $\{A_{j_1},\dots,A_{j_i}\}$ a un superconjunto $\{A_{k_1},\dots,A_{k_{n-i}}\}$. Si podemos hacer esto, entonces sabemos $$ \left|\cup_i A_{j_i}\right|\leq \left|\cup_i A_{k_i}\right|,\text{ o }\;\frac{1}{\left|\cup_i A_{j_i}\right|}\geq\frac{1}{\left|\cup_i A_{k_i}\right|} $$ y a partir de esta vinculación, se desprende que la $i$th suma menos el $(n-i)$th suma es no negativa. La adición en la final $n$th plazo, lo cual es positivo, se asegurará de que la suma total es positivo.

(Esperemos que el argumento anterior tiene sentido. Si no, siéntase libre de dejar un comentario y os puede ampliar, por ahora voy a pasar.)

Así que ahora basta con encontrar un bijection. Que desgraciadamente estoy teniendo problemas con rigor de mostrar que no hay uno, sino de forma heurística parece que debe ser un mapa. Espero que ayude un poco, y voy a seguir pensando en ello y ver si puedo terminarlo.

0voto

Markus Scheuer Puntos 16133

Nota: Un comentario además de la bonita respuesta de @darijgrinberg.

Él se refiere a una muy elegante respuesta por @zeraouliarafik con respecto a la fuertemente relacionada con la desigualdad pregunta:

Deje $x_1,\ldots,x_n> 0$. ¿La siguiente desigualdad? \begin{align*} \sum_{i=1}^n\frac{1}{x_i}-\sum_{i<j}\frac{1}{x_i+x_j}+\sum_{i<j<k}\frac{1}{x_i+x_j+x_k}-\cdots +(-1)^{n-1 }\frac{1}{x_1+\ldots+x_n}>0 \qquad\qquad \tag{1} \end{align*}

Observar, que el OPs pregunta es una generalización de (1). En los siguientes se consideran dos casos extremos:

Caso 1: Conjuntos de $A_1,\ldots,A_n$ la formación de una partición

Vamos a asumir que los conjuntos de $A_i, 1\leq i \leq n$ forma una partición de un conjunto $X\neq \emptyset$.

A continuación, OPs, la desigualdad se convierte en \begin{align*} \sum_{i=1}^n&\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}\\ &=\sum_{i=1}^n\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i|+|A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i|+|A_j|+|A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1|+\ldots+|A_n|} > 0\tag{2}\\ \end{align*} que es exactamente (1) y ya ha sido probada por @zeraouliarafik en la que se hace referencia MSE desigualdad pregunta.

En el otro lado tenemos el caso extremo de la

Caso 2: conjuntos Idénticos $X=A_1=\ldots=A_n\neq \emptyset$

A continuación, OPs, la desigualdad se convierte en

\begin{align*} \sum_{i=1}^n&\frac{1}{|A_i|}-\sum_{1\leq i<j\leq n}\frac{1}{|A_i\cup A_j|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|A_i\cup A_j\cup A_k|}-\cdots+\frac{(-1)^{n-1}}{|A_1\cup\cdots\cup A_n|}\\ &=\sum_{i=1}^n\frac{1}{|X|}-\sum_{1\leq i<j\leq n}\frac{1}{|X|}+\sum_{1\leq i<j<k\leq n}\frac{1}{|X|}-\cdots+\frac{(-1)^{n-1}}{|X|}\\ &=\frac{1}{|X|}\left(\binom{n}{1}-\binom{n}{2}+\binom{n}{3}-\ldots+(-1)^{n-1}\binom{n}{n}\right)\\ &=\frac{1}{|X|}\left(1-(1-1)^n\right)\\ &=\frac{1}{|X|}>0\tag{3} \end{align*}

Otros valores de $A_1,\ldots,A_n$ entre estos casos extremos dará un resultado entre los valores de (2) y (3).

Pregunta: parece OPs expresión podría ser algún tipo de medida de la dispersión de $n$ subconjuntos con $X=\bigcup_{i=1}^nA_i$. Tal vez alguien podría señalar la información relacionada?

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X