Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $L=\{a_1,a_2,\ldots,a_k\}$ be a random (uniformly chosen) subset of length $k$ of the numbers $\{1,2,\ldots,n\}$. I want to find $E(X)$ where $X$ is the random variable that sums all numbers. We might want that $k < n$ too.

My main problem is that I cannot get the function $q(a,k,n)$ that gives me the number of ways to write the number $a$ as the sum of exactly $k$ distinct addends less or equal $n$. This seems related but it doesn't limit the size of the numbers.

share|cite|improve this question
up vote 5 down vote accepted

The expectation of each of the terms in the sum is $(n+1)/2$ so the expectation is $k(n+1)/2$.

If you want to calculate the function $q(a,k,n)$ then you can use my Java applet here, by choosing "Partitions with distinct terms of:" $a$, "Exact number of terms:"$k$, "Each term no more than:" $n$, and then click on the "Calculate" button. If instead you start with "Compositions with distinct terms of:", then you will get a figure $k!$ times as big.

share|cite|improve this answer
Thanks, I accepted this one because I think your great applet can be useful for me on later tasks too :) – Listing May 7 '11 at 13:49

Hint: (1) Compute $E(a_1)$. (2) Show that $E(a_k)=E(a_1)$ for every $k$. (3) Deduce $E(X)$.

This is a good example where computing the distribution is messy but computing the expectation is easy.

share|cite|improve this answer
Thank you! Too bad I cannot accept two answers as both answers together answer my questions completely :) – Listing May 7 '11 at 13:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.