What is the number of subsets of $\{1, ..., n\}$ which sum to a given number $k \leq \frac{n(n+1)}{2}$?

Question

I'm trying to compute the number of ways to sum the first $n$ unique positive integers to a number $k$. This is not a partition of $n$ since we can't repeat numbers.

Any hints on how I can derive a generating function for this?

I encountered this in trying to compute the variance of the sum of $k$ balls randomly drawn from an urn of $n$ balls (where each ball is labeled with a unique positive integer from $1...n$). Letting $S$ be the random variable which is this sum, computing the variance using the definition of expectation directly uses $P(S = k) = \frac{N_{n,k}}{{n\choose k}}$, where $N_{n,k}$ denotes the desired quantity above. I can compute the variance by writing $S$ as a sum of indicators and expanding the expression inside of the expectation, but I was wondering if there was a nice expression for the above quantity.

Thank you!

Answer 1

Edit: this answer was written for a previous version of the question, which asked how to compute the variance.

---

The distribution is not needed to compute the variance. Let $X_i \in {1,2 \cdots n}$, for $i\in {1,2 \cdots k}$, be the result of the $i-$th extraction. CLearly $X_i$ are identically distributed, but not independent.

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

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

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

For the last term you can use $E[X_1 X_2]=E[X_1E[X_2 \mid X_1]]$

Can you go on from here?

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

At least it sounds consistent : $Var(n,n)=0$,$Var(n,1)=Var(X_1)$ and $Var(n,k)\to k n^2/12 $ for $n\gg k$

---

Edit: here goes some detail.

$$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

With regards to the number of subsets, the answer to the question is the number of solutions for $$1\cdot x_1+2\cdot x_2+3\cdot x_3+...+n\cdot x_n =k$$ where $x_i \in \{0,1\}$. It's generating function is $$P_n(x)=(1+x)(1+x^2)(1+x^3)...(1+x^n)$$ and the coefficient of $x^k$ is the answer $N_{n,k}$ (more reading here). It can be computed from $$N_{n,k}=\frac{P_n^{(k)}(0)}{k!} \tag{1}$$ or, given $P_n(x)=P_{n-1}(x)(1+x^n)$, using recurrence: $$N_{n,k}=N_{n-1,k}+N_{n-1,k-n} \tag{2}$$ where $N_{n,0}=1$ and $N_{n,k}=0, k >\frac{n(n+1)}{2}$, $\forall n\in\mathbb{N}$. According to the same article, this is NP-complete problem.