Register to reply

Related to partition theory, ways of representing a number

by tanujkush
Tags: partition, partition function
Share this thread:
tanujkush
#1
Sep21-09, 06:22 AM
P: 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
Phys.Org News Partner Science news on Phys.org
Final pieces to the circadian clock puzzle found
A spray-on light show on four wheels: Darkside Scientific
How an ancient vertebrate uses familiar tools to build a strange-looking head
ramsey2879
#2
Sep21-09, 07:00 PM
P: 894
Quote Quote by tanujkush View Post
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
#3
Sep21-09, 08:45 PM
P: 894
See http://www.research.att.com/~njas/se...lish&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
#4
Sep22-09, 01:20 AM
P: 39
Related to partition theory, ways of representing a number

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!
ramsey2879
#5
Sep22-09, 09:40 AM
P: 894
Quote Quote by tanujkush View Post
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!
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
#6
Sep23-09, 12:02 AM
P: 39
Quote Quote by ramsey2879 View Post
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 doesnt appear as if this problem is well posed . Thanks for your help though
damo_clark
#7
Sep23-09, 12:12 AM
P: 11
Quote Quote by tanujkush View Post
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
#8
Sep23-09, 03:53 AM
P: 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!
ramsey2879
#9
Sep23-09, 12:32 PM
P: 894
Quote Quote by tanujkush View Post
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
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.


Register to reply

Related Discussions
Representing vector by a number. General Math 16
Representing complex number as a vector. General Math 6
Number of ways to make change for dollar with even number of coins Calculus & Beyond Homework 1
Let X be a random variable representing the number of times you need to roll (includi Set Theory, Logic, Probability, Statistics 2
Representing a wave as a complex number. Introductory Physics Homework 6