# OK to post homework
# Michael Saunders, 9/13/2020, Homework 1

# loading packages
with(combinat):

# 1.0.0
#
print("printing some random stuff..."):
diff(x^6,x);
diff(%,x);
%%;
F := 5:
print("F = ",F):
f := 2:
print("f = ",f):
cheetos := evalb(F = f):
print("evalb(F = f) -> ", cheetos):


# 2.0.0
#
F6_BY_HAND := {[1,1,1,1,1,1], 
	  [1,1,1,1,2], [1,1,1,2,1], [1,1,2,1,1], [1,2,1,1,1], [2,1,1,1,1],
	  [1,1,2,2], [1,2,1,2], [2,1,1,2], [2,1,2,1], [2,2,1,1], [1,2,2,1],
	  [2,2,2]
	 }:
# 3.0.0
#
print("appending to a List in Maple!"):
L1 := [Mercury, Venus, Earth]:
L2 := [op(L1), Mars]:
L1;
L2;
#
# 3.1.0
# Walks(m,n) for m < 0 or n < 0 returns the Empty Set {} due to the nature of
# the recursive steps taken for both m and n (East and North, respectively).
# Walks(m,n) for m >= 0 and n >= 0 begins with the initial values of m and n, and recursively 
# decrements 1 from each value to find all possible paths from [m,n] to [0,0].
# Decrementation is the only defined recursive step in the algorithm. With this 
# procedure as it currently stands, it would be impossible to recursively decrement a negative
# number and get closer to 0 (the Base Case, or Exit Case). 
# Since this behavior is undefined, the Empty Set is returned.
#
# 3.2.0
# Walks(0,0) returns the singleton set {[]} because there does exist a path from [0,0]
# to [0,0], but the list of Walks from those two locations is empty, since they are the same location. 

# 4.0.0
#
# procedure F(n){0 <= n} returns the set of all lists constructed from elements in set {1,2} 
# that add-up to n. E.g. F(3) = {[1,1,1], [1,2], [2,1]}.
F := proc(n) local P, R, i:
	if n < 0 then
		RETURN({}):
	fi:
	if n = 0 then
		RETURN({[]}):
	fi:
	# permute requires second arg <= first.
	# special case for n = 1.
	if n = 1 then
		RETURN({[1]}):
	fi:
	R := {}:
	P := partition(n, 2);
	for i from 1 to nops(P) do
		R := R union {op(permute(P[i]))}:
	end do:
	RETURN(R):
end proc:
F6_BY_CPU := F(6):
print("Is my handwritten F(6) equivalent to the one produced by my Maple Procedure?"):
evalb(F6_BY_HAND minus F6_BY_CPU = F6_BY_CPU minus F6_BY_HAND);

# 5.0.0
#
# procedure NuF(n){0 <= n} returns the number of sets of all lists constructed from elements
# in set {1,2} that add-up to n. I.e. NuF(n) = nops(F(n)).
NuF := proc(n)
	option remember:
	if n < 0 then
		RETURN(0):
	fi:
	if n = 0 or n = 1 then
		RETURN(1):
	fi:
	RETURN(NuF(n-1) + NuF(n-2)):
end proc:

# 5.1.0
#
print("Does nops(F(n)) == NuF(n)?"):
print("n, nops(F(n)), NuF(n), evalb(nops(F(n) = NuF(n))"):
for i from 1 to 10 do
           a := nops(F(i)):
           b := NuF(i):
	print(i, a, b, evalb(a = b)):
end do:

# 5.2.0
#
print("NuF(1000)) = ", NuF(1000)):

# 5.3.0
#
# Maple would complain if you try to evaluate nops(F(n)), because for nops() to count all the lists
# F(1000) makes, F() first has to construct all the lists; it would take too many computing resources.