Results 1 to 8 of 8

Thread: Composition problem

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    114

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    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.




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

    . . . . .

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

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



    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2
    Quote Originally Posted by Soroban View Post
    Hello, Stonehambey!


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




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

    . . . . .

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

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



    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)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2008
    Posts
    114
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2
    Quote Originally Posted by Stonehambey View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    Quote Originally Posted by Stonehambey View Post
    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$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2008
    Posts
    114
    Quote Originally Posted by chisigma View Post
    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).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    Quote Originally Posted by Stonehambey View Post
    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$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Function composition problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: May 13th 2010, 07:56 AM
  2. function composition problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Mar 23rd 2010, 11:34 PM
  3. Difficult BC Composition Problem
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Oct 14th 2009, 08:30 AM
  4. Problem with Composition of Functions
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Sep 21st 2009, 07:38 PM
  5. Relational Composition Problem - Please help!
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Sep 10th 2006, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum