# Brute force code for avoidance sequences1import itertools2def PartitionAvoids(mu, pat):3mu = Partition(mu)4pat = Partition(pat)5r = mu.length()67a = pat.length()8b = pat.conjugate().length()91011R = range(0,r)12for Y in itertools.combinations(R, a):13nu = Partition([mu[i] for i in Y]).conjugate()1415c = nu.length()16if c>= b:17C = range(0,c)18for X in itertools.combinations(C,b):19nu2 = Partition([nu[i] for i in X]).conjugate()2021if nu2 == pat:22return false2324return true2526def GenAllAvoiding(pat,n):27P = []28for p in Partitions(n):29if PartitionAvoids(p,pat):30P.append(p)31return P3233def GetAvoidanceSequence(pat, N):34L = []35for n in range(1,N+1):36x = GenAllAvoiding(pat,n)37L.append(len(x))38return L39404142#Generating function code for avoidance sequences43def GetExp(monomial):44if monomial == 1:45return 046else:47return floor(log(monomial)(x=e))4849def GFTree(L, t):5051if L != []:52if L[0] == 'E':53G = (GFTree(L[1:],1) - x*t*GFTree(L[1:],x*t))/(1-x*t)54return G.full_simplify()55else:56if t!= 0:57m = GetExp(t)58G = 059F0 = GFTree(L[1:], 0)60for i in range(0,m+1):61G += GFTree(L[1:],x**i) - F06263G = 1/(1-x**(m+1))*G + F064return G.full_simplify()65else:66return GFTree(L[1:], 0)6768else:69return x*t/(1-x*t)707172def GetBoundaryDirections(mu):73B = []7475B = B+ ['E']*(mu[-1]-1)76B += ['NE']777879for i in range(len(mu)-2,0,-1):80k = (mu[i]-mu[i+1]-1)81B +=['E']*k82B += ['NE']8384B +=['E']*((mu[0]-mu[1]-2))858687B.reverse()8889return B909192# Nathan the procedure "Test" is what you need to run this.93# mu must be a partition (as a list) of a super distinct partition94# N is the the number of terms you will see in the GF95def Test(mu,N):96L = GetBoundaryDirections(mu)97print L98F = GFTree(L,1)99print F.full_simplify()100101#print GetAvoidanceSequence(mu, N)102return F.series(x,N+1).coefficients(sparse = False)[1:]103104105106107108109110111112# def Get(N, k):113# Seq = []114# for n in range(1,N+1):115# c = 0116117# for p in Partitions(n):118# S = set()119# for x in p:120# S.add(x)121# L = list(S)122# L.sort()123# if len(L) <=k and L[-1]- L[0]<= k-1:124# c+=1125126# Seq.append(c)127# return Seq128129# def GetTau_GF(N):130# x,t = var('x,t')131# T = x*0132133# for n in range(1,N+1):134# for d in divisors(n):135# T+= t**d * x**n136137# return T.collect(x)138139# def PartitionsDifferBy_GF(N,K):140# x,t = var('x,t')141# F0 = GetTau_GF(N)142143# Fk = (F0(t=1) - F0(t=x*t)) / (1-x*t)144145146147# for k in range(2,K+1):148# Fk = (Fk(t=1) - x*t*Fk(t=x*t)) / (1-x*t)149150151# return Fk(t=1).series(x,N)152153154# def CountGeneralizedDivisionAlgorithm_GF(N,K):155# x = var('x')156# F = x**K/(1-x**K)/(1-x**K)157158# for s in range(1,K):159# F += x**s/(1-x**s) * 1/(1-x**K)160161# return F.series(x,N+1).coefficients(sparse = False)[1:]162163164# def CountGeneralizedDivisionAlgorithm_Force(n,k):165# c = 0166# for a in range(1,n+1):167# for r in range(0,a):168# if n-k*r >= a:169# if (n-k*r) % a == 0:170# c +=1171# # print n, a, (n-k*r)/a, r172# return c173174# def GetSequence_Force(N,k):175# L = []176# for n in range(1,N+1):177# L.append(CountGeneralizedDivisionAlgorithm_Force(n,k))178# return L179180181182183184185