combinatorial problem??

**tanujkush** · September 23rd 2009, 01:08 AM

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$

**lepton** · September 23rd 2009, 03:14 PM

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.

**tanujkush** · September 23rd 2009, 10:29 PM

Originally Posted by lepton

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.

Thread: combinatorial problem??

LinkBack

Thread Tools

Display

combinatorial problem??

Similar Math Help Forum Discussions

a combinatorial problem

Combinatorial problem

Combinatorial problem

Combinatorial problem

Combinatorial problem

Search Tags