Register to reply 
Related to partition theory, ways of representing a number 
Share this thread: 
#1
Sep2109, 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 


#2
Sep2109, 07:00 PM

P: 894




#3
Sep2109, 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. 


#4
Sep2209, 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 p_{1} times, 4 appear p_{2} times and so on, till the second largest even number behind 2k+1 which is 2k2, 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^{(2k2).1}+x^{(2k2).2}+...) Coefficients of x^{2k}: 2k=2p_{1}+4p_{2}+...+(2k2)p_{m} Now the problem boils down to finding the number of solutions of the following equation: 2p_{1}+4p_{2}+6p_{3}+...+(2k2)p_{m}=2k or p_{1}+2p_{2}+3p_{3}+...+(k1)p_{m}=k here m is the number of even numbers between 1 and 2K+1 which is nothing but (k1) (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! 


#5
Sep2209, 09:40 AM

P: 894




#6
Sep2309, 12:02 AM

P: 39




#7
Sep2309, 12:12 AM

P: 11

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 coefficients 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 coefficients. (up to about the 70th coefficient). 5. If you see any obvious pattern in the coefficients then you can extend the coefficient 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 coefficient 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 coefficients for the inverse of the generating function. 


#8
Sep2309, 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! 


#9
Sep2309, 12:32 PM

P: 894

^{n+p1}C_{p1} for p = 2,4,6...INT((n1)/2)*2 then the problem would be to compute the number of ways to partion r2n r being the odd integer into an odd number (t) of odd integers. The number of ways to add t even numbers to get r2n+t is the same as the number of ways to sum t odd numbers to get r2n, which would be the sum of ^{(r2n+3t2)/2}C_{t1} for t = 1,3,5 ... (r2n+t)/21 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 