# Probability distribution of the sum of $N$ values from a set of values numbered $1$ to $K$

I have been trying to figure out how to determine the probability distribution function for the sum of $N$ values taken from a set of $K$ consecutive values (valued $1$ to $K$).

For example, if I choose at random 5 values from a set of 50 for a trial and sum the results, I get a value I'll call $S$. If I do that for a million trials and look at the distribution of $S$, it will be a bell-curved distribution, but I don't know how to calculate the mean, median, standard deviation, etc.

I also understand that:

• There are $\frac{50!}{(50-5)!} = 254,251,200$ permutations.
• The smallest sum is $1+2+3+4+5=15$ and the largest sum is $46+47+48+49+50=240$.

I just can't figure out how to derive a formula to determine how many permutations (or maybe combinations if order doesn't matter?) sum up to a given value $S$ between $15$ and $240$.

-
– vadim123 Jul 6 '13 at 23:18
When you "choose at random 5 values from a set of 50", are you choosing distinct values or allowing for duplicates? I.e., are you sampling with or without replacement? – awkward Jul 7 '13 at 0:55
The values are distinct...like choosing 5 of 50 lottery balls or something, numbered 1 to 50. Forgive me, I think that is called "without replacement". I'm a bit of a novice at statistics. – Mitselplik Jul 7 '13 at 17:08

Since the sum of Gaussian variables is Gaussian, you only need to find two parameters: the mean and the standard deviation. The mean is easy, due to linearity of expectation. Let's call it $\mu$.

The standard deviation is trickier. If $\frac{k}{n}$ is large, you can get an easy approximation by ignoring the fact that the values have to be distinct. In this case, just use the fact that the standard deviation scales like $\sqrt{n}$.

If you need an exact formula, you will have to compute the variance: $$-\mu^2+\sum_{|S|=N}\left(\sum_{x\in S}x\right)^2$$over all sets $S$ containing your elements.

-

So it turns out that the solution to this problem is non-trivial. After further analysis, I've determined that the "distribution" scales to a bell curve that can be obtained by simply counting the sums of all possible permutations of N values from the set of integers from 1 to K.

Facts/Discoveries:

• There are $N(K - N) + 1$ sums.
• The smallest sum $S$min = $\frac N 2$×$($N $+$ 1$)$.
• The largest sum $S$max = $\frac N 2$×$($2K - N + 1$)$.
• Given $S$ ∈ {$S$min, ... , $S$max}, then $count(S) = N!×p(S)$, where $p(S)$ is a strict partitioning function of $S$ such that all summands are unique and ≥ 1.
• Further Research:
Thus far, I have yet to find a straight-forward formula for $p(S)$ (or perhaps $p(S, K, N)$ since the function domain changes with different values of $K$ and $N$).

The question is essentially equivalent to asking "How many ways can a flight of $K$ stairs be climbed, taking at least 1 stair at a time, never repeating the number of stairs previously taken, and moving exactly $N$ times?"

Once I (or perhaps smarter minds than I) have figured out a way to calculate $p(S, K, N)$, then I will need to determine how to scale the "distribution" based on the number of trials. I am not sure that it would be linear.

Assuming anyone else is interested in this problem, I generated the set of counts for $K = 10, N = 5$ below:
{120,120,240,360,600,840,1080,1320,1680,1920,2160,2280,2400,2400,2280,2160,1920,1680,1320, 1080,840,600,360,240,120,120}

Factoring out $5!$ yields:
{1,1,2,3,5,7,9,11,14,16,18,19,20,20,19,18,16,14,11,9,7,5,3,2,1,1}

-