#OK to post
#Homework 18, Rebecca Embar

read `C18.txt`:

#2
SeqCoStupid := proc(N) local n:
	[seq(NuC(2*n-1,[[0,1,1],[0,0,1]]),n=1..N)]:
end:

#5
#Conjecture: the number of vote-count Condorcet scenarios 
#with 2*v-1 voters is binom(v+3,5)

#Proof: 

#1 -> 2 -> 3 -> 1

#1 -> 2 iff (123+132+312)-(213+231+321)>=1 (1)
#2 -> 3 iff (231+213+123)-(321+312+132)>=1 (2)
#3 -> 1 iff (312+321+231)-(132+123+213)>=1 (3)

#(1)+(2) gives us 123 > 321
#(2)+(3) gives us 231 > 132
#(3)+(1) gives us 312 > 213

#For ease of writing, I will introduce the following notation: let 
#V(k,conditions) denote the number of vote-count-Condorcet scenarios with 
#k voters, subject to some conditions.
#For example, V(2*v-1,321>0) denotes the number of vote-count-Condorcet
#scenarios with 2*v-1 voters and where 321>0

#By removing/adding one voter each to 123 and 321, we see that the 
#vote-count-Condorcet scenarios with 2*v-1 voters, 321>0 are in bijection 
#with the vote-count-Condorcet scenarios with 2*v-3 voters (123 is always 
#> 0 for a Condorcet scenario).

#Thus, V(2*v-1,321>0)=V(2*v-3)

#Similarly, by removing/adding one voter each to 231 and 132, or from 
#312 and 213, we have V(2*v-1,132>0)=V(2*v-1,213>0)=V(2*v-3)

#By removing/adding one voter each to 123,312,231,132, we see that the 
#vote-count-Condorcet scenarios with 2*v-1 voters, 321>0 and 132>0,
#are in bijection with the vote-count-Condorcet scenarios with 2*v-5
#voters. Thus, V(2*v-1,321>0,132>0)=V(2*v-5)

#Similarly, V(2*v-1,132>0,213>0)=V(2*v-1,213>0,321>0)=V(2*v-5)

#Finally, by removing/adding one voter each to 123,312,231,132,312,213,
#we see that the vote-count-Condorcet scenarios with 2*v-1 voters, 
#321>0, 132>0, and 213>0 are in bijection with the vote-count-Condorcet
#scenarios with 2*v-7 voters. V(2*v-1,132>0,213>0,321>0)=V(2*v-7)

#Thus, we can break V(2*v-1) up as follows:

#V(2*v-1)=V(2*v-1,321>0)+V(2*v-1,132>0)+V(2*v-1,213>0)
			-V(2*v-1,321>0,132>0)-V(2*v-1,132>0,213>0)-V(2*v-1,213>0,321>0)
			+V(2*v-1,321>0,132>0,213>0)
			+V(2*v-1,321=132=213=0)
		 =3*V(2*v-3)-3*V(2*v-5)+V(2*v-7)+V(2*v-1,321=132=213=0)
			
#If we assume by induction that our conjecture holds for numbers < v (we
#can check the first few base cases using our Maple programs), we have,

#V(2*v-1)=3*binom(v+2,5)-3*binom(v+1,5)+binom(v,5)+V(2*v-1,321=132=213=0)

#What remains is to count V(2*v-1,321=132=213=0). I claim that this is equal
#to binom(v,2).

#Notice that if we impose the conditions 321=132=213=0, our inequalities
#become
#1 -> 2 iff (123+312)-(231)>=1 (1)
#2 -> 3 iff (231+123)-(312)>=1 (2)
#3 -> 1 iff (312+231)-(123)>=1 (3)

#Since 123+312+231=2*v-1, we have 231=2*v-1-(123+312), and similarly 
#312=2*v-1-(231+123) and 123=2*v-1-(312+231). This allows us to rewrite
#our inequalties in the following way.

#1 -> 2 iff 123+312 > v-1 (1)
#2 -> 3 iff 231+123 > v-1 (2)
#3 -> 1 iff 312+231 > v-1 (3)

#Notice that these conditions, combined with the condition that 
#123+312+231=2*v-1, implies that 123,312,231 are all < v.

#Then, let 123 = a, where a is in {1,...,v-1} (recall from our earlier 
#inequalities that 123,312,231 cannot be equal to 0).

#The condition 123+312 > v-1 yields 312 > v-1-a. Combining this with our 
#condition that 312 < v, we have that 312 must be in the set {v-1-a+1,...,v-1}. 
#Thus, let 312 = v-1-b, where b is in {0,...,a-1}

#Then, 231=2*v-1-(123+312)=v-a+b 

#Let us show that every choice of 123,312,231 that we have made satisfies all 
#three necessary inequalties, and therefore corresponds to a 
#vote-count-Condorcet scenario.
#We have,
#123+312=a+v-1-b=v-1+a-b > v-1, since b < a
#231+123=v-a+b+a=v+b > v-1, since b >= 0
#312+231=v-1-b+v-a+b=2v-1-a > v-1, since a < v-1

#Thus, these encompass all possible choices for 123,312,231. For each choice 
#of a in {1,...,v-1}, there are a possible choices for b. Thus, we have 
#1+...+v-1 = binom(v,2) possible choices for a and b and therefore binom(v,2) 
#possible vote-count-Condorcet scenarios with 321=132=213=0.

#Finally, we have,
#V(2*k-1)=3*binom(v+2,5)-3*binom(v+1,5)+binom(v,5)+binom(v,2)
	     =3*(v+2)!/(5!(v-3)!)-3*(v+1)!/(5!(v-4)!)+v!/(5!(v-5)!)+v!/(2!(v-2)!)
		 =v!/(5!(v-2)!)[3*(v+1)*(v+2)*(v-2)-3*(v+1)*(v-3)*(v-2)+(v-4)*(v-3)*(v-2)+60]
		 =v!/(5!(v-2)!)[v^3+6*v^2+11*v+6]
		 =v!/(5!(v-2)!)[(v+1)*(v+2)*(v+3)]
		 =(v+3)!/(5!(v-2)!)
		 =binom(v+3,5)