#!/usr/local/bin/maple
#-*- maplev -*-

# Nathaniel Shar
# HW 25
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

Help := proc(): print(`Edges(n), Graphs(n), Neis(G,i), CC(G,Erdos), IsCon(G,n), ConG(n), NuCCSeqSlow(N), NuCCSeqFast(N), LabTrees(n), NuLabTreesSlow(N), WtCCSeqFast(N,y), LabAlmostTrees(n, a), NuLabAlmostTreesSlow(N, a), NuLabAlmostTreesFast(N, a), Image(G, n, pi), ULG(n, func), ConULG(n), Count(N, func), NuConULGSeqSlow(N), ULTrees(n), NuULTreesSeqSlow(N), ULAlmostTrees(n, a), NuULAlmostTreesSeqSlow(N, a)`): end:

#############
# Problem 1 #
#############

# Technically I have a Facebook account, but I don't ever use it.

# Therefore, the largest influence on the Facebook distance between me
# and Dr. Z is the weight of the edge between me and Facebook, which
# is large.

#############
# From c25:

with(combinat):

#Edges(n): the set of all edges of K_n
Edges:=proc(n) local i,j:

    {seq(seq({i,j},i=1..j-1),j=2..n)}:
end:

#Graphs(n): ALL graphs on {1, ..., n}
Graphs:=proc(n): powerset(Edges(n)):end:


#Neis(G,i): inputs a graph G (given as a set of edges,
#and every edge is given a 2-set) and outputs all
#the vertices adjacent to it (i.e. all j such that
#{i,j} is in G
Neis:=proc(G,i) local N,e:
option remember:
    N:={}:

    for e in G do
        if member(i,e) then
            N:=N union (e minus {i}):
        fi:
    od:

    N:

end:


#CC(G,Erdos): the connected component of vertex Erdos in graph G
CC:=proc(G,Erdos) local C1,NewF,v:

    C1:={Erdos}:
    NewF:=Neis(G,Erdos):

    while NewF minus C1<>{} do

        C1:=C1 union NewF:

        NewF:= `union`(seq(Neis(G,v), v in NewF)):
    od:

    C1:

end:

#IsCon(G,n): Is the graph G on {1, ..., n} connected?
IsCon:=proc(G,n): evalb(nops(CC(G,1))=n): end:

#the set of all connected labelled graphs  on {1, ..., n}
ConG:=proc(n) local ConGraphs, AllGraphs, G:

    AllGraphs:=Graphs(n):

    ConGraphs:={}:


    for G in AllGraphs do
        if IsCon(G,n) then
            ConGraphs:=ConGraphs union {G}:
        fi:
    od:

    ConGraphs:

end:


#The first N terms of sequence A001187 by the SLOW way
#(But slow is not always stupid)
NuCCSeqSlow:=proc(N) local i:
    [seq(nops(ConG(i)),i=1..N)]:
end:

# NuCCSeqFast(N):
#The first N terms of sequence A001187 by the FAST way
#(using exponential generatingfunctionology)

NuCCSeqFast:=proc(N) local i,x,F:

    F:=taylor(log(add(x^i*2^(binomial(i,2))/i!,i=0..N)), x=0, N+1):

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

end:


#the set of all labelled trees  on {1, ..., n}
LabTrees:=proc(n) local ConGraphs, AllGraphs, G:

    AllGraphs:=choose(Edges(n),n-1) :

    ConGraphs:={}:


    for G in AllGraphs do
        if IsCon(G,n) then
            ConGraphs:=ConGraphs union {G}:
        fi:
    od:

    ConGraphs:

end:

#The first N terms of the number of labelled trees
#sequence by the SLOW way
#(But slow is not always stupid)
NuLabTreesSlow:=proc(N) local i:
    [seq(nops(LabTrees(i)),i=1..N)]:
end:

# WtCCSeqFast(N,y):
#The first N terms of the weight-enumerator of
#all connected graphs according to the weight
#y^(#edges) the FAST way
#(using exponential generatingfunctionology)

WtCCSeqFast:=proc(N,y) local i,x,F:

    F:=taylor(log(add(x^i*(1+y)^(binomial(i,2))/i!,i=0..N)), x=0, N+1):

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

end:

#############

#############
# Problem 2 #
#############

LabAlmostTrees:=proc(n, a) local ConGraphs, AllGraphs, G:
    AllGraphs:=choose(Edges(n),n+a-1) :
    ConGraphs:={}:
    for G in AllGraphs do
        if IsCon(G,n) then
            ConGraphs:=ConGraphs union {G}:
        fi:
    od:
    return ConGraphs:
end:

NuLabAlmostTreesSlow := proc(N, a) local i:
    return [seq(nops(LabAlmostTrees(i, a)), i=1..N)]:
end:

#############
# Problem 3 #
#############

NuLabAlmostTreesFast := proc(N, a) local i:
    return [seq(coeff(WtCCSeqFast(N, y)[i], y, i+a-1), i=1..N)]:
end:

#############
# Problem 4 #
#############

# The sequence is in OEIS for 0 <= a <= 9. I conjecture that the
# sequence is not in OEIS for a > 9.

#############
# Problem 5 #
#############

Image := proc(G, n, pi) local v, e:
    return {seq(map(v -> pi[v], e), e=G)}:
end:

#############
# Problem 6 #
#############

ULG := proc(n, func) local todo, rv, G, pi:
    todo := func(n):
    rv := {}:
    while todo <> {} do:
        G := todo[1]:
        for pi in permute(n) do:
            todo := todo minus {Image(G, n, pi)}:
        od:
        rv := rv union {G}:
    od:
    return rv:
end:

ConULG := proc(n):
    return ULG(n, ConG):
end:

Count := proc(N, func):
    return [seq(nops(func(i)), i=1..N)]:
end:

NuConULGSeqSlow := proc(N) local i:
    return Count(N, ConULG):
end:

# It's A001349.

ULTrees := proc(n):
    return ULG(n, LabTrees):
end:

NuULTreesSeqSlow := proc(N) local i:
    return Count(N, ULTrees):
end:

# It works! It's A000055.

ULAlmostTrees := proc(n, a):
    return ULG(n, x -> LabAlmostTrees(x, a)):
end:

NuULAlmostTreesSeqSlow := proc(N, a) local i:
    return Count(N, x -> ULAlmostTrees(x, a)):
end:

# a = 0: A000055
# a = 1: A001429
# a = 2: A001435
# a = 3: A001436
# Conjecture: Not in OEIS for a > 3.