# John Miller # hw25.txt - Homework assigned Thu, Apr 19, due Apr 22. Help := proc(): print(`NuLabAlmostTreesSlow(N,a), LabAlmostTrees(n,a)`): print(`NuLabAlmostTreesFast(N,a), Image(G,n,pi)`): print(`ConULG(n), NuConULSeqSlow(N)`): print(`ConULAlmostTrees(n,a), NuConULAlmostTreesSlow(N,a)`): end: HelpC25:=proc(): print(`Edges(n), Graphs(n), Neis(G,i), CC(G,Erdos) `): print(`IsCon(G,n), ConG(n) , NuCCSeqSlow(N) , NuCCSeqFast(N)`): print(`LabTrees(n) , NuLabTreesSlow(N) , NuLabTreesSeqFast(N)`): end: with(combinat): ###################################################################### # Question 1 - Sorry I'm not on Facebook! ###################################################################### # Question 2 # NuLabAlmostTreesSlow(N,a): Inputs a postive integer N, and a # nonnegative integer "a", and outputs the list consisting of the # number of labelled connected graph on {1,...,n} with exactly n-1+a # edges, for n = 1,2,...,N. Slow, using brute force. NuLabAlmostTreesSlow := proc(N::posint,a::nonnegint) local i: [seq(nops(LabAlmostTrees(i,a)),i=1..N)]: end: # end of NuLabAlmostTreesSlow(N,a) ###################################################################### # LabAlmostTrees(n,a): The set of all labelled connected graphs on # {1,...,n} with exactly n-1+a edges. LabAlmostTrees := proc(n::posint,a::nonnegint) local ConGraphs, AllGraphs, G: AllGraphs:=choose(Edges(n),n-1+a): ConGraphs:={}: for G in AllGraphs do if IsCon(G,n) then ConGraphs:=ConGraphs union {G}: fi: od: ConGraphs: end: # end of LabAlmostTrees(n,a) ###################################################################### # Question 3 # NuLabAlmostTreesFast(N,a): Inputs a postive integer N, and a # nonnegative integer "a", and outputs the list consisting of the # number of labelled connected graph on {1,...,n} with exactly n-1+a # edges, for n = 1,2,...,N. Fast, using generating functionology. NuLabAlmostTreesFast := proc(N,a) local egfList::list, y, n: egfList := WtCCSeqFast(N,y): [seq(coeff(egfList[n],y,n-1+a),n=1..N)]: end: # end of NuLabAlmostTreesFast(N,a) ###################################################################### # Question 4 # NuLabAlmostTreesFase(N,a) # a OEIS # 0 A000272 # 1 A057500 # 2 A061540 # 3 A061541 # 4 A061542 # 5 A061543 # 6 A096117 # 7 A061544 # 8 A096150 # 9 A096224 # >10 not in OEIS ###################################################################### # Question 5 # Image(G,n,pi): Inputs a simple labelled graph G (in our notation) # of {1,...,n}, a positive intger n, and a permutation pi of {1,...,n} # and outputs the image under pi, i.e. the graph where the label pi[i] # goes to label pi[i] for i=1,2,...,n. Image := proc(G::set,n::posint,pi::list) local edge::set, vertex::posint, newG::set: newG := {}: for edge in G do: newG := newG union { {seq(pi[v],v in edge) } } od: newG: end: # end of Image(G,n,pi) ###################################################################### # Question 6 # ConULG(n): Inputs a positive intger n, and outputs ONE # representative from each equivalence class. ConULG := proc(n::posint) local ConGraphs::set, G::set, PermGroup::list, UnlabGraphs, Perm::list: PermGroup := permute(n): ConGraphs := ConG(n): UnlabGraphs := {}: while ConGraphs <> {} do: G := ConGraphs[1]: UnlabGraphs := UnlabGraphs union {G}: ConGraphs := ConGraphs minus {seq(Image(G,n,Perm),Perm in PermGroup)}: od: UnlabGraphs: end: # end of ConULG(n) ###################################################################### # NuConULSeqSlow(N): Counts the number of connected unlabelled graphs # on n vertices, for n from 1 to N. # NuConULSeqSlow(6); outputs [1, 1, 2, 6, 21, 112], # which in OEIS: A001349 NuConULSeqSlow := proc(N::posint) local n: [seq(nops(ConULG(n)),n=1..N)]: end: # end of NuConULSeqSlow(N) ###################################################################### # Question 7 & 8 combined # ConULAlmostTrees(n,a): Inputs a pos integer n and nonneg integer a # and outputs ONE representative from each equivalence class. # To count unlabelled TREES, just take a=0. ConULAlmostTrees := proc(n::posint,a::nonnegint) local ConGraphs::set, G::set, PermGroup::list, UnlabGraphs, Perm::list: PermGroup := permute(n): ConGraphs := LabAlmostTrees(n,a): UnlabGraphs := {}: while ConGraphs <> {} do: G := ConGraphs[1]: UnlabGraphs := UnlabGraphs union {G}: ConGraphs := ConGraphs minus {seq(Image(G,n,Perm),Perm in PermGroup)}: od: UnlabGraphs: end: # end of ConULAlmostTrees(n,a) ###################################################################### # NuConULAlmostTreesSlow(N,a): Counts the number of connected unlabelled # almost trees on n vertices and n-1+a edges, for n from 1 to N. # NuConULAlmostTreesSlow(7,0); outputs [1, 1, 1, 2, 3, 6, 11], # which of course is in OEIS: A000055, i.e. # of unlabeled trees NuConULAlmostTreesSlow := proc(N::posint,a::nonnegint) local n: [seq(nops(ConULAlmostTrees(n,a)),n=1..N)]: end: # end of NuConULAlmostTreesSlow(N,a) # NuConULAlmostTreesSlow(N,a) # a: OEIS: # 0 A000055 # 1 A001429 # 2 A001435 # 3 A001436 # 4 does not seem to be in OEIS ###################################################################### ##################### stuff from C25.txt ############################# #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: