¿Cuál es la distribución de todas las sumas de números del conjunto$\{1,2,\cdots,n\}$?

Question

Me wodering: si usted tiene el conjunto de números enteros $R = \{1, 2, \cdots , n\}$, me gustaría saber la distribución de la suma de los miembros de todas las posibles no vacía de subconjuntos. He hecho un cálculo simple para algunos valores de $n$ e aquí se puede ver en la parte inferior de la distribución, que se asemeja mucho a una de gauss o distribución binomial. Mi intuición me dice que el coeficiente binomial deben estar involucrados, pero con alguna modificación. Puede usted por favor me ayude con este problema? Parece ser más inocente que es.

Muchas gracias de antemano!

Answer 1

En lugar de conseguir un cerrado fórmula para el número de sumas, te voy a mostrar que la distribución tiende a una Gaussiana.

La elección de una suma uniformemente al azar es el mismo que el examen de la variable aleatoria $$Y_n = 1 \cdot X_1 + 2 \cdot X_2 +\cdots + n \cdot X_n$$

donde las variables $X_j$ son iid con $P[X_1 = 0] = P[X_1 = 1] = 1/2$. En el caso de que usted está buscando no está vacío sumas de dinero, así que debería técnicamente en la condición de no tener $X_1 = X_2 = ... = X_n = 0$, pero este juego tiene exponencialmente la probabilidad pequeña, y por lo tanto podemos pasar por alto.

Si queremos volver a centrar y cambiar la escala, tendremos $$\frac{Y_n - \mathbb{E}[Y_n]}{\sqrt{\operatorname{Var}[Y_n]}} \xrightarrow{d} \mathcal{N}(0,1)$$ como $n \to \infty$ por el Lindeberg Teorema del Límite Central.

Answer 2

Mi respuesta aquí trataremos de ser más accesibles, pero desgraciadamente incompleta, puede editar/volver a este si se me figura algo.

Resulta que este es Gaussiano/normal, y aunque no es una distribución binomial, es de hecho relacionados con los coeficientes binomiales... sorta.

Si ampliamos la expresión: $(1+x)(1+x^2)(1+x^3)(1+x^4) = x^{10} + x^9 + x^8 + 2 x^7 + 2 x^6 + 2 x^5 + 2 x^4 + 2 x^3 + x^2 + x + 1$

Te darás cuenta de los coeficientes de $x^k$ dará el número de maneras de producir el subconjunto suma de $k$! Usted puede probar esto para otros valores de $n$ multiplicando más de estos factores y el patrón se mantiene. (Tenga en cuenta que el último término constante de $1$ cuentas para el subconjunto vacío, así que usted debe incluir en el gráfico para mantener la realmente buena simetría.)

---

¿Por qué sucede esto?

Piense acerca de cómo funciona la distribución aquí. Para el primer factor $1+x$, se elige uno de los términos de $1$ o $x$. Luego para el segundo factor de $1+x^2$, podemos elegir cualquiera de las $1$ o $x^2$. Continuar hasta que la hemos elegido un término en cada factor, y los multiplicamos. Esto nos da uno de los términos de la plena expansión. Usted puede notar que $x^5$ se puede realizar de dos maneras: $$x^5 = x \cdot 1 \cdot 1 \cdot x^4 = 1 \cdot x^2 \cdot x^3 \cdot 1$$ Esto corresponde a los dos subconjuntos que pueden producir una suma de $5$: $\{1,4\}$ e $\{2,3\}$. Si tomamos el poder de $x$, estamos eligiendo el elemento de su exponente. Si decidimos elegir la $1$ en lugar de eso, estamos optando por no elegir ese elemento. Desde allí se $2$ maneras para formar una suma de $5$, el coeficiente delante de $x^5$ es $2$.

---

Esta fórmula que produce un polinomio (de potencia de la serie) en el que los coeficientes son los términos de nuestra secuencia es llamada generación de la función, y estos son muy poderosas en ser capaz de calcular estos tipos de secuencias, ya sea como una manipulación algebraica o mediante el uso de un sistema algebraico por computadora para calcular estas para grandes valores de $n$.

De tal manera, estos están relacionados con los coeficientes binomiales en que estamos multiplicando $n$ binomios juntos y los coeficientes del producto, es la secuencia de los términos que estamos buscando. Pero estos no son los coeficientes binomiales de la forma $\binom{n}{k}$, esto es completamente distinta a la de la secuencia.

Para probar que esto es Gaussiano, sin embargo, usted puede necesitar el uso de algunos cálculos y conceptos que involucran variables aleatorias, pero en cualquier propiedad de distribución Gausiana es compartida también por esta distribución para suficientemente grande $n$. Por ejemplo, Gauss distribuciones son simétricas, como es este. Cualquier subconjunto que elegimos para formar una suma que corresponde al complemento de un subconjunto que forma la simétrica de la suma en el otro lado.

---

Extra: Suponiendo que esto es Gaussiano sin embargo, conduce a una idea interesante. Considere el siguiente caso de Teorema del Binomio, que sabemos que se aproxima a una distribución Gaussiana para suficientemente grande $n$: $$ (1+x)^n = \sum_{k=0}^{n} \binom{n}{k}x^k $$ Deje $x=1$ y usted encontrará que $$ 2^n = \sum_{k=0}^{n} \binom{n}{k} $$ Esto se extiende a la suma de $2^n$ a través de una distribución normal con dominio de tamaño $n+1$.

Si se aplica la misma idea con nuestra generación de función aquí: (Deje $a_k^n$ el número de maneras de obtener una suma $k$ a partir de un subconjunto de a$[n]$.) $$ \prod_{k=0}^{n}(1+x^k) = \sum_{k=0}^{\frac{n(n+1)}{2}} a_k^n x^k $$ Deje $x=1$ y usted encontrará que $$ 2^n = \sum_{k=0}^{\frac{n(n+1)}{2}} a_k^n $$ desde $\frac{n(n+1)}{2}$ es el más alto posible de la suma. Esto se extiende exactamente el mismo $2^n$ suma de una distribución normal con dominio de tamaño $\frac{n(n+1)}{2}$.

Answer 3

Vamos a poner $$ N(s,n) $$ el número de ocurrencia de la suma de $s$ entre todos los no vacía de subconjuntos de tomado de $\{ 1,2, \cdots, n\}$

Entonces, respecto de la suma de subconjuntos de a$\{1,2,\cdots,n,n+1\}$ tendremos que $$ N(s,n + 1) = N(s,n) + N(s - n - 1,n) + \left[ {s = n + 1} \right] $$ porque
- que no impliquen $n+1$, vamos a tener la misma subconjuntos y por lo tanto el mismo sumas de dinero como de $\{1,\cdots,n\}$;
- los subconjuntos obtenidos a partir de un subconjunto anterior añadiendo $n+1$, se suma a $s$ si previamente se summimg a $s-(n+1)$;
- el único subconjunto que contiene $n+1$ se suma a $s$ si $s=n+1$: $\left[ {s = n + 1} \right]$ indica la Iverson soporte.

Como condiciones de partida que hemos $$ \left\{ \matriz{ N(s,n) = 0\quad \left| {\;n < 1\; \v \;s < 1} \right. \hfill \cr N(s,1) = \left[ {s = 1} \right] \hfill \cr} \right. $$ y podemos escribir de forma compacta la recurrencia como $$ \bbox[lightyellow] { N(s,n) = N(s,n - 1) + N(s - n,n - 1) + \left[ {s = n} \right]\quad \left| \matriz{ \;1 \le n \hfill \cr \;1 \le s\left( { \le \left( \matriz{ n + 1 \cr 2 \cr} \right)} \right) \hfill \cr} \right. }\etiqueta{1}$$

Esto le da una junta.g.f. en $s$como $$ \bbox[lightyellow] { \eqalign{ Y F(x,n) = \sum\limits_{1\, \le \,s} {N(s,n)\,x^{\,s} } = \cr & = \sum\limits_{1\, \le \,s} {N(s,n - 1)\,x^{\,s} } + \sum\limits_{1\, \le \,s} {N(s - n,n - 1)\,x^{\,s} } + \sum\limits_{1\, \le \,s} {\left[ {s = n} \right]\,x^{\,s} } = \cr Y = F(x,n - 1) + x^{\n} \sum\limits_{1\, \le \,s - n} {N(s - n,n - 1)\,x^{\,s - n} } + x^{\n} = \cr & = \left( {1 + x^{\n} } \right)F(x,n - 1) + x^{\n} \cr} }\etiqueta{2}$$

Pero que en $n$ o el doble de o.g.f. son de uso práctico.

Sin embargo a partir de (2) se puede obtener una forma cerrada para $F(x,n)$ $$ \eqalign{ Y F(x,n) - F(x,n - 1) = x^{\n} \left( {F(x,n - 1) + 1} \right) \cr & \left( {F(x,n) + 1 - \left( {F(x,n - 1) + 1} \right)} \right) = x^{\n} \left( {F(x,n - 1) + 1} \right) \cr Y G(x,n) = \left( {1 + x^{\n} } \right)G(x,n - 1) \cr Y G(x,n) = \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)} \cr} $$ es decir, $$ \bbox[lightyellow] { F(x,n) = \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)} - 1 }\etiqueta{3}$$ que coincide con la condición inicial $F(x,1)=x$.

Esto le da en el hecho de que

$N(s,n)$ es el número de particiones de $s$ en partes distintas, no mayor que $n$.