¿Cuál es el número de subconjuntos de $\{1, ..., n\}$ que suman un número determinado $k \leq \frac{n(n+1)}{2}$ ?

Question

Intento calcular el número de formas de sumar la primera $n$ enteros positivos únicos a un número $k$ . Esto no es una partición de $n$ ya que no podemos repetir los números.

¿Alguna pista sobre cómo puedo derivar una función generadora para esto?

Me encontré con esto al intentar calcular la varianza de la suma de $k$ bolas extraídas al azar de una urna de $n$ bolas (donde cada bola está etiquetada con un único número entero positivo de $1...n$ ). Dejando $S$ sea la variable aleatoria que es esta suma, el cálculo de la varianza mediante la definición de la expectativa utiliza directamente $P(S = k) = \frac{N_{n,k}}{{n\choose k}}$ , donde $N_{n,k}$ denota la cantidad deseada arriba. Puedo calcular la varianza escribiendo $S$ como una suma de indicadores y expandiendo la expresión dentro de la expectativa, pero me preguntaba si había una expresión agradable para la cantidad anterior.

Gracias.

Answer 1

Edición: esta respuesta fue escrita para una versión anterior de la pregunta, que preguntaba cómo calcular la varianza.

---

La distribución no es necesaria para calcular la varianza. Sea $X_i \in {1,2 \cdots n}$ , para $i\in {1,2 \cdots k}$ sea el resultado de la $i-$ de la extracción. CLearly $X_i$ están idénticamente distribuidos, pero no son independientes.

Dejemos que $S=\sum_{i=1}^k X_i$

Tenemos $E[S]=k E[X_1] = k \frac{n+1}{2}$

Y $E[S^2] = k E[X_1^2 ]+ k(k-1)E[X_1 X_2]$

Para el último término puede utilizar $E[X_1 X_2]=E[X_1E[X_2 \mid X_1]]$

¿Puedes seguir desde aquí?

Tengo $$Var(n,k) = \frac{k\,\left( n+1\right) \,\left( n-k\right) }{12}$$

Al menos suena coherente : $Var(n,n)=0$ , $Var(n,1)=Var(X_1)$ y $Var(n,k)\to k n^2/12 $ para $n\gg k$

---

Edición: aquí van algunos detalles.

$$E[X_1^2 ]=\frac{2{{n}^{2}}+3n+1}{6}$$

$$E[X_1 | X_2 =j] =\frac{1}{n-1}\left( -j + \sum_{i=1}^n i \right)=\frac{1}{2n-2}\left( n^2 +n -2j \right)$$

$$E[X_1 X_2 ] =\frac{1}{2n-2}\left( (n^2+n)E[X] -2 E[X^2] \right)=\frac{3{{n}^{2}}+5n+2}{12}$$

$$E[S^2] = \frac{k\,\left( n+1\right) \,\left( 3kn+n+2k\right) }{12}$$

$$\sigma_S^2(n,k)=E[S^2] -E[S]^2= \frac{k\,\left( n+1\right) \,\left( n-k\right) }{12}$$

Answer 2

Con respecto a la número de subconjuntos la respuesta a la pregunta es el número de soluciones para $$1\cdot x_1+2\cdot x_2+3\cdot x_3+...+n\cdot x_n =k$$ donde $x_i \in \{0,1\}$ . Es función generadora es $$P_n(x)=(1+x)(1+x^2)(1+x^3)...(1+x^n)$$ y el coeficiente de $x^k$ es la respuesta $N_{n,k}$ (más lectura) aquí ). Se puede calcular a partir de $$N_{n,k}=\frac{P_n^{(k)}(0)}{k!} \tag{1}$$ o, dado $P_n(x)=P_{n-1}(x)(1+x^n)$ utilizando la recurrencia: $$N_{n,k}=N_{n-1,k}+N_{n-1,k-n} \tag{2}$$ donde $N_{n,0}=1$ y $N_{n,k}=0, k >\frac{n(n+1)}{2}$ , $\forall n\in\mathbb{N}$ . Según el mismo artículo Este es un problema NP-completo.