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

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!

• Now I know what you are asking. – Laz Oct 4 '18 at 20:37
• @Laz Ok! Just a hint to point me in the right direction would be appreciated :) – TheProofisTrivium Oct 4 '18 at 20:38
• I believe this math.stackexchange.com/questions/421909/… is asking the same thing, but I'm not sure how the asker came up with that GF. – TheProofisTrivium Oct 4 '18 at 20:42
• You can try to use some kind of induction to construct a formula, using something like this. If you have a formula for any $k\leq m$, then any subset $S_{m+1}$ whose sum is $m+1$ can be partitioned into two subsets, the subset ${1}$ (if $1\in S_{m+1}$) and a subset $S_m$ whose sum is $m$. Of course, you have to garantee that $1\notin S_m$. If $1\notin S_{m+1}$, now you try with $2$, and so on ... In how many ways can you do that? I don't know if it'll work, but you can twist that idea as much as you want. – Laz Oct 4 '18 at 21:01
• 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 $$(1+x)(1+x^2)(1+x^3)...(1+x^n)$$ and the coefficient of $x^k$ is the answer. But this doesn't make the problem easier. – rtybase Oct 4 '18 at 21:02

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

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.