# 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,

-
What is the random variable $X$? Is it the number of parts in the composition? –  Michael Hardy Apr 9 '12 at 20:26
I think that you have a typo in the third paragraph. Is $E(X)$ supposed to be the expected value of the first part of a randomly selected composition of $n$? –  Brian M. Scott Apr 9 '12 at 20:34

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 ...

-

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?

-

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 .$

-