#OK to post homework
#Wanying Rao, 03/07/2021, Assignment 12

#1
PnkC := proc(n,k,S,m)local k1,L,L1:
option remember:

if not (type(n,integer) and type(k,integer) and type(m, integer) and type(S,set) and n>=1 and k>=1 and m>=1)then
 RETURN([]):
fi:
 
if k>n then
 RETURN([]):
fi:

if k=n then
 RETURN([[n]]):
fi:

if not k mod m in S then
 RETURN([]):
fi:


if not S subset {seq(i,i=0..m-1)} then
 RETURN([]):
fi:

L:=[]:

for k1 from min(n-k,k) by -1 to 1 do
 if k1 mod m in S then 
  L1:=PnkC(n-k,k1,S,m):
  L:=[op(L), seq([k, op(L1[j])],j=1..nops(L1))]:
 fi:
od:

L:
end:



PnC := proc(n,S,m) local k:
option remember:

if not (type(n,integer) and type(m, integer) and type(S,set) and n>=1 and m>=1)then
 RETURN([]):
fi:

if not S subset {seq(i,i=0..m-1)} then
 RETURN([]):
fi:

[seq(op(PnkC(n,n-k+1,S,m)),k=1..n)]:
end:



RandPnkC := proc(n,k,S,m) local k1,L,c:

if not (type(n,integer) and type(k,integer) and type(S,set) and type(m, integer) and n>=1 and k>=1 and m>=1)then
 RETURN(FAIL):
fi:
 
if k>n then
 RETURN(FAIL):
fi:

if k=n then
 RETURN([n]):
fi:

if not k mod m in S then
 RETURN(FAIL):
fi:


if not S subset {seq(i,i=0..m-1)} then
 RETURN(FAIL):
fi:

L:=[seq(0,i=1..min(n-k,k))]:

for k1 from min(n-k,k) by -1 to 1 do
 if k1 mod m in S then
  L[k1] := pnkC(n-k,k1,S,m):
 fi:
od:

c := LD(L):
[k,op(RandPnkC(n-k,c,S,m))]:
end:



RandPnC := proc(n,S,m) local L,c,k:

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

L := [seq(pnkC(n,k,S,m),k=1..n)]:
c := LD(L):

RandPnkC(n,c,S,m):
end:



pnkC := proc(n,k,S,m) local k1:
option remember:

if not (type(n,integer) and type(k,integer) and type(S,set) and type(m, integer) and n>=1 and k>=1 and m>=1)then
 RETURN(0):
fi:

if k>n then
 RETURN(0):
fi:

if not k mod m in S then
 RETURN(0):
fi:


if not S subset {seq(i,i=0..m-1)} then
 RETURN(0):
fi:

if n=k then
 RETURN(1):
else
 RETURN(add(pnkC(n-k,k1,S,m),k1=1..min(k,n-k))):
fi:

end:


pnC := proc(n,S,m) local k: 
option remember: 

if not (type(n,integer) and type(S,set) and type(m, integer) and n>=1 and m>=1)then
 RETURN(0):
fi:

if not S subset {seq(i,i=0..m-1)} then
 RETURN(0):
fi:

if n=0 then
 RETURN(1):
fi:

add(pnkC(n,k,S,m),k=1..n):
end:



#2
PnkD := proc(n,k,DI)local k1,L,L1:
option remember:

if not (type(n,integer) and type(k,integer) and type(DI,set) and n>=1 and k>=1)then
 RETURN([]):
fi:
 
if k>n then
 RETURN([]):
fi:

if k=n then
 RETURN([[n]]):
fi:

L:=[]:

for k1 from min(n-k,k) by -1 to 1 do
 if not k-k1 in DI then
  L1:=PnkD(n-k,k1,DI):
  L:=[op(L), seq([k, op(L1[j])],j=1..nops(L1))]:
 fi:
od:

L:
end:



PnD := proc(n,DI) local k:
option remember:

if not (type(n,integer) and type(DI,set) and n>=1)then
 RETURN([]):
fi:


[seq(op(PnkD(n,n-k+1,DI)),k=1..n)]:
end:



RandPnkD := proc(n,k,DI) local k1,L,c:

if not (type(n,integer) and type(k,integer) and type(DI,set) and n>=1 and k>=1)then
 RETURN(FAIL):
fi:
 
if k>n then
 RETURN(FAIL):
fi:

if k=n then
 RETURN([n]):
fi:

L:=[seq(0,i=1..min(n-k,k))]:

for k1 from min(n-k,k) by -1 to 1 do
 if not k-k1 in DI then
  L[k1] := pnkD(n-k,k1,DI):
 fi:
od:

c := LD(L):
[k,op(RandPnkD(n-k,c,DI))]:
end:

RandPnD := proc(n,DI) local L,c,k:

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

L := [seq(pnkD(n,k,DI),k=1..n)]:
c := LD(L):

RandPnkD(n,c,DI):
end:

pnkD := proc(n,k,DI) local k1,s:
option remember:

if not (type(n,integer) and type(k,integer) and type(DI,set) and n>=1 and k>=1)then
 RETURN(0):
fi:

if k>n then
 RETURN(0):
fi:

if n=k then
 RETURN(1):
fi:

s := 0:
for k1 from min(n-k,k) by -1 to 1 do
 if not k-k1 in DI then
  s := s + pnkD(n-k,k1,DI):
 fi:
od:

s:
end:

pnD := proc(n,DI) local k: 
option remember: 

if not (type(n,integer) and type(DI,set) and n>=1)then
 RETURN(0):
fi:

if n=0 then
 RETURN(1):
fi:

add(pnkD(n,k,DI),k=1..n):
end:

#3
#[seq(pnC(n,{1},2),n=1..30)]
#[1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, #142, 165, 192, 222, 256, 296]
#A117409

#[seq(pnC(n,{1},2),n=1..30)]
#[1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 31, 35, 41, 46, 54, 61, #70, 79, 91, 102, 117]
#A003114

#[seq(pnD(n,{0}),n=1..30)]
#[1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, #142, 165, 192, 222, 256, 296]
#A000009

#[seq(pnD(n,{0,1}),n=1..30)]
#[1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 12, 14, 17, 19, 23, 26, 31, 35, 41, 46, 54, 61, 70, 79, 91, 102, 117]
#A003114