Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

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

Search the Archive

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

  • To: mathgroup at smc.vnet.net
  • Subject: [mg89346] Re: [mg89338] Inequalities or histogram or something.......
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Sat, 7 Jun 2008 02:51:25 -0400 (EDT)
  • References: <200806061047.GAA24209@smc.vnet.net>

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
>



  • Prev by Date: Re: Adding markers on the surface of a Plot3D?
  • Next by Date: Major problem with 6.0.2.1
  • Previous by thread: Re: Inequalities or histogram or something.......
  • Next by thread: Re: Inequalities or histogram or something.......