#OK to post homework
#George Spahn, 2/21/2021, Assignment 8

#SPnF(n) inputs a non-neg. integer n and outputs the set of set-partitions
# of {1,..,n} using the NEW approach (the one used in NuSPnF(n) and RandSPn(n)

SPnF:=proc(n) local k,S,SP1,enemies,L,j,SP2,S1,l:
if n=0 then
 RETURN({{}}):
fi:
L:={}:

for k from 0 to n-1 do
 SP1:=SPnF(n-1-k): 

 S1:=Snk(n-1,k):
 for S in S1 do
  enemies:=sort(convert({seq(i1,i1=1..n-1)} minus S,list)): 
  SP2:=subs( {seq(j=enemies[j],j=1..nops(enemies))}  , SP1):
  for l in SP2 do
   L:=L union {l union {S union {n}}}:
  od:  
 od:
od:
L:
end:


# The number of connected labeled graphs is given by A001187


#NuCG(n,k) inputs positive integers n and k, and outputs the number 
#of labelled connected graphs with n vertices and k edges.
NuCG:=proc(n,k) local t,c1:
t:=taylor(log(Sum((1 + a)^(n1*(n1 - 1)/2)*x^n1/n1!, n1 = 0 .. infinity)), x = 0, n+1):
c1:=coeff(t,x,n)*n!:
coeff(c1,a,k):
end:


#5(i) This is the number of labeled trees and is given by A000272
#5(ii) The first one not in the OEIS was r=13.

#Snk(n,k): Inputs NON-NEG. integer n and an integer k and OUTPUTS
#THE SET OF k-element subsets of {1,...,n}
#FOR EXAMPLE
#Snk(3,2) should be {{1,2},{1,3},{2,3}}
Snk:=proc(n,k) local S1,S2,s:
option remember:

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

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

S1:=Snk(n-1,k):
S2:=Snk(n-1,k-1):
S1 union {seq( s union {n}, s in S2)}:
end: