#OK to post homework 
#Natalya Ter-Saakov, April 3, Assignment 18
read "C18.txt":

#Problem 2
#SeqCoStupid(N): inputs a positive integer N and outputs the first N terms of the sequence
#"Number of voting-profiles (NOT vote-count profiles) with 2*n-1 voters that lead to 1->2->3->1"

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

#Problem 3
SeqCoSmart:=proc(N) local t,x123,x132,x213,x231,x321,x312,p,i,l:
p:=seq(coeff(taylor(((1+t^3*x123*x231*x312)*t^3*x312*x123*x231) / ((1-t^2*x123*x321)*(1-t^2*x213*x312)*(1-t^2*x312*x123)*(1-t^2*x132*x231)*(1-t^2*x123*x231)*(1-t^2*x231*x312)),t=0,2*N+1),t,2*i-1),i=1..N):
for i from 1 to N do
	if p[i]=0 then l[i]:=0: 
	else 
	l[i]:=Umb(p[i],[x123,x132,x213,x231,x312,x321]):
	fi:
	print(2*l[i]/6^(2*n-1)):
od:

seq(l[i],i=1..N):
end:

#SeqCoSmart(20) took 0.625 seconds
#and SeqCoStupid(20) took 1986.265 seconds

#Problem 4
#The limiting probability seems to be ???

#Problem 6

#GQP1(L,p,n): inputs a list L and tries to guess a quasi-polynomial of period p that fits the data

GQP1:= proc(L,p,n) local i,j,length, q, SL,k:
if not type(n,symbol) then error("n is not a symbol"): fi:
length:=nops(L):
if length<p then 
	print("sequence too short"): 
	return(FAIL): 
fi:
for i from 1 to p do
	SL[i]:=[seq(L[p*j+i], j=0..floor((length-i)/p))]:
	if GP(SL[i],k)=FAIL then return(FAIL) fi:
	print(GP(SL[i],k)):
	q[i]:=subs(k=(n-i+p)/p,GP(SL[i],k)):
od:
[seq(q[i],i=1..p)]:
end:

#GQP(L,n): tries out p=1, p=2, until either a success or failure. the output should be a list of polynomials in n,let's call it P, such that if n mod p=i (but we take i=1,...p, rather than the usual i=0,..,p-1) then L[n]=P[i][n].

GQP:=proc(L,n) local length,p,tryp:
if not type(n,symbol) then error("n is not a symbol"): fi:
length:=nops(L):
for p from 1 to length do
	tryp:=GQP1(L,p,n):
	if tryp<>FAIL then return(tryp) fi:
od:
FAIL:
end: