Choose a composition from the previous composition Problem:In how many ways can one choose a composition $ \alpha $ of n, and then choose a composition of each part of $ \alpha $?
My attempt:

Consider the dot-and-bar argument on a row.
  Let the final result be the composition $ \beta $ of n. Suppose $ \beta $ has k parts. Then, there are $2^k$ ways to group all the parts to form a row, which is forming a composition of k.

And then I don't know how to connect $ \alpha $ and $ \beta $...
 A: HINT: This is an expansion of Michael Lugo’s hint in the comments. Suppose that you use start with $n$ dots and use some number of copies of $|_1$ to split these dots into the composition $\alpha$ of $n$. Then you use copies of $|_2$ to break each block of $\alpha$ into a composition. (Note that you need not break up a given block: if one block of $\alpha$ has $k$ dots, and you insert no copies of $|_2$ into this block you’re simply using the one-part composition $k$ of that block.) You end up with a string of $n$ dots, some number of copies of $|_1$, and some number of copies of $|_2$. With a bit of thought you can see that there are only two limitation on these strings: the first and last symbols must be dots, and you cannot have two adjacent bars, either of the same or of different types. Here’s one way to reason your way from here to the answer:


*

*In how many ways can you choose positions for the bars, ignoring the distinction between bars of type $|_1$ and bars of type $|_2$?  

*If you’ve chosen $k$ positions for the bars, in how many ways can you split these positions between types $|_1$ and $|_2$?  

*Combine the two answers above to express the answer to the question as a summation; then use the binomial theorem to find a closed form for this summation.


And here’s another:


*

*When all of the bars of both types have been inserted, each of the $n-1$ gaps between adjacent dots will contain one of how many different possibilities?  

*These possibilities can be determined independently for each gap, so altogether how many different ways are there to determine them? 


Each of those ways corresponds to a unique choice of $\alpha$ and compositions of the parts of $\alpha$, and choice of $\alpha$ and compositions of the parts of $\alpha$ corresponds to a unique choice of possibilities for the $n-1$ gaps between dots, so the answer to the second question is also the answer to the original question.
