#OK to post homework
#Karnaa Mistry, 09/20/20, Assignment HW #3

with(combinat):


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




# 2.

#NuFP(pi): inputs a permutation pi of [1,...,n] and outputs the number of fixed points of pi
NuFP:=proc(pi) local ct,i:
option remember:

ct:=0:

if pi = [] then
 RETURN(0):
fi:

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

ct:
end:




# 3.

#Der(n): inputs a non-negative integer n and outputs the set of derangements of length n
Der:=proc(n) local i,S1,S2:
option remember:

if n<0 then
 RETURN({}):
fi:

if n=0 then
 RETURN({}):
fi:

S1:=MyPerms(n):
S2:={}:

for i from 1 to numelems(S1) do
 if NuFP(S1[i])=0 then
  S2:= S2 union {S1[i]}:
 fi:
od:

S2:

end:




# 4.

# The sequence [seq(nops(Der(i)),i=0..8)] is [0, 0, 1, 2, 9, 44, 265, 1854, 14833].  On OEIS, this does not give
# any results, HOWEVER, if we exclude the first 0 in our search, and only look up [0, 1, 2, 9, 44, 265, 1854, 14833]
# we find "Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points."




# 5.

# [seq(nops(Comps(i)),i=1..8)] gives us [1, 2, 4, 8, 16, 32, 64, 128]
# For n > 0, it appears that the formula for the number of compositions of n is:
# 2^(n-1)




# 6. My attempt at the Optional Challenge:

# We will provide a combinatorial conceptualization to show that for n >= 1 the number of compositions of n is 2^(n-1).

# Take any positive integer n and let b be a binary string of length n with only 0's.
# We want to find the number of ways to 'partition' this string into different non-empty groups of 0's by using 1's.
# The number of 0's within each group can be correspond to a single number in a composition.
#     For example: 00000 partitioned into 0100100 --> [1,2,2]  and  000 partitioned into 01010 --> [1,1,1]
# So, there can never be adjacent 1's, nor 1's at the beginning and/or end of the string (we need non-empty groups of 0's).

# There are n-1 TOTAL places to put 1's in the string so that we have n 0's put into respective groups to correspond to our lists.
#     For example: 0_0_0_0_0 for n = 5, 0_0_0 for n = 3  (1's may be placed between each of the n 0's but not at the ends of the string).
# If we do not place a 1 in a particular spot, we can ignore that spot, as we may have more than one 0's per group.
# If n = 1, then there will be no ways to partition the string using 1's, as we just have a single 0. (There is only one composition of 1).

# For some integer p from [0,n] there are C(n-1,p) ways to place p 1's in those spots, where C(n,k) is "n choose k".
# When p = 0, there are no 1's, and so we have [n] as the composition.
# When p = n-1, there are n-1 1's, and so we have partitioned the 0's into n groups ( ex: {[1,...,1]} )

# We just have to sum C(n-1,p), p from 0 to n-1 to get our answer.  This is representative of the Binomial Theorem, which states:
#   "The sum of C(n,k)*x^k*y^(n-k), k from 0 to n  =  (x + y)^n"
#   In our case, k is p, and "n" is our n-1, and x = y = 1 (power of 1 is always 1)
# Therefore, from the Binomial Theorem, our sum of combinations is equal to (1+1)^(n-1), or 2^(n-1).

# We have found that the number of compositions of n = 2^(n-1) by linking an n-bit string visualization to the Binomial Theorem.












# Maple Code (MyPermsL and MyPerms for reference)

#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: