Results 1 to 8 of 8

Math Help - 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

    \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
    11,826
    Thanks
    714
    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 \,n units long.

    . . . . .

    There are \,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 \,n units long.

    . . . . .

    There are \,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
    5
    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

    \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

    \chi \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

    \chi \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
    5
    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

    \chi \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: March 23rd 2010, 11:34 PM
  3. Difficult BC Composition Problem
    Posted in the Calculus Forum
    Replies: 3
    Last Post: October 14th 2009, 08:30 AM
  4. Problem with Composition of Functions
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 21st 2009, 07:38 PM
  5. Relational Composition Problem - Please help!
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 10th 2006, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum