Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
    
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

3 Answers 3

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

share|improve this answer

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?

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.