CoCalc Shared Filesresearch / partitions / PartitionAvoidanceGF.pyOpen in CoCalc with one click!
Author: Nathan McNew
Description: Partitions
1
# Brute force code for avoidance sequences
2
import itertools
3
def PartitionAvoids(mu, pat):
4
mu = Partition(mu)
5
pat = Partition(pat)
6
r = mu.length()
7
8
a = pat.length()
9
b = pat.conjugate().length()
10
11
12
R = range(0,r)
13
for Y in itertools.combinations(R, a):
14
nu = Partition([mu[i] for i in Y]).conjugate()
15
16
c = nu.length()
17
if c>= b:
18
C = range(0,c)
19
for X in itertools.combinations(C,b):
20
nu2 = Partition([nu[i] for i in X]).conjugate()
21
22
if nu2 == pat:
23
return false
24
25
return true
26
27
def GenAllAvoiding(pat,n):
28
P = []
29
for p in Partitions(n):
30
if PartitionAvoids(p,pat):
31
P.append(p)
32
return P
33
34
def GetAvoidanceSequence(pat, N):
35
L = []
36
for n in range(1,N+1):
37
x = GenAllAvoiding(pat,n)
38
L.append(len(x))
39
return L
40
41
42
43
#Generating function code for avoidance sequences
44
def GetExp(monomial):
45
if monomial == 1:
46
return 0
47
else:
48
return floor(log(monomial)(x=e))
49
50
def GFTree(L, t):
51
52
if L != []:
53
if L[0] == 'E':
54
G = (GFTree(L[1:],1) - x*t*GFTree(L[1:],x*t))/(1-x*t)
55
return G.full_simplify()
56
else:
57
if t!= 0:
58
m = GetExp(t)
59
G = 0
60
F0 = GFTree(L[1:], 0)
61
for i in range(0,m+1):
62
G += GFTree(L[1:],x**i) - F0
63
64
G = 1/(1-x**(m+1))*G + F0
65
return G.full_simplify()
66
else:
67
return GFTree(L[1:], 0)
68
69
else:
70
return x*t/(1-x*t)
71
72
73
def GetBoundaryDirections(mu):
74
B = []
75
76
B = B+ ['E']*(mu[-1]-1)
77
B += ['NE']
78
79
80
for i in range(len(mu)-2,0,-1):
81
k = (mu[i]-mu[i+1]-1)
82
B +=['E']*k
83
B += ['NE']
84
85
B +=['E']*((mu[0]-mu[1]-2))
86
87
88
B.reverse()
89
90
return B
91
92
93
# Nathan the procedure "Test" is what you need to run this.
94
# mu must be a partition (as a list) of a super distinct partition
95
# N is the the number of terms you will see in the GF
96
def Test(mu,N):
97
L = GetBoundaryDirections(mu)
98
print L
99
F = GFTree(L,1)
100
print F.full_simplify()
101
102
#print GetAvoidanceSequence(mu, N)
103
return F.series(x,N+1).coefficients(sparse = False)[1:]
104
105
106
107
108
109
110
111
112
113
# def Get(N, k):
114
# Seq = []
115
# for n in range(1,N+1):
116
# c = 0
117
118
# for p in Partitions(n):
119
# S = set()
120
# for x in p:
121
# S.add(x)
122
# L = list(S)
123
# L.sort()
124
# if len(L) <=k and L[-1]- L[0]<= k-1:
125
# c+=1
126
127
# Seq.append(c)
128
# return Seq
129
130
# def GetTau_GF(N):
131
# x,t = var('x,t')
132
# T = x*0
133
134
# for n in range(1,N+1):
135
# for d in divisors(n):
136
# T+= t**d * x**n
137
138
# return T.collect(x)
139
140
# def PartitionsDifferBy_GF(N,K):
141
# x,t = var('x,t')
142
# F0 = GetTau_GF(N)
143
144
# Fk = (F0(t=1) - F0(t=x*t)) / (1-x*t)
145
146
147
148
# for k in range(2,K+1):
149
# Fk = (Fk(t=1) - x*t*Fk(t=x*t)) / (1-x*t)
150
151
152
# return Fk(t=1).series(x,N)
153
154
155
# def CountGeneralizedDivisionAlgorithm_GF(N,K):
156
# x = var('x')
157
# F = x**K/(1-x**K)/(1-x**K)
158
159
# for s in range(1,K):
160
# F += x**s/(1-x**s) * 1/(1-x**K)
161
162
# return F.series(x,N+1).coefficients(sparse = False)[1:]
163
164
165
# def CountGeneralizedDivisionAlgorithm_Force(n,k):
166
# c = 0
167
# for a in range(1,n+1):
168
# for r in range(0,a):
169
# if n-k*r >= a:
170
# if (n-k*r) % a == 0:
171
# c +=1
172
# # print n, a, (n-k*r)/a, r
173
# return c
174
175
# def GetSequence_Force(N,k):
176
# L = []
177
# for n in range(1,N+1):
178
# L.append(CountGeneralizedDivisionAlgorithm_Force(n,k))
179
# return L
180
181
182
183
184