#!/usr/local/bin/maple #-*- maplev -*- # Nathaniel Shar # HW 27 # Experimental Mathematics # It is okay to link to this assignment on the course webpage. Help := proc(): print(`A55(N), PermToCyc(P), CIP(G, s), NumColorings(G, c), Mul(P, Q), Gp(S), CycleIndexSn(n, x), SSe(deglist, N)`): end: ############# # Stuff from class 27: with(combinat): with(group): # #URT(N): the first N terms of the enumerating # #sequence for the numnber of UNLABELLED rooted trees # #with n vertices # URT:=proc(N) local A,f,n,x,i: # A:=[1]: # for n from 2 to N do # f:=x*mul(1/(1-x^i)^A[i],i=1..nops(A)): # f:=taylor(f,x=0,n+1): # A:=[op(A),coeff(f,x,n)]: # od: # A: # end: # Cayley: Let A be the ogf of unlabeled trees and R be the ogf of unlabeled rooted trees. # Then A(x) = R(x) - R(x)^2/2 + R(x^2)/2. # The first N terms of A000055. A55 := proc(N) local R,A,x,i,L: L := URT(N): R := add(L[i]*x^i, i=1..N): A := R - R^2/2 + subs(x=x^2, R)/2: return [seq(coeff(expand(A), x, i), i=1..N)]; end: 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 # ############# CycleIndexSn := proc(n, x) local t, u: return coeff(taylor(exp(add(t^i*x[i]/i, i=1..n)), t, n+1), t, n): end: SSe := proc(deglist, N) local x, T, i, j, k, s: if not member(0, deglist) then: FAIL: fi: T := x: for i from 2 to N do: T := add(coeff(x + x*add(subs({seq(s[i]=subs(x=x^i, T), i=1..j)}, CycleIndexSn(j, s)), j=deglist minus {0}), x, k)*x^k, k=0..i): od: return [seq(coeff(T, x, i), i=1..N)]: end: ############# # Problem 2 # ############# # In OEIS: # {0}: A7 # {0,1}: A12 # {0,1,2}: Almost in OEIS (A1190 and A36656 differ only in offset) # {0,1,2,3}: A598 # {0,1,2,3,4}: A36718 # {0,1,2,3,4,5}: A36721 # {0,1,2,3,4,5,6}: A36722 # {0,1,2,3,4,5,6,7}: A36723 (observer effect -- approved Apr. 26) # I did not find any others.