#OK to post homework
#Blair Seidler, 2021-02-21 Assignment 8

with(combinat):

Help:=proc(): print(`SPnF(n), NuConnLabGr(N),NuCG(n,k)`): end:

# 1.

#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 P,i,j,FriendSets,S,EnemyParts,nEnemies,EP:
option remember:
if n=0 then
 RETURN({{}}):
fi:

P:={}:

for i from 0 to n-1 do
  FriendSets:=Snk(n-1,i):
  for S in FriendSets do
    nEnemies:=sort(convert({seq(i1,i1=1..n-1)} minus  S,list)):
    EnemyParts:=subs( {seq(j=nEnemies[j],j=1..n-1-i)}  , SPnF(n-1-i)):
    for EP in EnemyParts do
      P:={op(P),EP union { {n} union S}}:
    od:
  od:
od:
P:
end:

# 3.

#NuConnLabGr(N): The number of connected labelled graphs on n vertices
#outputs values for n=1..N
NuConnLabGr:=proc(N) local x,f:
 
f := taylor(log(Sum(2^(n*(n - 1)/2)*x^n/n!, n = 0 .. infinity)), x = 0, N+1):

[seq(i!* coeff(f,x,i),i=1..N)]:

end:

#[1, 1, 4, 38, 728, 26704, 1866256, 251548592, 66296291072, 34496488594816, 35641657548953344,
#73354596206766622208, 301272202649664088951808, 2471648811030443735290891264,
#40527680937730480234609755344896, 1328578958335783201008338986845427712,
#87089689052447182841791388989051400978432, 11416413520434522308788674285713247919244640256,
#2992938411601818037370034280152893935458466172698624,
#1569215570739406346256547210377768575765884983264804405248,
#31645471602537064877722485517800176164374001516327306287561310208, 
#3450836972295011606260171491426093685143754611532806996347023345844224, 
#14473931784581530777452916362195345689326195578125463551466449404195748970496, 
#121416458387840348322477378286414146687038407628418077332783529218671227143860518912, 
#2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472, 
#68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896, 
#4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344,
#615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208,
#165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128,
#88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584]

#Comfortingly, these numbers are A001187: Number of connected labeled graphs with n nodes.

# 4.

# I had to spend some time buried in chapter 3 of generatingfunctionology, but I think
# I'm convinced now

# 5.

#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 N,f,t:
f:=log(Sum((1+a)^(N*(N-1)/2)*x^N/N!,N=0..infinity)):

t:=taylor(f,x=0,n+1):

coeff(n!*coeff(t,x,n),a,k):

end:

#seq(NuCG(n, n - 1), n = 1 .. 20) is
#1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 
# 2357947691, 61917364224, 1792160394037, 56693912375296, 
# 1946195068359375, 72057594037927936, 2862423051509815793, 
# 121439531096594251776, 5480386857784802185939, 262144000000000000000000

#Again comfortingly, this is A000272: Number of trees on n labeled nodes: n^(n-2) 

#Now for seq(NuCG(n,n+r),n=1..20):
#r=0:  A057500		Number of connected labeled graphs with n edges and n nodes.
#r=1:  A061540		Number of connected labeled graphs with n nodes and n+1 edges.
#r=2:  A061541		Number of connected labeled graphs with n nodes and n+2 edges.
#r=3:  A061542		Number of connected labeled graphs with n nodes and n+3 edges.
#r=4:  A061543		Number of connected labeled graphs with n nodes and n+4 edges.
#r=5:  A096117		Number of connected labeled graphs with n nodes and n+5 edges.
#r=6:  A061544		Number of connected labeled graphs with n nodes and n+6 edges.
#r=7:  A096150		Number of connected labeled graphs with n nodes and n+7 edges.
#r=8:  A096224		Number of connected labeled graphs with n nodes and n+8 edges.
#r=9:  A182294		Number of connected labeled graphs with n nodes and n+9 edges
#r=10: A182295		Number of connected labeled graphs with n nodes and n+10 edges.
#r=11: A182371		Number of connected labeled graphs with n nodes and n+11 edges.
#r=12: This is the first one not already in the OEIS

#### Imported from C4.txt ####
#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: