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

#I originally misinterpreted
#"the partial sums are positive, or zero, but the previous partial sum is positive."
#as
#"(the partial sums are positive, or zero), but the previous partial sum is positive."
#This is the result.  I was able to get formulas for P and Q, but
#I could not do anything with generating functions to prove them

#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:
    s:=0:
    ct:=0:
    for i from 1 to nops(w)-1 do
        s:=s+w[i]:
        if s > 0 then
            ct:=ct+1:
        fi:
    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)=(1+t)*add(add(C(n-1-k)*C(k), k=0..m)*t^(2*n-2-2*m), m=0..n-1)
#where C(n)=(1/(n+1))*binomial(2n,n) is the nth Catalan number
#(based on A028364 in OEIS)

##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: Q(n, t)=add(2*binomial(n-i-1, floor((n-i-1)/2))*binomial(i-1, floor((i-1)/2))*t^i, i=0..n-1)
#(based on A063886 in OEIS)

##PROBLEM 5##

#After much failure, this is when I realized I must have misinterpreted the problem