Related to partition theory, ways of representing a number

[tanujkush]

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

 

[ramsey2879]

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

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

 

[ramsey2879]

See http://www.research.att.com/~njas/sequences/?q=partitions+%22even+number+of+parts%22+partition&sort=0&fmt=0&language=english&go=Search
In particular A027187 a(n+1) gives the number of ways 2n can be partition into an even number of even integers. Each A(n+1) would have to be multiplied by the number of ways your odd integral number less 2n, can be partioned into odd numbers and the products summed.

 

[tanujkush]

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, let's say the odd number is 2k+1
Then, let 2 appear p₁ times, 4 appear p₂ 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₁+4p₂+...+(2k-2)p_m

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

2p₁+4p₂+6p₃+...+(2k-2)p_m=2k
or
p₁+2p₂+3p₃+...+(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,

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

 

[ramsey2879]

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, let's say the odd number is 2k+1
Then, let 2 appear p₁ times, 4 appear p₂ 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₁+4p₂+...+(2k-2)p_m

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

2p₁+4p₂+6p₃+...+(2k-2)p_m=2k
or
p₁+2p₂+3p₃+...+(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,

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

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.

 

[tanujkush]

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.

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 doesn't appear as if this problem is well posed . Thanks for your help though

 

[damo_clark]

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.

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.

 

[tanujkush]

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!

 

[ramsey2879]

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 doesn't appear as if this problem is well posed . Thanks for your help though

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-1C_p-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)/2}C_t-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.