What's The Probability?

Observe that the expression $0 \times p_0 + 1\times p_1 + 2 \times p_2 + \cdots n \times p_n$ is actually asking for the expected value of a term.

For each equation, suppose that we have a solution $A_1 + A_2 + \cdots + A_k = n$ , it is clear that the expected value of each term is simply $\frac { \sum a_i }{ \sum 1 } = \frac{n}{k} .$ This tells us that $E[ X | a_1=A_1, a_2=A_2, \ldots, a_k = A_k] = \frac{n}{k} .$

Now, we apply the law of iterated expectation , which tells us that

$E[X] = \sum E[X | P_i ] \times P ( P_i )$

Letting $P_i$ be the individual events of each solution set $\{ A_1, A_2, \ldots A_k \}$ , we get that $E[X] = \sum E[X | P_i ] \times P(P_i)$ . Since each of the $E[X|P_i]$ values are equal to $\frac{n}{k}$ , hence we conclude that

$E[X] = \sum \frac{n}{k} \times P ( P _ i ) = \frac{n}{k} \sum P(P_1) = \frac{n}{k} \times 1$

Thus, the answer to the question is $\frac{n}{k}$ .

---

Note: This solution is independent of which specific sets of equations we have to use (e.g. do we allow repeated terms, do we count permutations as distinct solution sets, etc).
In fact, it is also independent of the types of integers that we're allowed to have. In particular, the answer is the same for positive integers or the positive odd integers! All that it uses is $\sum P(P_i) = 1$ , so we just need to ensure that there exists non-zero but finitely many solutions to the equation, for the uniform distribution selection to make sense.

The key to this is that there is nothing special about the integer $j$ . We are being asked for the expected value $\mathbb{E}[a_j]$ of the $j$ th integer. The symmetry of the problem makes it clear that $\mathbb{E}[a_1] = \mathbb{E}[a_2]= \cdots = \mathbb{E}[a_k]$ and so, since $a_1 + a_2 +\cdots + a_k = n$ , it is clear that each expectation is equal to $\tfrac{n}{k}$ .

Here is a simpler solution that uses only an elementary counting argument. List the set of all solutions of the equations in a particular order. Assume that there is a total of $N$ solutions and the integer $i$ appears in the $j$ th solution $N_{ij}$ times. Then, we have $\sum_{i=0}^{n} iN_{ij}=n, \hspace{10pt} \forall j=1,2, \ldots N, \hspace{10pt} (1)$ Note that, there is a total of $Nk$ coordinates (i.e., $a_i$ 's). Fraction of the coordinates in which the integer $i$ appears is $p_i = \frac{1}{Nk}\sum_{j=1}^{N} N_{ij}$ Hence, $\sum_{i=0}^{n} ip_i\stackrel{(a)}{=} \frac{1}{Nk} \big(\sum_{j=1}^{N} \sum_{i=0}^{n} iN_{ij}\big) \stackrel{(b)}{=} \frac{Nn}{Nk}= \frac{n}{k},$ where in (a), we have interchanged the order of summation and in (b), we have used the equation (1).