#Nathan Fox
#Homework 15
#I give permission for this work to be posted online

#Read packages
with(`LinearAlgebra`):

#Read procedures from class
read(`C15.txt`):

#Help procedure
Help:=proc():
    print(` Happy(w) , P(n, t) , Q(n, t) `):
end:

##PROBLEM 2##

#Happy(w): inputs a sequence in {-1,1} and outputs the number of
#places where the partial sums are positive, or zero, but the
#previous partial sum is positive.
Happy:=proc(w) local s, ct, i, prev:
    s:=0:
    ct:=0:
    prev:=0:
    for i from 1 to nops(w) do
        s:=s+w[i]:
        if s > 0 or (s = 0 and prev > 0) then
            ct:=ct+1:
        fi:
        prev:=s:
    od:
    return ct:
end:

##PROBLEM 3##

#P(n, t): inputs a positive integer n, and outputs the sum of
#t^Happy(w) over all sequences with n 1's and n -1's.
P:=proc(n, t) local w:
    return add(t^Happy(w), w in AllWalks(n, n)):
end:

#Conjecture: P(n, t)=C(n)*add(t^(2*i), i=0..n)
#where C(n)=(1/(n+1))*binomial(2n,n) is the nth Catalan number

##PROBLEM 4##

#Q(n, t): inputs a positive integer n, and outputs the sum of
#t^Happy(w) over all sequences in {1,-1} of length n (i.e.
#AllWalks(n,0) union AllWalks(n-1,1) ... union AllWalks(0,n))
Q:=proc(n, t) local w, i:
    return add(t^Happy(w), w in `union`(seq(AllWalks(i, n-i), i=0..n))):
end:
#Conjecture: If n is even, Q(n, t)=add(binomial(2*k,k)*binomial(n-2*k,n/2-k)*t^(2*k), k=0..n/2):
#(based on A67804 in OEIS)
#If n is odd, then Q(n, t)=t^n*Q(n, 1/t),
#and the t^0 coefficient is binomial(n, (n-1)/2),
#and the t^1 coefficient is 1/n*binomial(n, (n-1)/2),
#and the t^2 coefficient is (n-1)/(2*n)*binomial(n, (n-1)/2)
#and the central coefficients are binomial(floor(n/2), floor(n/4))^2
#I see patterns in the other coefficients, but I can't find a
#formula, and these coefficient sequences are not in OEIS

##PROBLEM 5##

#See hw15.pdf for a proof of P(n, t) and a generating function that
#gives Q(n, t) (but no proof, since I don't have a conjecture)