# Experimental Math - Homework 20 - Due April 8 # Phil Benjamin # Note: this homework assignment may be freely uploaded to the # Experimental Math course web site # Problem 1 # UA(k) # Input: integer k # Output: # Set of sets of length-k patterns on alphabet {0,1} # that are unavoidable in every sufficiently long word in {0,1}. # Note: don't try this for k > 4! # Hint: use GFunT(A,B,FP,T) with FP ranging over all 2^(2^k) possible sets # of length-k B-free patterns. See which of them outputs a polynomial # in T. # Experiments: # Note: UA(1) --> {{[0],[1]}} # Find UA(2), UA(3), UA(4) [if possible!] # TBD # Problem 2 # AUA(k) # Input: integer k # Output: # set of sets of patterns of length k that are almost unavoidable # Hint: use GFunT(A,B,FP,T) as above. See which of them outputs a rational # function with denominator having abs(all roots) >= 1. # TBD # Problem 3 # IsImpliedPattern(pat1,pat2,B) # Input: patterns pat1, pat2 and blank B # Output: true if an occurance of pat1 implies an occurrance of pat2 # Examples: # IsImpliedPattern([1,1,1],[1,1],B) --> true # IsImpliedPattern([1,3,1],[1,B,1],B) --> true # IsImpliedPattern([2,1,1],[1,B,1],B) --> false # TBD # Problem 4 # MinimalFP(B,FP) # Input: blank B and set of forbidden patterns FP # Output: subset of forbidden patterns of FP whose avoidance implies # the avoidance of all patterns in FP # Example: # MinimalFP(B,{[1,1,1],[1,1,1,1],[1,B,1],[1,2,1]}) --> {[1,B,1]} # TBD # Problem 5 # SAW(n) # Input: integer n # Output: set of all self-avoiding walks of length n # Self-avoiding walk using alphabet {1,-1,2,-2} such that no sublist has # the same number of {1,-1} AND the same number of {2,-2} # Example # SAW(2) --> {[1,1],[1,2],[1,-2],[2,2],[2,1],[2,-1], # [-1,-1],[-1,-2],[-1,2],[-2,2],[-2,-1],[-2,1]} # Hint: use recursion # Count number of occurrances of a in list L (is there a proc for this?) CountMember := proc(a,L) local c, i; c := 0; for i from 1 to nops(L) do if L[i] = a then c := c + 1; end; end; return c; end: SAW := proc(n) local Alpha, a, SAWout, L, n1; Alpha := {1,-1,2,-2}; SAWout := {seq([a],a in Alpha)}; if n = 1 then return SAWout; end; for n1 from 2 to n do SAWout := SAWappend(Alpha,SAWout); end; return SAWout; end: # append to SAWset for each letter of Alpha if "safe" SAWappend := proc(Alpha,SAWset) local a, L, SAWout; SAWout := {}; for L in SAWset do for a in Alpha do if CountMember(a,L)+1 <> CountMember(-a,L) then SAWout := SAWout union {[op(L),a]}; end; end; end; return SAWout; end: # Problem 6 # Find SAW(1..10) and check OEIS # Problem 7 # SAP(n) # Input: integer n # Output: set of all self-avoiding polygons # Self-avoiding polygon: list length 2*n with all sublists SAW (see above) # but entire list is not (i.e. "end where you start"). # Example # SAP(1) --> {[1,-1],[-1,1],[2,-2],[-2,2]} # TBD # Problem 8 # GFsawd(d,T) # Input: d positive integer, T symbol # Output: # rational function in T with Maclarin coefficient of T^n # is the number of memory-d-self-avoiding walks of length n. # where # memory (2*d) so no consecutive subwalk of length 2*r is a sap for r=1..d # Hint: # Use GFunT({1,-1,2,-2},B,FP,T) with FP = Union{SAP(r),r=1..d} # TBD # Problem 9 # Find GFsawd(d,T) for d=1..4 [if possible]. # Find the first 30 terms in the Taylor expansions and check OEIS # Problem 9 # TBD