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

*To*: mathgroup at smc.vnet.net*Subject*: [mg89459] Re: [mg89353] Re: [mg89338] Inequalities or histogram or something.......*From*: Curtis Osterhoudt <cfo at lanl.gov>*Date*: Tue, 10 Jun 2008 03:40:09 -0400 (EDT)*Organization*: LANL*References*: <200806061047.GAA24209@smc.vnet.net> <6AABE4A5-728F-45E8-AB45-F86C6B445438@mimuw.edu.pl> <200806070656.CAA09750@smc.vnet.net>*Reply-to*: cfo at lanl.gov

And I believe that Andrzej is correct, merely because his closed-form solution agrees with my plot :) Cheers, Curtis O. On Saturday 07 June 2008 00:56:29 Andrzej Kozlowski wrote: > 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 -- ========================================================== Curtis Osterhoudt cfo at remove_this.lanl.and_this.gov PGP Key ID: 0x4DCA2A10 Please avoid sending me Word or PowerPoint attachments See http://www.gnu.org/philosophy/no-word-attachments.html ==========================================================

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

**Re: Inequalities or histogram or something.......***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>