2
$\begingroup$

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,

  • 0
    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?2012-04-09

3 Answers 3

1

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

0

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

0

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?