> #Weiji Zheng, 09/22/2020, Assignment 3
;
> #OK to post homework
;
> 
;
> #Q1
;
> 
;
> #Bnk(n,k): The set of words (i.e. lists) of lenght n, in the "alphabet" {0,1} with EXACTLY k 1's
;
> Bnk:=proc(n,k) local S1,S2,s:
> option remember:
> if n=0 then
>  if k=0 then
>   RETURN({[]}):
>  else
>   RETURN({}):
>  fi:
> fi:
> S1:=Bnk(n-1,k):
> S2:=Bnk(n-1,k-1):
> {seq([op(s),0],s in S1), seq([op(s),1],s in S2)}:
> end:
> #MyChoose(S,k): An home-made version of Maple's command combinat[choose](S,k)
;
> MyChoose:=proc(S,k) local a,S1,s,P1,P2:
> option remember:
> if S={} then
>  if k=0 then
>   RETURN({{}}):
>   else
>    RETURN({}):
>  fi:
> fi:
> a:=S[1]:
> S1:=S minus {a}:
> P1:=MyChoose(S1,k):
> P2:=MyChoose(S1,k-1):
> 
> P1 union {seq(s union {a}, s in P2)}:
> 
> end:
> #MyPermsL(L): The list of permutations in the list L, in LEXICOGRAPHIC order given by L.
;
> 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:

> #WtoS(w): inputs a word in {0,1} outputs the correpsonding subset of {1,...,n} (where n=nops(w))
;
> WtoS:=proc(w) local n,i,S:
> 
> n:=nops(w):
> 
> S:={}:
> 
> for i from 1 to n do
>  if w[i]=1 then
>   S:=S union {i}:
>  fi:
> od:
> 
> S:
> 
> end:

> #Answer
;
> 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}
;
> 
;
> #Q2
;
> 
;
> #NuFP(pi)-> inputs a permutation pi of [1,...,n] and outputs the NUMBER of Fixed points of pi.
;
> 
;
> NuFP := proc(Pi) local n, i, count:
> n := nops(Pi):
> count :=0:
> for i from 1 to n do
>   if Pi[i] = i then
>      count := count+1:
>   fi:
> od:
> 
> count:
> 
> end:
> NuFP([1,2,3,4])
4
;
> NuFP([3,2,3,5])
2
;
> NuFP([3,4,1,2])
0
;
> #Succeed
;
> 
;
> #Q3
;
> 
;
> MyPerms:=proc(n) local i:
>  MyPermsL([seq(i,i=1..n)]):
> end:
> 
> Der:=proc(n) local L,i,S:
> S:={}:
> L:=MyPerms(n):
> for i from 1 to (nops(L)) do
>   if NuFP(L[i])=0 then
>     S:=S union {L[i]}:
>   fi:
> od:
> S:
> end:
> 
;
> Der(4)
{[2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2], [4, 3, 2, 1]}
;
> #Succeed
;
> 
;
> #Q4
;
> 
;
> #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]
;
> #Yes.Search it on OEIS i get 
;
> #A000166
;
> #Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.(Formerly M1937 N0766)

;
> 
;
> #Q5
;
> 
;
> #Comps(n): The set of compositions of n, i.e. the set of lists of POSITIVE integers that add-up to n.
;
> 
;
> 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:
> 
;
> Comps(3)
{[3], [1, 2], [2, 1], [1, 1, 1]}
;
> Comps(8)
{[8], [1, 7], [2, 6], [3, 5], [4, 4], [5, 3], [6, 2], [7, 1], [1, 1, 6], [1, 2, 5], [1, 3, 4], [1, 4, 3], [1, 5, 2], [1, 6, 1], [2, 1, 5], [2, 2, 4], [2, 3, 3], [2, 4, 2], [2, 5, 1], [3, 1, 4], [3, 2, 3], [3, 3, 2], [3, 4, 1], [4, 1, 3], [4, 2, 2], [4, 3, 1], [5, 1, 2], [5, 2, 1], [6, 1, 1], [1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 1, 4, 2], [1, 1, 5, 1], [1, 2, 1, 4], [1, 2, 2, 3], [1, 2, 3, 2], [1, 2, 4, 1], [1, 3, 1, 3], [1, 3, 2, 2], [1, 3, 3, 1], [1, 4, 1, 2], [1, 4, 2, 1], [1, 5, 1, 1], [2, 1, 1, 4], [2, 1, 2, 3], [2, 1, 3, 2], [2, 1, 4, 1], [2, 2, 1, 3], [2, 2, 2, 2], [2, 2, 3, 1], [2, 3, 1, 2], [2, 3, 2, 1], [2, 4, 1, 1], [3, 1, 1, 3], [3, 1, 2, 2], [3, 1, 3, 1], [3, 2, 1, 2], [3, 2, 2, 1], [3, 3, 1, 1], [4, 1, 1, 2], [4, 1, 2, 1], [4, 2, 1, 1], [5, 1, 1, 1], [1, 1, 1, 1, 4], [1, 1, 1, 2, 3], [1, 1, 1, 3, 2], [1, 1, 1, 4, 1], [1, 1, 2, 1, 3], [1, 1, 2, 2, 2], [1, 1, 2, 3, 1], [1, 1, 3, 1, 2], [1, 1, 3, 2, 1], [1, 1, 4, 1, 1], [1, 2, 1, 1, 3], [1, 2, 1, 2, 2], [1, 2, 1, 3, 1], [1, 2, 2, 1, 2], [1, 2, 2, 2, 1], [1, 2, 3, 1, 1], [1, 3, 1, 1, 2], [1, 3, 1, 2, 1], [1, 3, 2, 1, 1], [1, 4, 1, 1, 1], [2, 1, 1, 1, 3], [2, 1, 1, 2, 2], [2, 1, 1, 3, 1], [2, 1, 2, 1, 2], [2, 1, 2, 2, 1], [2, 1, 3, 1, 1], [2, 2, 1, 1, 2], [2, 2, 1, 2, 1], [2, 2, 2, 1, 1], [2, 3, 1, 1, 1], [3, 1, 1, 1, 2], [3, 1, 1, 2, 1], [3, 1, 2, 1, 1], [3, 2, 1, 1, 1], [4, 1, 1, 1, 1], [1, 1, 1, 1, 1, 3], [1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 3, 1], [1, 1, 1, 2, 1, 2], [1, 1, 1, 2, 2, 1], [1, 1, 1, 3, 1, 1], [1, 1, 2, 1, 1, 2], [1, 1, 2, 1, 2, 1], [1, 1, 2, 2, 1, 1], [1, 1, 3, 1, 1, 1], [1, 2, 1, 1, 1, 2], [1, 2, 1, 1, 2, 1], [1, 2, 1, 2, 1, 1], [1, 2, 2, 1, 1, 1], [1, 3, 1, 1, 1, 1], [2, 1, 1, 1, 1, 2], [2, 1, 1, 1, 2, 1], [2, 1, 1, 2, 1, 1], [2, 1, 2, 1, 1, 1], [2, 2, 1, 1, 1, 1], [3, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 2, 1], [1, 1, 1, 1, 2, 1, 1], [1, 1, 1, 2, 1, 1, 1], [1, 1, 2, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1]}
;
> nops(Comps(1))
1
;
> nops(Comps(2))
2
;
> nops(Comps(8))
128
;
> [seq(nops(Comps(i)),i=1..8)]
[1, 2, 4, 8, 16, 32, 64, 128]
;
> #I easily find the numbers are all power of 2, so I believe the formula is nops(Comps(i))  =  2^(i-1)
;
> 
;
> 
;
Warning, premature end of input, use <Shift> + <Enter> to avoid this message.
;