Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Inequalities or histogram or something.......

• To: mathgroup at smc.vnet.net
• Subject: [mg89353] Re: [mg89338] Inequalities or histogram or something.......
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Sat, 7 Jun 2008 02:56:29 -0400 (EDT)
• References: <200806061047.GAA24209@smc.vnet.net> <C131242B-F293-41C3-86B9-233078332582@mimuw.edu.pl> <6AABE4A5-728F-45E8-AB45-F86C6B445438@mimuw.edu.pl>

In fact, I think, I was initially too pessimistic about this problem.  
I belive that I can now prove the following:

d(v,k) = (k + 1) (v - k - 2)

The proof uses the same argument which I used to show that d(v,0) = v-2
(note that this follows form the above formula). Note also that

d(v,k) + d(v,v-k-3) = (k + 1) (-k + v - 2) + (k + 1) (-k + v - 2) = 2  
(k + 1) (-k + v - 2)

which is just your formula. You can also check that this agrees with  
the function d[v,k] defined below.

So I think your problem is now completely solved.

Andrzej Kozlowski


On 6 Jun 2008, at 22:39, Andrzej Kozlowski wrote:

> I just realized that the program I wrote is usually giving wrong  
> answers (but very fast ;-)) . The answer returned last time for  
> d[10000, 2305]  was absurdly low!
> The reason for this is that I  forgot (not for the first time) that  
> Reduce only returns a list of solutions of an equation with a finite  
> number of solutions if that number is less than a certain value,  
> which by default is only 10. We can change this as follows:
>
> SetSystemOptions[ReduceOptions -> {DiscreteSolutionBound -> 10^8}]
>
> d[v_, 0] := v - 2
> d[v_, k_] /; (v - 3)/2 < k < v - 2 := d[v, k] = 2 (k + 1) (v - k -  
> 2) - d[v, v - k - 3]
> d[v_, k_] /; 0 < k <= (v - 3)/2 := d[v, k] = Length[Union[Reduce[1  
> <= x1 < x2 < x3 <= v && k == x1 + x3 - x2 - 2, {x1, x2, x3},  
> Integers]]]
>
> d[200, 24] // Timing
> {0.118747, 4350}
>
> This is still pretty fast and this time correct. One can try  
> somewhat larger values:
>
> d[1000, 500] // Timing
> {3.47657, 249498}
>
> The number of solutions is already pretty large and I would  
> certainly not try much larger numbers with this method. Of course,  
> if the purpose if to find a conjecture about the value of d[v,k]  
> this ought to be quite enough.
>
> Andrzej Kozlowski
>
>
>
>
>
>
> On 6 Jun 2008, at 22:13, Andrzej Kozlowski wrote:
>
>> I don't have a general formula, and having given it only a little  
>> thought, am not convinced an explicit formula can be found in the  
>> general case. But I may be wrong. But here are some observations.
>>
>> First, note that in your post you make the assumption that 1<=k but  
>> then you give an example with k==0. Presumably you mean k>=0?
>>
>> Also, your assumption k<v follows from   1<= x1 < x2 < x3 <= v and  
>> k = x1 + x3 - x2 - 2, since clearly
>> k==x3 -(x2-x1)-2 must be less than x3 which is less than v. But  
>> this is not important.
>>
>> It also easy to see that your equation can only have solutions if  
>> v>k+2, which of course is needed for your relation d(v,k) + d(v,v- 
>> k-3) = 2(k+1)(v-k-2) to make sense. The case v=3 then k must be 0  
>> so we can assume that v>=4.
>>
>> Next, it is easy to prove that
>>
>> d[v,0]== v -2
>>
>> The proof goes as follows. For k= 0 your equation becomes
>>
>> x1 + x3 - x2 - 2==0
>>
>> which can be re-written as
>>
>> x1 = 2 -(x3-x2)
>>
>> Now, since x3-x2>0 and x1>=1, this only leaves the possibility that  
>> x1 = 1. So the equation becomes x3-x2=1. So d[v,0] is the number of  
>> ways of choosing two successive integers between 1 and v. You can  
>> choose any integer z such that 2<=z<=v-1 as the smaller one, and v 
>> +1 as the larger one. There are v-2 such choices.
>> So now that we know that d[v,0]=v-2 and can write a reasonably fast  
>> program to find other values of d[v,k].
>>
>> d[v_, 0] := v - 2
>>
>> d[v_, k_] /; (v - 3)/2 < k < v - 2 := d[v, k] = 2 (k + 1) (v - k -  
>> 2) - d[v, v - k - 3]
>>
>> d[v_, k_] /; 0 < k <= (v - 3)/2 := d[v, k] = Length[Union[ Reduce[1  
>> <= x1 < x2 < x3 <= v && k == x1 + x3 - x2 - 2, {x1, x2, x3},   
>> Integers]]]
>>
>>
>> This seems quite fast; for example
>>
>> d[10000, 2305] // Timing
>> {0.283073, 4}
>>
>> d[10000, 7692] // Timing
>> {0.000065, 35480112}
>>
>> So one could try to first explore this empirically, guess the  
>> formula and then it should not be hard to prove it inductively. But  
>> this is as much time as I can devote to this problem.
>>
>>
>> Andrzej Kozlowski
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> On 6 Jun 2008, at 19:47, Steve Gray wrote:
>>
>>> Can Mathematica help with this? Or can someone?
>>>
>>> I have positive integers x1,x2,x3,k,v.
>>>
>>> There are assumptions:
>>> 1 <= k < v and
>>> 1 <= x1 < x2 < x3 <= v.
>>>
>>> There is one equation:
>>> k = x1 + x3 - x2 - 2.
>>>
>>> I need a symbolic solution for the number of combinations of  
>>> x1,x2,x3
>>> that satisfy the equation under the assumptions.
>>>
>>> This will be a histogram of k vs. the number of solutions.
>>> One numeric point on the histo: if v=8 and k=0, there are 6  
>>> solutions,
>>> x1,x2,x3 = 1,2,3; 1,3,4; 1,4,5; 1,5,6; 1,6,7; 1,7,8; none with x1  
>>> > 1.
>>>
>>> I need a general symbolic solution in terms of D(v,k). I need a  
>>> way to
>>> show its derivation for a paper. I happen to know that
>>> D(v,k) + D(v,v-k-3) = 2(k+1)(v-k-2).
>>>
>>> This is not overwhelmingly complicated but I don't know a decent way
>>> to go about it. Thank you for any help, using Mathematica or not.  
>>> (I have
>>> version 6.)
>>>
>>> Steve Gray
>>>
>>
>

• Follow-Ups:
  • Re: Re: Inequalities or histogram or something.......
    • From: Curtis Osterhoudt <cfo@lanl.gov>

• References:
  • Inequalities or histogram or something.......
    • From: Steve Gray <stevebg@roadrunner.com>