OK to post

#Question 1
#Carefully study the Maple code for lecture 3 and find
#Bnk(10,5)[20]
#MyChoose({1,2,3,4,5,6},2)[5]
#MyPermsL([r,u,t,g,e,r,s])[100]
#WtoS([1,0,0,0,1])

#Answer to question 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}

#Question 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 count, ans, i; 
count := 1; ans := 0; 
for i in pi do 
if count = i 
then ans := ans + 1; 
end if; 
count := count + 1; 
end do; 
ans; 
end proc


#Question 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]}

#The answer is as follows. I also used the NuFP function. Hope that is ok, 

Der := proc(n) local l1, ans, i; 
l1 := MyPerms(n); 
ans := {}; 
for i in l1 
do if NuFP(i) = 0 then 
ans := {op(ans), i}; 
end if; 
end do;
ans
end proc



#Question 4
#What is the sequence [seq(nops(Der(i)),i=0..8)]?
[seq(nops(Der(i)),i=0..8)]=[1, 0, 1, 2, 9, 44, 265, 1854, 14833]

#Found it on OEIS:
A166
Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.


#Question 5

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

#Can you conjecture a formula for the number of compositions of n?

#Answer to question 5:

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

My conjecture for the formula for number of compositions of n is = 2^n-1