Results 1 to 3 of 3

Math Help - combinatorial problem??

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    13

    combinatorial problem??

    Hi,

    I've been trying to find the number of ways an odd integer can be partitioned into smaller integers such that even integers occur an even number of time in the partition. While working on this, I have reached the following roadblock - finding the number of solutions of a linear equation. As an example, what would be the number of integral, non negative solutions of the following equation:

    x + 2y + 3z = 4
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie lepton's Avatar
    Joined
    Sep 2009
    Posts
    10
    Are you familiar with generating functions?

    If so...

    Let o_n,e_n be the number of ways to partition n into at most n odd parts and the number of partitions of n such that each even part occurs an even number of times, respectively. Define O(x),E(x) to be the respective generating functions for o_n,e_n, then

    O(x)=\sum_{n\ge0}o_nx^n=\prod_{r\,\text{odd}}\left  (\sum_{k=0}^nx^{rk}\right)=\prod_{r\,\text{odd}}(1  +x^r+\cdots+x^{rn})

    and

    E(x)=\sum_{n\ge0}e_nx^n=\prod_{r\,\text{even}}\lef  t(\sum_{k\ge0}x^{rk}\right)=\prod_{r\,\text{even}}  \frac{1}{1-x^{2r}}

    Let P(x)=O(x)E(x), then

    P(x)=\prod_{r\,\text{odd}}(1+x^r+\cdots+x^{rn})\pr  od_{r\,\text{even}}\frac{1}{1-x^{2r}}=\sum_{n\ge 0} p_nx^n,

    where p_n is the number of partitions of n where the number of even parts is even. The number of ways to do this when n=2k+1 is the coefficient of x^{2k+1}.

    If not...I highly recommend generatingfunctionology by Wilf because it's a good book, but better yet, it's free to download at the link I provided. In particular, page 100 begins his discussion of using generating functions for partitions.

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    13
    Quote Originally Posted by lepton View Post
    Are you familiar with generating functions?

    If so...

    Let o_n,e_n be the number of ways to partition n into at most n odd parts and the number of partitions of n such that each even part occurs an even number of times, respectively. Define O(x),E(x) to be the respective generating functions for o_n,e_n, then

    O(x)=\sum_{n\ge0}o_nx^n=\prod_{r\,\text{odd}}\left  (\sum_{k=0}^nx^{rk}\right)=\prod_{r\,\text{odd}}(1  +x^r+\cdots+x^{rn})

    and

    E(x)=\sum_{n\ge0}e_nx^n=\prod_{r\,\text{even}}\lef  t(\sum_{k\ge0}x^{rk}\right)=\prod_{r\,\text{even}}  \frac{1}{1-x^{2r}}

    Let P(x)=O(x)E(x), then

    P(x)=\prod_{r\,\text{odd}}(1+x^r+\cdots+x^{rn})\pr  od_{r\,\text{even}}\frac{1}{1-x^{2r}}=\sum_{n\ge 0} p_nx^n,

    where p_n is the number of partitions of n where the number of even parts is even. The number of ways to do this when n=2k+1 is the coefficient of x^{2k+1}.

    If not...I highly recommend generatingfunctionology by Wilf because it's a good book, but better yet, it's free to download at the link I provided. In particular, page 100 begins his discussion of using generating functions for partitions.

    Hope this helps.
    hi lepton, thanks for your reply. I am aware of partition theory and using this, I have arrived at the problem that I mentioned in my first post. Please see this:

    Using the Euler generating function, lets say the odd number is 2k+1
    Then, let 2 appear p_1 times, 4 appear p_2 times and so on, till the second largest even number behind 2k+1 which is 2k-2, which appears say p_m times. (Here m = k - 1)
    Then, comparing the coefficients of x^{2k} in the Euler generating function, (which amounts to finding the number of ways 2k is partitioned into even integers)

    Coeff(2k)= (1+x^{2.1}+x^{2.2}+...)(1+x^{4.1}+x^{4.2}+...)....  (1+x^{(2k-2).1}+x^{(2k-2).2}+...)

    Coefficients of x^{2k}:
    2k=2p_1+4p_2+...+(2k-2)p_m

    Now the problem boils down to finding the number of solutions of the following equation:

    2p_1+4p_2+6p_3+...+(2k-2)p_m=2k
    or
    p_1+2p_2+3p_3+...+(k-1)p_m=k

    here m is the number of even numbers between 1 and 2K+1 which is nothing but (k-1) (and not k, since if m goes up to k, there will be one even integer 2k which will have to appear alone and that is not allowed)

    I'm stuck at calculating the number of solutions to the above equation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 23rd 2011, 07:04 AM
  2. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 16th 2011, 03:39 PM
  3. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 4th 2011, 09:05 AM
  4. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 13th 2008, 06:22 PM
  5. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2008, 06:19 PM

Search Tags


/mathhelpforum @mathhelpforum