#!/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.