### Kristen Lew, Homework 25 ### ExpMath, Spring 2012 ## Post if you wish. with(combinat): ### Problem 1 ## Find your facebook distance to Dr. Z. (=1+ your facebook distance to Ian Page) # Facebook distance = 3, I have a mutual friend of Ian Page # [Myself, my friend, Ian Page, Dr. Z] ### Problem 2 ## 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) [seq(nops(AlmostLabTrees(i,a)),i=1..N)]: end: Edges:=proc(n) local i,j: {seq(seq({i,j},i=1..j-1),j=2..n)}: end: Graphs:=proc(n) powerset(Edges(n)): end: 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:=proc(G,i) local C1,NewF,v: C1:={i}: NewF:=Neis(G,i): while NewF minus C1<>{} do C1:=C1 union NewF: NewF:=`union`(seq(Neis(G,v), v in NewF)): od: C1: end: IsCon:=proc(G,n): evalb(nops(CC(G,1))=n): end: AlmostLabTrees:=proc(n,a) 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: ### Problem 3 ## 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 n,y,L: L:=WtCCSeqFast(N,y): [seq(coeff(L[n],y,n-1+a),n=1..N)]: end: 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 4 ## By taking N=20, find out for which a is the sequence NuLabAlmostTreesFast(20,a); # in Sloane? # a=0: A000272 Number of trees on n labeled nodes: n^(n-2). # a=1: A057500 Number of connected labeled graphs with n edges and n nodes. # a=2: A061540 Number of connected labeled graphs with n nodes and n+1 edges. # a=3: A061541 Number of connected labeled graphs with n nodes and n+2 edges. # a=4: A061542 Number of connected labeled graphs with n nodes and n+3 edges. # a=5: A061543 Number of connected labeled graphs with n nodes and n+4 edges. # a=6: A096117 Number of connected labeled graphs with n nodes and n+5 edges. # a=7: A061544 Number of connected labeled graphs with n nodes and n+6 edges. # a=8: A096150 Number of connected labeled graphs with n nodes and n+7 edges. # a=9: A096224 Number of connected labeled graphs with n nodes and n+8 edges. ### Problem 5 ## 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): if nops(G)<>n or nops(pi)<>n then return(FAIL): end: Mul(pi,G): end: Mul:=proc(P,Q) local perm,k: if nops( P) <> nops(Q) then RETURN(FAIL): fi: perm:=[seq(Q[P[k]],k=1..nops(Q))]: end: ### Problem 6 ## 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 cong, perm, ULG, g, p: cong:=ConG(n): perm:=permute(n): ULG:={}: while cong<>{} do g:=cong[1]: for p in perm do cong:=cong minus {Image(g,n,p)}: od: ULG:=ULG union {g}: od: ULG: end: 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: NuConULSeqSlow:=proc(N) local n: [seq(nops(ConULG(n)),n=1..N)]: end: ### Problem 7 ## Do the analogous things for unlabelled trees, and see whether you get # Neil Sloane's favorite sequence, 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?