#OK to post homework
#Kent Mei, 9/20/20, Assignment 3

#---------------------------------
#Part 1
#Bnk(10,5)[20]
#[0, 0, 0, 1, 1, 1, 1, 0, 1, 0]

#MyChoose({1,2,3,4,5,6},2)[5]
#{1, 6}

#MyPermsL([r,u,t,g,e,r,s])[100]
#[r, u, s, t, e, r, g]

#WtoS([1,0,0,0,1])
#{1, 5}

#---------------------------------
#Part 2
NuFP:=proc(pi) local i, ans:
option remember:

ans := 0:

for i from 1 to nops(pi) do
 if pi[i] = i then
  ans++:
 fi:
od:

ans:

end:

#---------------------------------
#Part 3

#Note, uses procedures NuFP, MyPerms, and MyPermsL.

Der:=proc(n) local i, P, Ans:
option remember:

Ans := {}:

P := MyPerms(n):
for i from 1 to nops(P) do
 if NuFP(P[i]) = 0 then
  Ans := {op(Ans), P[i]}
 fi:
od:

Ans:

end:


#---------------------------------
#Part 4

#[seq(nops(Der(i)),i=0..8)];
#[1, 0, 1, 2, 9, 44, 265, 1854, 14833]
#I could find it in the OEIS as the sequence A166.


#---------------------------------
#Part 5

#[seq(nops(Comps(i)),i=1..8)];
#[1, 2, 4, 8, 16, 32, 64, 128].

#A formula I can conjecture for the number of compositions of n is f(n) = 2^(n-1) for n >= 1.

#---------------------------------
#Part 6

#Let f(n) be the number of compositions of n and let g(n) = 2^(n-1). We wish to prove that f(n) = g(n).
#Note that f(1) = 1 since there is only one list of positive integers that add up to 1 (i.e. [1]).
#Also, note that f(n) = 1 + f(1) + f(2) + ... + f(n-1) by construction.
#Now we check to see if g(n) follows the same recurrence relation.
#g(1) = 2^(1-1) = 2^0 = 1 = f(1).
#g(n) = 1 + g(1) + g(2) + ... + g(n-1) 
#     = 1 + 2^0 + 2^1 + ... + 2^(n-2) 
#     = 1 + 1((1-2^(n-1))/(1-2))
#     = 1 + 2^(n-1) - 1
#     = 2^(n-1) as desired.
#Since f(n) and g(n) follow the same recurrence relation, by induction, it means that f(n) = g(n).