Two product formulas for counting successive vertex orderings

Boon Suan Ho, hbs@u.nus.edu

This Mathematica notebook accompanies a paper with the same title. The paper is available as an e-print from [insert arXiv link here when available].

Introduction

c[n_,j_]:=(6/j)(Binomial[n,3]-Binomial[n-j,3])

FullSimplify[c[n,j]==(j^2)+(3-3n)j+3(n^2)-6n+2]

d[m_,n_,j_]:=(1/j)(m Binomial[n,2]-(m-j)Binomial[n-2j,2])

Proof of Theorem 1

X[n_]:=Sqrt[1+6n-3(n^2)]

FullSimplify[-Binomial[n-3j,3]==-(1/6)(n-3j)(n-1-3j)(n-2-3j)]

FullSimplify[Binomial[n,3]-Binomial[n-3j,3] == (9/2)j(j-(1/6)(3n-3+X[n]))(j-(1/6)(3n-3-X[n]))]

Sum[Product[((-Binomial[n-3j,3])/(Binomial[n,3]-Binomial[n-3j,3])),{j,1,i}],{i,0,Floor[n/3]-1},Method->"HypergeometricTermPFQ"]

Note: I’ve rendered the output above in TraditionalForm to make it easier to read, as well as in some places below. To change it into a form manipulable by Mathematica, right-click on the expression, and click “Convert To > StandardForm.”

SheppardTransform[N_,a_,b_,d_,e_]:={d-a,e-a,d,e,-N,a,a+b-N-d-e+1,a-N-d+1,a-N-e+1}

FullSimplify/@SheppardTransform[(n/3)-1,(4/3)-(n/3),(5/3)-(n/3),(1/6)(9-3n+X[n]),(1/6)(9-3n-X[n])]

FullSimplify[X[n] == Sqrt[1-3(-2+n)n]]

FullSimplify[((1/6) (1-n+(Sqrt[1-3 (-2+n) n]))+j)((1/6) (1-n-(Sqrt[1-3 (-2+n) n]))+j)]

FullSimplify[((1/6) (9-3 n+(Sqrt[1-3 (-2+n) n]))+j)((1/6) (9-3 n-(Sqrt[1-3 (-2+n) n]))+j)]

Series[(20/9)+(j^2)-j (-3+n)+(1/3) (-5+n) n,{j,0,2}]

FullSimplify[c[3j+3]==9(j^2)+9(3-n)j+3(n^2)-15n+20]

b[n_,j_]:=9(j^2)-3(n-1)j+(n^2)-2n

FullSimplify[((b[n,0])/(c[n,n+1]))==((n(n-2))/((n^2)-4n+6))]

FullSimplify[c[n,k]==c[n,3n-3-k]]

FullSimplify[b[n,j]==c[n,n-1+3j]]

FullSimplify[b[n,j]==c[n,2n-2-3j]]

Proof of Theorem 2

Y[m_,n_]:=Sqrt[(((2m+1))^2)-8m n]

FullSimplify[-(m-j)Binomial[n-2j,2]==2(j-(n/2))(j+(1/2)-(n/2))(j-m)]

FullSimplify[m Binomial[n,2]-(m-j)Binomial[n-2j,2]==2j(j+(1/4)(1-2m-2n+Y[m,n]))(j+(1/4)(1-2m-2n-Y[m,n]))]

Sum[Product[((-(m-j)Binomial[n-2j,2])/(m Binomial[n,2]-(m-j)Binomial[n-2j,2])),{j,1,i}],{i,0,Min[m,Floor[(n/2)]]},Method->"HypergeometricTermPFQ"]

FullSimplify/@SheppardTransform[(n/2)-1,(3/2)-(n/2),1-m,(1/4)(5-2m-2n+Y[m,n]),(1/4)(5-2m-2n-Y[m,n])]

FullSimplify[((1/4) (-1-2 m+(Sqrt[1+4 m (1+m-2 n)]))+j)((1/4) (-1-2 m-(Sqrt[1+4 m (1+m-2 n)]))+j)]

FullSimplify[((1/4) (5-2 m+(Sqrt[1+4 m (1+m-2 n)])-2 n)+j)((1/4) (5-2 m-(Sqrt[1+4 m (1+m-2 n)])-2 n)+j)]

Series[(1/4) (2 (3+2 j) (1+j-m)+(-5-4 j+4 m) n+(n^2)),{j,0,2}]

FullSimplify[d[m,n,j+1]==2(j^2)+(5-2m-2n)j+(1/2)(6-6m-5n+4m n+(n^2))]

p[m_,n_,j_]:=2(j^2)-(2m+1)j+m n

q[m_,n_,j_]:=m n-Binomial[m+1,2]+Binomial[j,2]

FullSimplify[q[m,n,j]==q[m,n,1-j]]

FullSimplify[p[m,n,j]==q[m,n,m-2j+1]]

FullSimplify[p[m,n,j]==q[m,n,2j-m]]

FullSimplify[d[m,n,j]==p[m,n,m+(n/2)-j]]

FullSimplify[d[m,n,j]==q[m,n,m+n-2j]]

FullSimplify[((4(m^2))/(6+4m-5n+(n^2)))==((q[m,n,m]q[m,n,m+1])/(q[m,n,m-n+1]q[m,n,m-n+3]))]

Here we give some examples of how the general behavior of the product identity looks like in all three cases.

Case 1 ().

m=15

n=18

Indices on the left-hand side of Equation (4):

Table[m-2j+1,{j,0,(n/2)}]

Table[m+n-2j,{j,(n/2),m-1}]

Indices on the right-hand side of Equation (4):

Table[j,{j,1,m+1}]

Our goal is to show that the two sets of indices on the left partition the set of indices on the right, subject to the relation ; that is, the index 0 should be interpreted as 1, the index -1 as 2, index -2 as 3, etc., so that all indices considered are positive.

Case 1A ().

In this case, negative indices can only belong to the second product on the left.

m=23

n=12

Indices on the left-hand side of Equation (4):

Table[m-2j+1,{j,0,(n/2)}]

Table[m+n-2j,{j,(n/2),m-1}]

Indices on the right-hand side of Equation (4):

Table[j,{j,1,m+1}]

Case 1B ().

In this case, negative indices can only belong to the first product on the left.

m=17

n=26

Indices on the left-hand side of Equation (4):

Table[m-2j+1,{j,0,(n/2)}]

Table[m+n-2j,{j,(n/2),m-1}]

Indices on the right-hand side of Equation (4):

Table[j,{j,1,m+1}]

Case 2 ().

There are five products to consider in this case: Three on the left, and two on the right.

m=12

n=30

Indices from splitting the left-hand product into three parts:

Table[m-2j+1,{j,0,Ceiling[((m-1)/2)]}]

Table[m-2j+1,{j,Ceiling[((m+1)/2)],m}]

Table[m-2j+1,{j,m+1,(n/2)}]

Indices on the right-hand side of the first displayed equation in Case 2:

Table[j,{j,1,m+1}]

Table[m+n-2j,{j,m,(n/2)-1}]

Now we unset the values of m and n to avoid bugs later on.

m=.

n=.

Gosper’s Algorithm

We import Paule and Shorne’s fastZeil package, which contains a fast implementation of Gosper’s algorithm (as well as Zeilberger’s algorithm, but we do not use it here).

<<RISC`fastZeil`

Fast Zeilberger Package version 3.61
written by Peter Paule, Markus Schorn, and Axel Riese
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Now we prove the  identity needed in the proof of Theorem 1 for the  case.

Gosper[(Pochhammer[1-(n/3),k]Pochhammer[(4/3)-(n/3),k]Pochhammer[2,k])/(Pochhammer[(1/6)(11-n+X[n]),k]Pochhammer[(1/6)(11-n-X[n]),k]Factorial[k]),{k,0,(n/3)-1}]

You can run Prove[] right after running Gosper[] to generate a proof of this equality, which gives you the value of  discussed in Section 3 of the paper.

Prove[]

FullSimplify[-(((5-n+(Sqrt[1+6 n-3 (n^2)])) (-5+n+(Sqrt[1+6 n-3 (n^2)])))/(12 (-2+n)))==(((n^2)-4n+6)/(3n-6))]

Let’s work through the details of the proof generated by Gosper’s algorithm.

t[n_,k_]=(Pochhammer[1-(n/3),k]Pochhammer[(4/3)-(n/3),k]Pochhammer[2,k])/(Pochhammer[(1/6)(11-n+X[n]),k]Pochhammer[(1/6)(11-n-X[n]),k]Factorial[k])

R1[n_,k_]:=-((6+9(k^2)-3k(n-5)+n(n-4))/(3(k+1)(n-2)))

FullSimplify[(1/(t[n,k]))(R1[n,k+1] t[n,k+1]-R1[n,k]t[n,k])]

FullSimplify[R1[n,(n/3)]t[n,(n/3)]-R1[n,0]t[n,0],Element[(n/3),PositiveIntegers]&&Divisible[n,3]]

Notice that since we have assumed that  here, the large term on the right vanishes since it contains the factor .

FullSimplify[((6+(-4+n)n)/(3(-2+n)))==(((n^2)-4n+6)/(3n-6))]

Now we prove the  identity needed in the proof of Theorem 2 for the  case.

u[m_,n_,k_]:=(Pochhammer[1-(n/2),k]Pochhammer[(3/2)-(n/2),k]Pochhammer[2,k])/(Pochhammer[(1/4)(9+2m-2n+Y[m,n]),k]Pochhammer[(1/4)(9+2m-2n-Y[m,n]),k]Factorial[k])

R2[m_,n_,k_]:=-((2(1+k)(3+2k+2m)-(5+4k)n+(n^2))/(4(1+k)m))

FullSimplify[(1/(u[m,n,k]))(R2[m,n,k+1]u[m,n,k+1]-R2[m,n,k]u[m,n,k])]

FullSimplify[R2[m,n,(n/2)+1]u[m,n,(n/2)+1]-R2[m,n,0]u[m,n,0],Element[(n/2),PositiveIntegers]]

Here, much like before, the term  vanishes as we have assumed that .

Appendix A

Induction base case ():

FullSimplify[1+(((-N)(a)(-a+N+d+e-1))/(d e))-(((-a+N+d-1)(-a+N+e-1))/(d e))==(((1-N)(a+1)(-a+N+d+e-1))/(d e))]

Inductive step: Write the big expression as Sum[ir[k], {k,0,s}] - ic Sum[iu[k], {k,0,s-1}] == iv[s]:

ir[k_]:=((Pochhammer[-N,k]Pochhammer[a,k]Pochhammer[-a+N+d+e-1,k])/(Pochhammer[d,k]Pochhammer[e,k]Factorial[k]))

ic := (((-a+N+d-1)(-a+N+e-1))/(d e))

iu[k_]:=((Pochhammer[1-N,k]Pochhammer[a+1,k]Pochhammer[-a+N+d+e-1,k])/(Pochhammer[d+1,k]Pochhammer[e+1,k]Factorial[k]))

iv[k_]:=((Pochhammer[1-N,k]Pochhammer[a+1,k]Pochhammer[-a+N+d+e-1,k])/(Pochhammer[d,k]Pochhammer[e,k]Factorial[k]))

We are to show that Sum[ir[k], {k,0,s+1}] - ic Sum[iu[k], {k,0,s}] == iv[s+1] during the induction step. Using the inductive hypothesis this amounts to proving that ir[s+1] - ic iu[s] + iv[s] == iv[s+1]:

FullSimplify[ir[s+1]-ic iu[s] + iv[s] == iv[s+1]]

FullSimplify/@SheppardTransform[(n/3)-(4/3),1-(n/3),(5/3)-(n/3),(1/6)(9-3n+X[n]),(1/6)(9-3n-X[n])]

FullSimplify/@SheppardTransform[(n/3)-(5/3),1-(n/3),(4/3)-(n/3),(1/6)(9-3n+X[n]),(1/6)(9-3n-X[n])]

Gosper[((Pochhammer[(5/3)-(n/3),k]Pochhammer[1-(n/3),k]Pochhammer[2,k])/(Pochhammer[(1/6)(13-n+X[n]),k]Pochhammer[(1/6)(13-n-X[n]),k]Factorial[k])),{k,0,(n/3)-(2/3)}]

FullSimplify[-(((7-n+(Sqrt[1+6 n-3 (n^2)])) (-7+n+(Sqrt[1+6 n-3 (n^2)])))/(12 (-1+n)))]

FullSimplify/@SheppardTransform[(n/2)-(3/2),1-(n/2),1-m,(1/4)(9+2m-2n+Y[m,n]),(1/4)(9+2m-2n-Y[m,n])]