Suppose we have $n$ elements that we want to distribute to people forming a queue, and we want to know the number of different ways we could make the distribution independently of the number of beneficiaries (let us call this number $f(n)$).
If we have one element, we can only distribute it to the first people in the queue, and we are done. Therefore, $f(1)=1$.
If we have two elements, we could (i) give one element to each of the first two people in the queue, or (ii) give two elements to the first people in the queue. Therefore, $f(2)=2$.
If we have three elements, we could (i) give one element to each of the first three people in the queue, (ii) give two elements to the first people in the queue, and one element to the second people in the queue, (iii) give one element to the first people in the queue, and two elements to the second people in the queue, and (iv) give three elements to the first people in the queue. Therefore, $f(3)=4$.
We can already see that a pattern is arising. Indeed, I think I can prove that
Claim
$$f(n) = 2^{n-1}$$
Proof
Let us sort the different ways of distributing by the number of elements that we give to the first people in the queue, from less to more.
Applying induction, the base case $f(1) =2^{1-1}$ holds, and we can assume that it holds for every number of elements less than or equal to $n$.
Let us compute the numbers of ways of distributing $n+1$ elements.
It can be seen that the number of ways of distributing $n+1$ elements such that the first people in the queue receives one element is equal to the number of ways of distributing $n$ elements, but starting at the second people and giving one element to the first people.
Equally, it can be seen that the number of ways of distributing $n+1$ elements such that the first people in the queue receives two elements is equal to the number of ways of distributing $n-1$ elements, but starting at the second people and giving two elements to the first people.
Indeed, this can be seen for every number of ways of distributing $n+1$ elements such that the first people in the queue receives $k$ elements; it will be equal to the number of ways of distributing $n+1-k$ elements, but starting at the second people and giving $k$ elements to the first people.
Therefore, we get that $$f(n+1)=f(n)+f(n-1)+f(n-2)+...+f(1)+1$$
As by the induction hypothesis $f(n)=2^{n-1}$, $f(n-1)=2^{n-2}$, $\dots$ , $f(1)=2^0$, substituting we get that $$f(n+1)=2^{n-1}+2^{n-2}+...+1+1=2^n$$
And we conclude the proof.
Interestingly enough, this "distribution function" $f(n)$ is related to the partition function, as the distribution function counts the number of partitions of a positive integer $n$ but considering that two sums that differ in the order of summands are different partitions. However, this relationship does not help (at least, as I see it) in calculating the partition function $p(n)$, although it is an upper bound for it (a very bad one).
I would like to ask:
(i) Are the problem and the proof correctly stated and exposed? How could the proof be improved?
(ii) I have not been able to find this result anywhere, although I believe it should be known for sure. I have found plenty of results of the type "distributing $n$ elements to $k$ recipients", but not this general "distribution problem" one. Could you please share some reference?
(iii) Am I missing some way to use $f(n)$ in order to calculate / approximate $p(n)$?
Thanks in advance!
Your $f(n)$ is the number of compositions of $n$ (i.e. partitions where the order matters).
Your proof looks correct, but a much easier induction proof is this:
Suppose you have already distributed $n$ items (in one of $f(n)$ ways) and then you suddenly find you have one more item to distribute. You can either give to the last person you already gave something to, or you can give it to the next person in the queue. You always have the choice between exactly these two possibilities. Therefore $f(n+1)=2f(n)$.
The linked wikipedia page gives a different proof without induction.