# OK to post homework
# Michael Saunders, 9/20/2020, Homework 3
#

# load packages
#
with(combinat):



# 1. 
#    Carefully study the Maple code for lecture 2 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,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}
#
#    > MyPerms([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,2,...,n] and outputs the NUMBER of FIXED POINTs of pi.
#    
NuFP := proc(pi) local i, r:
    r := 0:
    for i from 1 to nops(pi) do
        if pi[i] = i then
            r := r+1:
        fi:
    end do:
    RETURN(r):
end proc:

#    Test procedure NuFP(pi) with examples given in assignment description:
#
print("2:"):
print("NuFP([1,2,3,4]) --> ",NuFP([1,2,3,4])):
# 4
print("NuFP([2,1,3,4]) --> ", NuFP([2,1,3,4])):
# 2
print("NuFP([3,4,1,2]) --> ", NuFP([3,4,1,2])):
# 0



# 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) from M3.txt to write a procedure Der(n) that inpute a non-negative integer n and
#    outputs the SET of derangements of length n.
#    e.g. Der(2) = {[2,1]} and Der(3) = {[2,3,1], [3,1,2]}.

#    MyPermsL(L): The list of permutations in the list L, in LEXICOGRAPHIC order given by L.  For example,
#    MyPermsL([1,2]) outputs [[1,2],[2,1]].
#
MyPermsL:=proc(L) local n,PL,PL1,i,p:
    option remember:
    n:=nops(L):
    if n=0 then
        RETURN([[]]):
    fi:
    PL:=[]:
    for i from 1 to nops(L) do
        PL1:=MyPermsL([op(1..i-1,L),op(i+1..n,L)]):
        PL:=[op(PL),seq([L[i],op(p)], p in PL1)]:
    od:
    PL:
end:

#    MyPerms(n): The list of permutations of [1,2..., n]. For example
#    MyPerms(2) outputs [[1,2],[2,1]].
#
MyPerms:=proc(n) local i:
    MyPermsL([seq(i,i=1..n)]):
end:

#    Procedure isDer(L) inputs a list L, returns L if the list is a derangement and empty-set otherwise.
#
isDer(L) := proc(L) local i:
    for i from 1 to nops(L) do
        if L[i] = i then
            print("deranged!"):
        fi:
    end do:
    RETURN(L):
end proc:

#    This is my Der(n) procedure as described above...
#
Der := proc(n) local L, S, i:
    if n < 0 then
        RETURN({}):
    elif n = 0 then
        RETURN({[]}):
    fi:
    L := MyPerms(n):
    S := {}:
    for i from 1 to nops(L) do
        if NuFP(L[i]) <> 0 then
            next:
        fi:
        S := S union {L[i]}:
    end do:
    RETURN(S):    
end proc:

#    Test procedure Der(n) with examples given in assignment description:
#
print("3:"):
tmp := Der(2):
print("Der(2) --> ", tmp):
# tmp = {[2, 1]}
tmp := Der(3):
print("Der(3) --> ", tmp):
# tmp = {[2, 3, 1], [3, 1, 2]}



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

#    Can you find it in the OEIS?
#
#    Yes, I found the sequence [1, 0, 1, 2, 9, 44, 265, 1854, 14833] in the OEIS. 
#    It is the "Subfactorial or recontres numbers, or number of derangements of n elements."
#    This verifies my Der(n) procedure is correct.



# 5.
#    Study the code for Comps(n) and understand it.
#    What is [seq(nops(Comps(i)),i=1..8)]?
#
#    Comps(n): The set of compositions of n, i.e. the set of lists of POSITIVE integers that add-up to n.
#    For example,
#    Comps(3) should output {[1,1,1],[1,2],[2,1],[3]});

#
Comps:=proc(n) local S,S1,i,s:
    option remember:
    if n<0 then
        RETURN({}):
    fi:
    if n=0 then
        RETURN({[]}):
    fi:
    S:={}:
    for i from 1 to n do
        S1:=Comps(n-i):
        S:=S union {seq( [op(s),i], s in S1)}:
    od:
    S:
end:

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

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

#    Comp(n) = 2^(n-1) for all n > 0.



# 6.
#    Prove Comp(n) = 2^(n-1)

#    Proof by Maple Procedure:
#
#    Procedure ProveComp(n) computes the conjecture I made: Comp(n) = 2^(n-1).
#
ProveComp := proc(n)
    RETURN(2^(n-1)):
end proc:

#   compare [1, 2, 4, 8, 16, 32, 64, 128] to my procedure
#
print("6:"):
for i from 1 to 8 do
    print("i = ", i, " evalb(ProveComp(i) = nops(Comps(i))? -- ", evalb(ProveComp(i) = nops(Comps(i)))):
od:
# true
# true
# true
# true
# true
# true
# true
# true