I got this question in an online contest today (which is now over).
Anna writes a sequence of positive integers $(a_1, a_2, · · · , a_n)$, such that
$$a_1 + a_2 + · · · + a_n = 2023$$
Suppose the sequence Anna picks is equally likely to be any sequence satisfying the above condition. Find the expected value of $n$. Note: The expected value of $n$ is the average value of $n$ across all possibilities.
My attempt:
I found that the given equation has $\binom{2022}{n-1}$ solutions for a fixed $n$. My line of reasoning (which you may skip if you are familiar with stars and bars):
In general, it can be combinatorialy shown that $x_1+x_2+\ldots+x_r=n$ has ${}^{n-1}\textrm C_{r-1}$ positive integer solutions for given $n$ and $r$.
It's like we have to partition $n$ consecutive dots into $r$ parts such that each part has at least $1$ dot.
$\overbrace{\begin{array}{c|c|c|}\hline \underbrace{\cdots}_{x_1} & \underbrace{\cdots}_{x_2} & \underbrace{\cdots}_{x_3} \\ \hline\end{array}\cdots\begin{array}{|c|c}\hline \underbrace{\cdots}_{x_{r-1}} & \underbrace{\cdots}_{x_r} \\ \hline\end{array}}^n\tag*{}$
We need $r-1$ pipes (i.e., $|$) to make $r$ partitions. Out of $n$ dots, we need to distribute one each to $r$ parts. So we are left with $n-r$ dots which can be distributed freely. The number of ways in which we can permutate $r-1$ pipes and $n-r$ dots is: $\dfrac{(n-r+r-1)!}{(n-r)!\cdot(r-1)!}={}^{n-1}\textrm C_{r-1}\tag*{}$
We can vary $n$ from $1$ to $2023$ so the number of possible sequences of positive integers which sum to $2023$ is given by $$\sum_{n=1}^{2023}\binom{2022}{n-1}=2^{2022}$$
The probability that the chosen sequence is of length $r$ is given by $$P(n=r)=\frac{1}{2^{2022}}\binom{2022}{r-1}$$
Thus, the expected value of $n$ is $\sum_{r=1}^{2023}r\cdot P(n=r)$.
Is my assessment correct?
Also, how to arrive at the $2^{2022}$ i.e., the number of possible sequences of any length combinatorically?
Best Answer
Indeed your idea of using pipes in the attempt is more useful than what you might think. Since there are $2022$ possible positions for you to put the pipe, and each gives a different configurations, hence it's actually $2022$ binary choices. (as what lulu has mentioned) So there are $2^{2022}$ partitions, and the expected value of $n$ is $1+2022(0.5)=1012$. (Adding a pipe adds $1$ to $n$)