# Related to partition theory, ways of representing a number

1. ### tanujkush

39
Hi,

I've been trying to find out the ways in which an odd integral number can be represented by smaller integers such that the even integers occur an even number of times. So for example, the number 15 has the following representations:

15: 2+2+2+2+2+2+3 (even integer 2 occurs even number of times i.e. 6 times)
15: 4+2+2+2+5 (even integers 4 and 2 combined occur 4 times - 2 occurs thrice and 4 occurs once)
15: 6+2+2+2+3 and so on.

I've been trying to derive an analytical formula for this problem. Any ideas anyone?

Thanks

2. ### ramsey2879

894
Would zero times be considered an even number of times, e.g. 3+3+5 = 11?

894
4. ### tanujkush

39
thanks ramsey, that link does provide an analytical method to go about it.

i came up with this formulation over a night of concentrated thinking aided by floyd's "brain damage"

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

Coeff(2k)=(1+x2.1+x2.2+...)(1+x4.1+x4.2+...)....(1+x(2k-2).1+x(2k-2).2+...)

Coefficients of x2k:
2k=2p1+4p2+...+(2k-2)pm

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

2p1+4p2+6p3+...+(2k-2)pm=2k
or
p1+2p2+3p3+...+(k-1)pm=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,

Does this make sense or have I gone wrong somewhere? Help is appreciated thank you!

Last edited: Sep 22, 2009
5. ### ramsey2879

894
Sorry, you have gotten into something that is beyond my skills. But I am surprised that you didn't take my suggestion of using the earlier work to reduce your problem to something more simple.

Last edited: Sep 22, 2009
6. ### tanujkush

39
I did look into what you had pointed to. The thing is, the solution listed on the website provides a computational solution and not one that is analytical. I am looking for a closed form solution. But it seems like I will have to resort to a computational solution myself, since it doesnt appear as if this problem is well posed . Thanks for your help though

7. ### damo_clark

11
I haven't solved this problem but can suggest a method which might solve it.

1. I would first generalise the problem to finding the number of ways any number can be represented by smaller integers such that the even integers occur an even number of times.

2. Write a computer program to generate all partitions of an integer n for n< 100, and then count the the partitions of interest for a particular number. From this you can generate a set of 100 numbers, such that the nth element in the set represents the number of partitions of n, satisfying your conditions.

3. Construct a polynomial generating function of order 100, whose co-efficients come from the set constructed with your computer program.

4. Expand the inverse of your polynomial generating function, as a polynomial, and note it's co-efficients. (up to about the 70th co-efficient).

5. If you see any obvious pattern in the co-efficients then you can extend the co-efficient set up to an arbitrary length, then pop them back into your inverse generating function, and do step 4 in reverse. This will give you back an expanded set, as explained in step 3. These are the numbers you want.

The co-efficient from step 4, can also be used to define a recursive formula to solve your problem.

I know this method works if your partitions are unrestricted but it will fail if you don't get a nice set of polynomial co-efficients for the inverse of the generating function.

Last edited: Sep 23, 2009
8. ### tanujkush

39
Thanks damo_clark for your solution.

Actually, I have something similar to what damo_clark suggested already written and coded out. It works fine, for odd numbers up to a certain maximum value after which the program just hangs.

The reason I need to find a closed form analytical solution (which is exact) is that I am using the method here as a cryptography algorithm and thus I need to be exact. (plus the numbers that I need to partition sometimes are bigger than my algorithm can handle).

Thanks for the help though!

9. ### ramsey2879

894
Ok, for an analytical solution, an even no of solutions for r = 2n in even numbers is the same as an even number of solutions in integers for r = n. This would be the sum of
n+p-1Cp-1 for p = 2,4,6...INT((n-1)/2)*2 then the problem would be to compute the number of ways to partion r-2n r being the odd integer into an odd number (t) of odd integers. The number of ways to add t even numbers to get r-2n+t is the same as the number of ways to sum t odd numbers to get r-2n, which would be the sum of
(r-2n+3t-2)/2Ct-1 for t = 1,3,5 ... (r-2n+t)/2-1 since 1 would have to be subtracted t times to get odd numbers instead of even numbers.
You might find a flaw in my logic, but my idea should be helpful.

Last edited: Sep 23, 2009
Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?