# combinatorial problem??

• Sep 23rd 2009, 01:08 AM
tanujkush
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$
• Sep 23rd 2009, 03:14 PM
lepton
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.
• Sep 23rd 2009, 10:29 PM
tanujkush
Quote:

Originally Posted by lepton
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.