#M3.txt: Maple Code for Lecture 3 of Math 454,Combinatorics, Rutgers University, taught by Dr. Z. (Doron Zeilberger)
Help3:=proc():print(` Bn(n), Bnk(n,k), MyPowerSet(S), MyChoose(S,k) , MyPermsL(L), MyPerms(n), WtoS(w), StoW(S,n), Comps(n)  `): end:

with(combinat):

#Bn(n): The set of words (i.e. lists) of lenght n, in the "alphabet" {0,1}
Bn:=proc(n) local S,s:
option remember:
if n=0 then
 RETURN({[]}):
fi:
S:=Bn(n-1):
{seq([op(s),0],s in S), seq([op(s),1],s in S)}:
end:


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


#MyPowerSet(S): An home-made version of Maple's command combinat[powerset](S)
#For example
#MyPowerSet({a,b})={{},{a},{b},{a,b}} .
MyPowerSet:=proc(S) local a,S1,P1,s:
option remember:
if S={} then
 RETURN({{}}):
fi:
a:=S[1]:
S1:=S minus {a}:
P1:=MyPowerSet(S1):

P1 union {seq(s union {a}, s in P1)}:

end:


#MyChoose(S,k): An home-made version of Maple's command combinat[choose](S,k)
#In other words, it inputs a finite set S and a non-negative integer k, and outputs
#the set of subsets of S with k elements.
#For example
#MyChoose({a,b},1)={{a},{b}} .
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.  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:


#WtoS(w): inputs a word in {0,1} outputs the correpsonding subset of {1,...,n} (where n=nops(w))
#For example
#WtoS([0,1,0,1]); should output {2,4}
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:

#StoW(S,n): inputs a subset S of {1,...,n} and outputs the corresponding binary word
StoW:=proc(S,n) local i,w:

if S  minus {seq(i,i=1..n)}<>{} then
 print(S, `is not a subset of`,  {seq(i,i=1..n)} ):
 RETURN(FAIL):
fi:

w:=[]:

for i from 1 to n do
 
if member(i,S) then
  w:=[op(w),1]:
else
  w:=[op(w),0]:
fi:

od:

w:

end:


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