Probabilistic method: what is the probability of the event that randomly selected composition of $n$ Can anyone help me out with the following question?
Q. What is the probability of the event that randomly selected composition of $n$ has a second part and that second part is $1$?
I know that the expected number, $E(X)$ that the first part of a randomly selected composition of $n$ is $2- 1/2^{n-1}$.
This problem is from 'A walk through Combinatorics' by Bona.
Thanks,
 A: Obviously for $n=1$ the probability is $0$. I suggest that you do some experimenting with small values of $n$, say $n=2,3,4$, and $5$. The compositions that meet the requirement are as follows.
$n=2$: $$1+1$$
$n=3$: $$\begin{align*}&1+1+1\\&2+1\end{align*}$$
$n=4$: $$\begin{align*}&1+1+1+1\\&1+1+2\\&2+1+1\\&3+1\end{align*}$$
$n=5$:
$$\begin{align*}
&1+1+1+1+1\\
&1+1+1+2\\
&1+1+2+1\\
&2+1+1+1\\
&1+1+3\\
&3+1+1\\
&2+1+2\\
&4+1
\end{align*}$$
Presumably you know already that there are $2^{n-1}$ compositions of $n$, so with these experimental data you ought to be able to make a good conjecture. And once you’ve made that conjecture, ask yourself why the number of ‘good’ compositions of $n$ is the same as ...
A: Hints: 


*

*How many compositions are there of $n$?  

*How many of these are a single part? 

*If there is a second part and it is 1 then what must the other parts add up to? 

*How many compositions are there of that smaller total? 


Replies:


*

*$2^{n-1}$

*$1$ 

*$n-1$

*$2^{n-2}$


so the probabilities  are $\dfrac{2^{n-1}-1}{2^{n-1}}=1 - \dfrac{1}{2^{n-1}}$ and  $\dfrac{2^{n-2}}{2^{n-1}}=\dfrac12 .$
A: It's sometimes useful to think of a "stars and bars" representation of random compositions. (I don't recall if this is in Bona, but it's in Stanley; if it's not in Bona it's at least there implicitly.) Namely, a random composition can be viewed as a sequence of stars with bars between them; the bars separate the different parts. So  * * * | * * | * | * *, for example, corresponds to the composition 3 + 2 + 1 + 2.
Then a uniformly chosen random composition of $n$ is given by the following procedure:
- draw n stars;
- flip n-1 fair, independent coins to decide whether to put a bar in each of the "gaps" between two stars.
So can you translate the statement about compositions into a statement about the results of a sequence of random coin flips?
