#OK to post

#Soham Palande, Assignment 3, 09/14/2020


#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(pi): returns the number of fixed points the permutation list pi, in 
NuFP:=proc(pi) local n,i,x:


n:=nops(pi):
x:=0:
if n=0 then
 RETURN(0):
fi:

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

x:

end:


NuFP([1,2,3,4])
4

NuFP([2,1,3,4])
2

NuFP([3,4,1,2])
0


#PART 3

#Der(n): The list of derangements of [1,2..., n]. For example
#Der(2) outputs [[1,2],[2,1]]
Der:=proc(n) local i,L,j,L1:
 L:=MyPermsL([seq(i,i=1..n)]):
 L1:=[]:
 for j from 1 to nops(L) do
    if NuFP(L[j])=0 then
       L1:=[op(L1),L[j]]:
    fi:
 od:
 L1:
end:

Der(2)
[[2, 1]]

Der(3)
[[2, 3, 1], [3, 1, 2]]


#PART 4

[seq(nops(Der(i)),i=0..8)]
[1, 0, 1, 2, 9, 44, 265, 1854, 14833]

#Yes it can be found in OEIS as A000166- subfactorials or recontres numbers


#PART 5

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


# I can conjecture a formula: the number of compositions of n can be given by 2^(n-1)


#PART 6

#To prove that the number of compositions of n, F(n)=2^(n-1)
#We have : F(3)= nops(Comp(3))= nops({[1,1,1],[1,2],[2,1],[3]})= 4
#           F(2)= nops(Comp(2))= nops({[2], [1, 1]})= 2
#           F(3)=F(2)*2

#Let G(n)=2^(n-1)

#Proof:
# Induction on n 
# By inductive hypothesis, we assume 
# F(n-1)=2^(n-1-1)
#Then we know that 
#F(n)=F(n-1) * 2
#F(n)=2 * 2^(n-2)
#F(n)= 2^(n-1)
#F(n)=G(n)

#Therefore, the number of compositions of n can be given by F(n)=2^(n-1)