What is the distribution of all sums of numbers from the set $\{1,2,\cdots,n\}$?

Question

I was wodering: if you have the set of integers $R = \{1, 2, \cdots , n\}$, I would like to know the distribution of the sum of the members of all the posible non-empty subsets. I have done a simple calculation for some values of $n$ and here you can see at the bottom the distribution, which resembles a lot to a gaussian or binomial distribution. My intuition says that binomial coefficient must be involved, but with some modification. Can you please help me with this problem? Seems to be more innocent that it is.

Many thanks in advance!

Answer 1

Rather than getting a closed formula for the number of sums, I'll show that the distribution tends to a Gaussian.

Choosing a sum uniformly at random is the same as examining the random variable $$Y_n = 1 \cdot X_1 + 2 \cdot X_2 +\cdots + n \cdot X_n$$

where the variables $X_j$ are iid with $P[X_1 = 0] = P[X_1 = 1] = 1/2$. In your case you're looking at non-empty sums, so we should technically condition on not having $X_1 = X_2 = ... = X_n = 0$, but this set has exponentially small probability, and thus we can ignore it.

If we recenter and rescale, we will have $$\frac{Y_n - \mathbb{E}[Y_n]}{\sqrt{\operatorname{Var}[Y_n]}} \xrightarrow{d} \mathcal{N}(0,1)$$ as $n \to \infty$ by the Lindeberg Central Limit Theorem.

Answer 2

Let's put $$ N(s,n) $$ to be the number of occurrence of the sum $s$ among all the non-empty subsets taken from $\{ 1,2, \cdots, n\}$

Then, concerning the sum of the subsets of $\{1,2,\cdots,n,n+1\}$ we will have that $$ N(s,n + 1) = N(s,n) + N(s - n - 1,n) + \left[ {s = n + 1} \right] $$ because
- not involving $n+1$, we will have the same subsets and thus the same sums as from $\{1,\cdots,n\}$;
- the subsets obtained from a previous subset adding $n+1$, will sum to $s$ if previously was summimg to $s-(n+1)$;
- the unique subset containing $n+1$ will sum to $s$ if $s=n+1$: $\left[ {s = n + 1} \right]$ indicates the Iverson bracket.

As starting conditions we have $$ \left\{ \matrix{ N(s,n) = 0\quad \left| {\;n < 1\; \vee \;s < 1} \right. \hfill \cr N(s,1) = \left[ {s = 1} \right] \hfill \cr} \right. $$ and we can compactly write the recurrence as $$ \bbox[lightyellow] { N(s,n) = N(s,n - 1) + N(s - n,n - 1) + \left[ {s = n} \right]\quad \left| \matrix{ \;1 \le n \hfill \cr \;1 \le s\left( { \le \left( \matrix{ n + 1 \cr 2 \cr} \right)} \right) \hfill \cr} \right. }\tag{1}$$

This gives an o.g.f. in $s$ as $$ \bbox[lightyellow] { \eqalign{ & 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 & = 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} }\tag{2}$$

But that in $n$ or the double o.g.f. are of no practical use.

However from (2) we can obtain a closed form for $F(x,n)$ $$ \eqalign{ & 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 & G(x,n) = \left( {1 + x^{\,n} } \right)G(x,n - 1) \cr & G(x,n) = \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)} \cr} $$ i.e. $$ \bbox[lightyellow] { F(x,n) = \prod\limits_{k = 1}^n {\left( {1 + x^{\,k} } \right)} - 1 }\tag{3}$$ which matches the initial condition $F(x,1)=x$.

This gives in fact that

$N(s,n)$ is the number of partitions of $s$ into distinct parts, no greater than $n$.