1. ## Composition problem

Let c(n) be the number of ways of writing n as a sum, where order matters. So we have

3 = 3, 3 = 1 + 2, 3 = 2 + 1, 3 = 1 + 1 + 1

thus c(3) = 4.

According to the author it is "easily verified" that

$\displaystyle \sum_{n=1}^\infty c(n) x^n = \sum_{m=1}^\infty (x + x^2 + x^3 + ...)^m$

Could someone please tell me how to easily verify this, because I have no idea!

2. Hello, Stonehambey!

Let c(n) be the number of ways of writing n as a sum, where order matters.

So we have: .3 = 3, 3 = 1 + 2, 3 = 2 + 1, 3 = 1 + 1 + 1

Thus: c(3) = 4.

I don't understand that equation.
Both sums diverge to infinity.

$\text{We can determine }c(n)\text{ like this . . .}$

We have a board which is $\displaystyle \,n$ units long.

. . . . . $\square\!\square\! \square\!\square \cdots \square\!\square$

There are $\displaystyle \,n-1$ places where the board can be cut.

For each place, there are two choices: cut or not cut.

$\text{Therefore, there are: }\,2^{n-1}\text{ possible partitions of the board.}$

3. Originally Posted by Soroban
Hello, Stonehambey!

I don't understand that equation.
Both sums diverge to infinity.

$\text{We can determine }c(n)\text{ like this . . .}$

We have a board which is $\displaystyle \,n$ units long.

. . . . . $\square\!\square\! \square\!\square \cdots \square\!\square$

There are $\displaystyle \,n-1$ places where the board can be cut.

For each place, there are two choices: cut or not cut.

$\text{Therefore, there are: }\,2^{n-1}\text{ possible partitions of the board.}$

I think it's a little more complicated than that... (many such "cuts" leave us with identical collections of boards)
Partition (number theory) - Wikipedia, the free encyclopedia

Also, @Stoneham: there is a section on the wikipedia page just for you! "generating function" (or something like that)

4. He's right for compositions; c(n) = 2^{n-1}. Partitions, which you linked to, are less trivial as you say.

The book I took this from was An Introduction to the Theory of Numbers by Leo Moser; it can be freely downloaded at trillia.com

5. Originally Posted by Stonehambey
He's right for compositions; c(n) = 2^{n-1}. Partitions, which you linked to, are less trivial as you say.

The book I took this from was An Introduction to the Theory of Numbers by Leo Moser; it can be freely downloaded at trillia.com
Key words: "where order matters". Hah!
That's what I get for trying to post from my phone...while driving

6. Originally Posted by Stonehambey
Let c(n) be the number of ways of writing n as a sum, where order matters. So we have

3 = 3, 3 = 1 + 2, 3 = 2 + 1, 3 = 1 + 1 + 1

thus c(3) = 4.

According to the author it is "easily verified" that

$\displaystyle \sum_{n=1}^\infty c(n) x^n = \sum_{m=1}^\infty (x + x^2 + x^3 + ...)^m$

Could someone please tell me how to easily verify this, because I have no idea!
Is...

(1)

... but is also...

(2)

... and the series (1) and (2) for |x|<.5 both converge to the same value...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

7. Originally Posted by chisigma
Is...

(1)

... but is also...

(2)

... and the series (1) and (2) for |x|<.5 both converge to the same value...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
Yeah, the algebra is similar to the authors'. The only difference is that he uses it to show that c(n) = 2^{n-1}, rather than assuming it and then showing the equivalence of the two series for certain x (which he never even mentions).

8. Originally Posted by Stonehambey
Yeah, the algebra is similar to the authors'. The only difference is that he uses it to show that c(n) = 2^{n-1}, rather than assuming it and then showing the equivalence of the two series for certain x (which he never even mentions).
Effectively the particular 'multinomial series expansion'...

(1)

... justifies what is written in Your textbook...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$