#!/usr/local/bin/maple #-*- maplev -*- # Nathaniel Shar # HW 26 # Experimental Mathematics # It is okay to link to this assignment on the course webpage. Help := proc(): print(`PermToCyc(P), CIP(G, s), NumColorings(G, c), Mul(P, Q), Gp(S), NumColoringsWtEnum(G, wts)`): end: # Stuff from my class 26 file: PermToCyc := proc(P) local rv, c, i, j, seen: seen := {}: rv := {}: for i from 1 to nops(P) do: if not member(i, seen) then: seen := seen union {i}: c := [i]: j := P[i]: while j <> i do: c := [op(c),j]: seen := seen union {j}: j := P[j]: od: rv := rv union {c}: fi: od: return rv: end: # CIP = "cycle index polynomial" CIP := proc(G, s) local i,k: return add(mul(s[nops(c)], c=PermToCyc(pi)), pi=G)/nops(G): end: NumColorings := proc(G, c) local s: return subs({seq(s[i]=c, i=1..nops(G[1]))}, CIP(G, s)): end: Mul := proc(P, Q): return map(i -> Q[i], P): end: Gp := proc(S) local todo, G, product, rho, pi: G := S: todo := S: while todo <> {} do: rho := todo[1]: todo := todo minus {rho}: for pi in G do: product := Mul(pi, rho): if not member(product, G) then: todo := todo union {product}: G := G union {product}: fi: od: od: return G: end: ############# # Problem 1 # ############# NumColoringsWtEnum := proc(G, wts) local s, wt: return subs({seq(s[i]=add(wt^i, wt in wts),i=1..nops(G[1]))}, CIP(G, s)); end: # Running # coeff(coeff(coeff(expand(NumColoringsWtEnum(Gp({[50,seq(i,i=1..49)], [seq(51-i, i=1..50)]}), [r,b,g])), r, 15), b, 23), g, 12); # gives 18782087906662883712. (This assumes the necklaces can be # turned over; that is, the group of symmetries is the dihedral # group.) ############# # Problem 2 # ############# # Running # coeff(coeff(coeff(expand(NumColoringsWtEnum(Gp({[1,4,2,5,3,6], [3,2,6,1,5,4], [2,6,3,4,1,5]}), [r,b,g])), r, 3), b, 2), g, 1) # yields 3. # This is easier to check by hand. If the two blue faces are opposite, # then there is no choice about where to put the green face relative # to the blue faces. If the two blue faces are adjacent, then the # green face can be either adjacent to both, or just one. These are # the only possibilities, so the answer is 3.