Homework 1, Problem 4

I think I’m confused about what this question is asking. Can someone rephrase it for me? I can’t tell if it’s a single question or two questions, where the first is simply, “how many compositions of $n$ are there?”

1. I’m having my doubts about this question as well. But I think its just a single question, since, if there were two separate ones, then … the first one would be “how many compositions of n are?” but then what would the second question be?

I’m taking it like this. Take an $n$, say $n = 5$. Now take a composition of $5$$3+2$. For each component in the composition (in this case, for 3 and for 2) take a composition. In my example, I’ll take … $1+2$ and $1+1$. You end up then with these two compositions $(1+2,1+1)$ and thats one of the items you could have gotten. But you could have also taken the initial composition $2+2+1$ and then taken the compositions $(1+1,2,1)$ and that would be another possible item of the items you (we) are trying to count. Any thoughts? Does it even make sense?

• What Santiago said is correct.

2. Dear Santiago, that’s exactly the way i counted it (vectors of vectors), and the result is something nice enough, so go ahead! 🙂

3. Thanks! It’s clear to me now what it’s asking for.

4. ale7bravo

There is something I still don’t get. In the composition does the order matters? and, if I’m taking a composition, for example, of 5 does 5 counts as one? and so (5,0) is an item to count?

The order does matter and n is a composition of n.

For example:
n=3, then the compositions are:
1+1+1
1+2
2+1
3

• Adding to what Juan Camilo said, if you are taking n=3, the whole set of thinks you want to count looks like this:
For 1+1+1: (1,1,1)
For 1+2 : (1,2),(1,1+1)
For 2+1 : (2,1),(1+1,1)
For 3 : (3), (1+2),(2+1),(1+1+1)

That means, take one composition. For each component of such composition, choose another composition. Do that for all compositions. If I am not wrong, the count for n=3 should be $9$, the number of “vectors” I was able to make. Notice that you will never get any zeros. So (3) counts, but (3,0) does not.

5. Are these compositions of compositions the same: $(1+1,2,1)$, $(1,1+2,1)$?

• Those two are considered to be different.