# Matthew Russell # Experimental Math # Homework 25 # I give permission to post this read `public_html/em12/C25.txt`: ##################################################################################### # Recall that a labelled tree on {1, ...,n} is a connected labelled graph on {1, ...,n} # with exactly n-1 edges. Generalize NuLabTreesSlow(N), to write a procedure # NuLabAlmostTreesSlow(N,a) # that inputs a pos. integer N, and a non-neg. 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. # [In particular # NuLabAlmostTreesSlow(N,0); # should output the same as # NuLabTreesSlow(N); ] NuLabAlmostTreesSlow:=proc(N,a) local i: return [seq(nops(LabAlmostTrees(a,i)),i=1..N)]: end: LabAlmostTrees:=proc(a,n) 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: return ConGraphs: end: ##################################################################################### # By using # WtCCSeqFast(N,y): # (that outputs a list whose n-th entry is a polynomials of degree n(n-1)/2 in y, for n=1..N ) # and extracting the coefficient of the right power of y, write a procedure # NuLabAlmostTreesFast(N,a); # that gives you the same output as NuLabAlmostTreesSlow(N,a), but much faster. NuLabAlmostTreesFast:=proc(N,a) local i,y: return [seq(coeff(WtCCSeqFast(N,y)[i],y,i-1+a),i=1..N)]: end: ##################################################################################### # By taking N=20, find out for which a is the sequence # NuLabAlmostTreesFast(20,a); # in Sloane? # It is in Sloane for a up to 9 (which represents the sequence of the number of graphs # on n nodes with exactly n+8 edges). ##################################################################################### # Write a procedure # Image(G,n,pi) # that inputs a simple labelled graph G (in our notation) of {1, ...,n}, a pos. # integer n, and a permutation pi of {1, ...,n} and outputs the image under pi, # in other words, the graph where label i goes to label pi[i] for i=1,2, ,... n. Image:=proc(G,n,pi) local ed, i: if nops(pi)<>n then return `FAIL`: fi: return {seq(map(i->pi[i],ed),ed in G)}: end: ##################################################################################### # By starting out with the output of ConG(n), and using combinat's function # "permute(n)", write a procedure # ConULG(n) , # that inputs a pos. integer n, and outputs ONE representative from each equivalence # class. Use this to write a procedure # NuConULSeqSlow(N): # that counts, the number of connected unlabelled graph (alias equivalence class under permuting labels) on n vertices for n from 1 to N. # Is # NuConULSeqSlow(6): # in Sloane? ConULG:=proc(n) local CoGr, S, Good, curr, p: S:=convert(combinat[permute](n),set): CoGr:=ConG(n): Good:={}: while CoGr<>{} do curr:=CoGr[1]: Good:=Good union {curr}: for p in S do CoGr:=CoGr minus {Image(curr,n,p)}: od: od: return Good: end: NuConULGSeqSlow:=proc(N) return [seq(nops(ConULG(i)),i=1..N)]: end: # NuConULGSeqSlow(6) = [1, 1, 2, 6, 21, 112] # is A001349. ##################################################################################### # Do the analogous things for unlabelled trees, and see whether you get Neil Sloane's favorite sequence, A000055. ConULT:=proc(n) local CoTr, S, Good, curr, p: S:=convert(combinat[permute](n),set): CoTr:=LabTrees(n): Good:={}: while CoTr<>{} do curr:=CoTr[1]: Good:=Good union {curr}: for p in S do CoTr:=CoTr minus {Image(curr,n,p)}: od: od: return Good: end: NuConULTSeqSlow:=proc(N) return [seq(nops(ConULT(i)),i=1..N)]: end: # NuConULGSeqSlow(6) = [1, 1, 1, 2, 3, 6] # is A000055. ##################################################################################### # Do the analogous things for almost trees. For which a's are the sequences # "number of unlabelled connected graphs with n vertices and n-1+a edges" # in Sloane? ConULAT:=proc(a,n) local CoATr, S, Good, curr, p: S:=convert(combinat[permute](n),set): CoATr:=LabAlmostTrees(a,n): print(`CoATr done`): if CoATr={} then return {}: fi: Good:={}: while CoATr<>{} do curr:=CoATr[1]: Good:=Good union {curr}: for p in S do CoATr:=CoATr minus {Image(curr,n,p)}: od: od: return Good: end: NuConULATSeqSlow:=proc(a,N) return [seq(nops(ConULAT(a,i)),i=1..N)]: end: # NuConULATSeqSlow(1,7) = [0, 0, 1, 2, 5, 13, 33] # appears to be A001429 # NuConULATSeqSlow(2,6) = [0, 0, 0, 1, 5, 19] # is A001435 # NuConULATSeqSlow(3,6) = [0, 0, 0, 1, 4, 22] # is A001436 # It is too difficult to get enough data for a>=4