Results 1 to 3 of 3

Thread: 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:

    $\displaystyle 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 $\displaystyle o_n,e_n$ be the number of ways to partition $\displaystyle n$ into at most $\displaystyle n$ odd parts and the number of partitions of $\displaystyle n$ such that each even part occurs an even number of times, respectively. Define $\displaystyle O(x),E(x)$ to be the respective generating functions for $\displaystyle o_n,e_n$, then

    $\displaystyle 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

    $\displaystyle 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 $\displaystyle P(x)=O(x)E(x)$, then

    $\displaystyle 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 $\displaystyle p_n$ is the number of partitions of $\displaystyle n$ where the number of even parts is even. The number of ways to do this when $\displaystyle n=2k+1$ is the coefficient of $\displaystyle 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 $\displaystyle o_n,e_n$ be the number of ways to partition $\displaystyle n$ into at most $\displaystyle n$ odd parts and the number of partitions of $\displaystyle n$ such that each even part occurs an even number of times, respectively. Define $\displaystyle O(x),E(x)$ to be the respective generating functions for $\displaystyle o_n,e_n$, then

    $\displaystyle 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

    $\displaystyle 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 $\displaystyle P(x)=O(x)E(x)$, then

    $\displaystyle 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 $\displaystyle p_n$ is the number of partitions of $\displaystyle n$ where the number of even parts is even. The number of ways to do this when $\displaystyle n=2k+1$ is the coefficient of $\displaystyle 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 $\displaystyle p_1$ times, 4 appear $\displaystyle p_2$ times and so on, till the second largest even number behind 2k+1 which is 2k-2, which appears say $\displaystyle p_m$ times. (Here m = k - 1)
    Then, comparing the coefficients of $\displaystyle x^{2k}$ in the Euler generating function, (which amounts to finding the number of ways 2k is partitioned into even integers)

    Coeff(2k)=$\displaystyle (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 $\displaystyle x^{2k}:$
    $\displaystyle 2k=2p_1+4p_2+...+(2k-2)p_m$

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

    $\displaystyle 2p_1+4p_2+6p_3+...+(2k-2)p_m=2k$
    or
    $\displaystyle 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: Oct 23rd 2011, 07:04 AM
  2. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 16th 2011, 03:39 PM
  3. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Oct 4th 2011, 09:05 AM
  4. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Jun 13th 2008, 06:22 PM
  5. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 19th 2008, 06:19 PM

Search Tags


/mathhelpforum @mathhelpforum