#OK to post
#Michael Yen, 9/20/20, Assignment 3

#1.Carefully study the Maple code for lecture 3 and find
#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}

#2.Given a permutation, pi=[pi[1], ..., pi[n]], a location i, between 1 and n is called a 
#FIXED POINT if pi[i]=i.
#write a procedure

#NuFP(pi)

#That inputs a permutation pi of [1,...,n] and outputs the NUMBER of Fixed points of pi. 
#For example
#NuFP([1,2,3,4])=4 (Since pi[1]=1, pi[2]=2, pi[3]=3, pi[4]=4,)   NuFP([2,1,3,4])=2 (since 
#pi[3]=3, pi[4]=4, but pi[1] != 1, pi[2]!=2)   NuFP([3,4,1,2])=0  

NuFP:=proc(pi) local i,n:
option remember:

n:=0:

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

n:

end:

#3. A permutation is called a derangement if it has no fixed points. For example [2,3,1] is 
#a derangement. Use procedure MyPerms(n) in M3.txt to write a procedure

#Der(n)

#That inputs a non-negative integer n and outputs the SET of derangements of length n.
#For example, Der(2)={[2,1]}, Der(3)={[2,3,1], [3,1,2]}

Der:=proc(n) local i,p,S:
S:={}:
p:=MyPermsL([seq(i,i=1..n)]):
for i from 1 to nops(p) do
  if NuFP(p[i])=0 then
    S:=S union {p[i]}:
  fi:
od:
S:
end:

#4. What is the sequence [seq(nops(Der(i)),i=0..8)]?
#Can you find it in the OEIS?

#The sequence is [1, 0, 1, 2, 9, 44, 265, 1854, 14833].
#It is in the OEIS as sequence A000166: the subfactorial or rencontres numbers, or 
#derangements: number of permutations of n elements with no fixed points.

#5. Study the code for Comps(n) and understand it. What is
#[seq(nops(Comps(i)),i=1..8)]?

#It is the following sequence: [1, 2, 4, 8, 16, 32, 64, 128]. This is the powers of 2, as you
#can see - 2^0, 2^1, 2^2, 2^3... and so on.

#Can you conjecture a formula for the number of compositions of n?
#The number of compositions of n is 2^n.

#6. [Optional Challenge] PROVE IT!