Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
C++ and Maple
TM
Programs 439
{
setclass[nclass][i1][j1]=state1[i1][j1];
printf("%d",state1[i1][j1]+1);
fprintf(fout,"%d",state1[i1][j1]+1);
}
printf(" , ");
fprintf(fout," , ");
}
printf("\n");
fprintf(fout,"\n");
lsetclass[nclass]=lstate1;nclass++;
for(i1=0;i1<sizeAu+1;i1++)
{
Au[sizeAu][i1]=0;
Au[i1][sizeAu]=0;
}
Au[i][sizeAu]++; sizeAu++;
}
}
else Au[i][ans]++;
}
}
nst=pns+1;
pns=nclass;
}
}
/* print the transfer matrix Au(p,k) */
void printautomaton()
{
int i,j;
printf("\n\nThe matrix is given by
(maple form)\n\nAu:=matrix([[");
fprintf(fout,"\n\nThe matrix is given by
(maple form)\n\nAu:=matrix([[");
for(i=0;i<sizeAu-1;i++)
{
for(j=0;j<sizeAu-1;j++)
{
printf("%d,",Au[i][j]);
fprintf(fout,"%d,",Au[i][j]);
}
printf("%d],\n[",Au[i][sizeAu-1]);
fprintf(fout,"%d],\n[",Au[i][sizeAu-1]);
}
for(j=0;j<sizeAu-1;j++)
{
printf("%d,",Au[sizeAu-1][j]);
fprintf(fout,"%d,",Au[sizeAu-1][j]);
© 2010 by Taylor and Francis Group, LLC
440 Combinatorics of Compositions and Words
}
printf("%d]]);\n",Au[sizeAu-1][sizeAu-1]);
fprintf(fout,"%d]]);\n",Au[sizeAu-1][sizeAu-1]);
}
/* main procedure */
void main()
{
int i;
printf("Enter the number k of letters in your alphabet: ");
scanf("%d",&NUMBERLETTER);
numberrow=1;
printf("Enter the length of the pattern (3-6): ");
scanf("%d",&lenpattern);
numbercolumn=lenpattern;
printf("Enter the pattern (space between the letters): ");
for(i=0;i<lenpattern;i++)
scanf("%d",&pattern[0][i]);
fout=fopen("data.dat","w");
printf("The automaton for the number
of %d-ary words of length n\n",NUMBERLETTER);
printf("that avoid the pattern ");
fprintf(fout,"The automaton for the number
of %d-ary words of length n\n",NUMBERLETTER);
fprintf(fout,"that avoid the pattern ");
for(i=0;i<lenpattern;i++)
{
printf("%d ",pattern[0][i]);
fprintf(fout,"%d ",pattern[0][i]);
}
printf(" is given by:\n\n");
fprintf(fout," is given by:\n\n");
printf("The states are \n");
fprintf(fout,"The states are \n");
extendbymat();
nclass=0; sizeAu=0; automat();
printautomaton();
fclose(fout);
}
We show how to use the program for the pattern 112.
Example G.2 To compute the automaton for avoidance of the subsequence
pattern 112 in 3-ary words using the program TOU
AUTO, the user inputs
the alphabet, the length of the pattern, and the pattern:
Enter the number k of letters in your alphabet: 3
Enter the length of the pattern (3-6): 3
Enter the pattern (space between the letters): 1 1 2
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 441
This results in the output
The automaton for the number of 3-ary words of length n
that avoid the pattern 1 1 2 is given by:
The states are
1) empty state
2) 1 ,
3) 2 ,
4) 11 ,
5) 12 ,
6) 22 ,
7) 122 ,
The matrix is given by (maple form)
Au:=matrix([[1,1,1,0,0,0,0],
[0,1,0,1,1,0,0],
[0,0,1,0,1,1,0],
[0,0,0,1,0,0,0],
[0,0,0,1,1,0,1],
[0,0,0,0,0,1,1],
[0,0,0,1,0,0,1]]);
Press any key to continue
G.5.2 Maple
TM
program TOU FORMULA
The core of this program is the implementation of the formula given in The-
orem 7.34. Using partial fraction decomposition and geometric series allows
us to obtain an explicit formula for AW
τ
[k]
(n). The program has as its output
this explicit formula and the values of AW
τ
[k]
(n)forn =0,...,12.
formula:=proc()
local S,Au,sizeAu,J,i,j,ii,jj,nn,Values,A,size,B,b,w,form,M:
Au:=args[1]: with(linalg):
J:=factor(minpoly(Au,x)):
S:=roots(J): sizeAu:=rowdim(Au): nn:=nops(S):
Values:={}: size:=0:
for i from 1 to nn do
Values:=Values union {S[i][1]}: size:=size+S[i][2]:
od:
A:=matrix(size,size,[]): w:=linalg[vector](sizeAu,[]):
b:=vector(size,[]): B:=linalg[vector](size,[]):
for i from 1 to sizeAu do w[i]:=1: od:
b[1]:=1: B[2]:=evalm(Au): b[2]:=evalm(B[2]&*w)[1]:
for i from 2 to size-1 do
B[i+1]:=evalm(B[i]&*Au): b[i+1]:=evalm(B[i+1]&*w)[1]:
od:
© 2010 by Taylor and Francis Group, LLC
442 Combinatorics of Compositions and Words
for i from 1 to size do jj:=0:
for ii from 1 to nops(Values) do
for j from 0 to S[ii][2]-1 do
jj:=jj+1:
if i-1>=j then
A[i,jj]:=(S[ii][1])^(i-1-j)*binomial(i-1,j):
else
A[i,jj]:=0:
fi:
od: od: od:
w:=linsolve(A,b);
printf("First values n=0...12");
M:=vector(13,[]):
for i from 0 to 12 do
form:=0: jj:=0:
for ii from 1 to nops(Values) do
for j from 0 to S[ii][2]-1 do
jj:=jj+1:
form:=form+w[jj]*(S[ii][1])^(i-j)*binomial(i,j):
od: od:
M[i+1]:=form:
od:
print(M):
printf("The formula is");
form:=0: jj:=0:
for ii from 1 to nops(Values) do
for j from 0 to S[ii][2]-1 do
jj:=jj+1:
form:=form+w[jj]*(S[ii][1])^(n-j)*binomial(n,j):
od: od:
print(form):
end:
Using the output of the program TOU AUTO as input for the program
TOU
FORMULA allows us to compute the values {AW
112
[3]
(n)}
12
n=0
and an
explicit formula for AW
112
[3]
(n).
Example G.3 (Continutaion of Example G.2) The transfer matrix for the
pattern 112 is given by
Au:=matrix([[1,1,1,0,0,0,0],
[0,1,0,1,1,0,0],
[0,0,1,0,1,1,0],
[0,0,0,1,0,0,0],
[0,0,0,1,1,0,1],
[0,0,0,0,0,1,1],
[0,0,0,1,0,0,1]]);
This matrix is in the form needed for the argument of the Maple program.
Using
© 2010 by Taylor and Francis Group, LLC
C++ and Maple
TM
Programs 443
formula(Au)
results in the following output:
First values n=0...12
[1, 3, 9, 24, 56, 116, 218, 379, 619, 961, 1431, 2058, 2874]
The formula is
1 + 2 n + 4 binomial(n, 2) + 5 binomial(n, 3) + 3 binomial(n, 4)
© 2010 by Taylor and Francis Group, LLC
Appendix H
Notation
The table below lists the notation. The first part of the table contains sets,
structures and equivalences, followed by an alphabetical listing of named
quantities. Greek letters occur according to their sound. We use “gf” as
an abbreviation for generating function. Note that in rare instances we use
the same symbol for two different objects. This is a result of following the
commonnotationintheliterature. In each case, the two different notations
do not occur in the same chapter.
Notation Definition
(a; q)
n
n−1
j=0
(1 − aq
j
)
[a
0
,a
1
,...] infinite simple continued fraction
[a
0
,a
1
,...,a
k
] finite simple continued fraction
[d]
set of first d integers, {1, 2,...,d}
[k]
∗
set of all finite words on the alphabet [k]
[i, j]
{i, i +1,...,j}
(j
1
,j
2
,...,j
) type of generalized pattern
k
j
shorthand for j letters k ···k
[x
n
] coefficient of x
n
x equivalence class of x for the automaton A
a
n
≈ b
n
a
n
and b
n
are of the same order
a
n
(k)
d
≈N(μ
n
,σ
2
n
) a
n
is approximately normally distributed
K K
block K is to the left of block K
K K
block K is to the right of block K
τ ∼ ν τ and ν are Wilf-equivalent
τ
s
∼ ν τ and ν are strongly equivalent
τ
st
∼ ν τ and ν are strongly tight Wilf-equivalent
τ
t
∼ ν τ and ν are tight Wilf-equivalent
v
A
∼ w v and w are equivalent on [k]
∗
with regard to
avoidance of τ
v ∼
T
w v and w are equivalent on [k]
∗
with regard to
avoidance of T
445
© 2010 by Taylor and Francis Group, LLC
446 Combinatorics of Compositions and Words
Notation Definition
A
ops
↔{a
n
}
n≥0
A is the ordinary gf of {a
n
}
n≥0
E
egf
↔{a
n
}
n≥0
E is the exponential gf of {a
n
}
n≥0
A finite automaton
A(τ,k)
automaton for avoidance of pattern τ for words
on alphabet [k]
A(τ,k)
adjacency matrix of A(τ,k)
A(x),A(x)
ordinary gf
A(x, y)
ordinary gf with respect to order and statistic
A
k
{a
1
,...,a
k
}
¯
A
k
{a
k+1
,a
k+2
,...,a
d
}
AC
A
n
(τ) set of compositions of n with parts in A that
avoid the pattern τ
AC
τ
A
(n) |AC
A
n
(τ)|
AC
τ
A
(x) gf for AC
τ
A
(n)
AC
τ
A
(σ
1
···σ
|n) number of compositions in AC
A
n
(τ)thatstart
with σ
1
···σ
AC
τ
A
(σ
1
···σ
|x) gf for AC
τ
A
(σ
1
···σ
|n)
AC
A
n,m
(τ) set of compositions of n with m parts in A that
avoid the pattern τ
AC
τ
A
(m; n) |AC
A
n,m
(τ)|
AC
τ
A
(x, y) gf for AC
τ
A
(m; n)
AC
τ
A
(σ
1
···σ
|m; n) number of compositions in AC
A
n,m
(τ)that
start with σ
1
···σ
AC
τ
A
(σ
1
···σ
|x, y) gf for AC
τ
A
(σ
1
···σ
|m; n)
adj(A)
adjoint of matrix A
AT
B
κ
(τ) set of compositions in T
B
κ
that avoid τ
AW
[k]
∗
(τ) set of words in [k]
∗
that avoid τ
AW
[k]
n
(τ) set of k-ary words of length n that avoid τ
AW
τ
[k]
(n) |AW
[k]
n
(τ)|
AW
τ
[k]
(x) gf for AW
τ
[k]
(n)
AW
τ
[k]
(w
1
···w
|x) gf for words in AW
τ
[k]
(n)thatstart
with w
1
···w
AW
τ
(x, y) gf for AW
τ
[k]
(x)
AW
[k]
n
(T ) set of reduced k-ary words of length n that
avoid T
AW
T
[k]
(n) |
AW
[k]
n
(T )|
B(σ)
set of parts of σ
© 2010 by Taylor and Francis Group, LLC
Notation 447
Notation Definition
B(n, p) Binomial random variable with parameters n, p
C
set of complex numbers
c(σ)
complement of σ with respect to A
C(n)
number of compositions of n in N
C(x)
gf for C(n)
C(m; n)
number of compositions of n with m parts in N
C(m; x)
gf for C(m; n)
˜
C(x)
gf for number of nonempty compositions
¯
C(n)
number of n-color compositions of n with parts
in N
¯
C(x)
gf for
¯
C(n)
¯
C(m; n)
number of n-color compositions of n with m
parts in N
¯
C(m; x)
gf for
¯
C(m; n)
C
A
set of compositions (of any order) with parts
in A
C
A
n
set of compositions of n with parts in A
C
A
(n) |C
A
n
|
C
A
(x) gf for C
A
(n)
C
A
n,m
set of compositions of n with m parts in A
C
A
(m; n) |C
A
n,m
|
C
A
(m; x) gf for C
A
(m; n)
C
A
n
(τ; r) set of compositions of n with parts in A that
contain τ exactly r times
C
τ
A
(n, r) |C
A
n
(τ; r)|
C
τ
A
(x, q) gf for C
τ
A
(n, r)
C
τ
A
(σ
1
···σ
|n, r) number of compositions in C
A
n
(τ; r)thatstart
with σ
1
···σ
C
τ
A
(σ
1
···σ
|x, q) gf for C
τ
A
(σ
1
···σ
|n, r)
C
A
n,m
(τ; r) set of compositions of n with m parts in A
that contain τ exactly r times
C
τ
A
(m; n, r) |C
A
n,m
(τ; r)|
C
τ
A
(x, y, q) gf for C
τ
A
(m; n, r)
C
τ
A
(σ
1
···σ
|m; n, r) number of compositions in C
A
n,m
(τ; r)that
start with σ
1
···σ
C
τ
A
(σ
1
···σ
|x, y, q) gf for C
τ
A
(σ
1
···σ
|m; n, r)
C
A
(x, y, r, , d) gf for the number of compositions of n with
parts in A according to order and statistic
→
s
σ
© 2010 by Taylor and Francis Group, LLC
448 Combinatorics of Compositions and Words
Notation Definition
C
A
(σ
1
···σ
|x, y, r, , d) gf for the number of compositions of n with
parts in A according to order and statistic
→
s
σ
that start with σ
1
···σ
C
m
(x) gf for number of compositions with at most m
cracks per part
C
n,k
number of k-element combinations of [n]
CC
A
(n) number of Carlitz compositions of n in A
CC
A
(x) gf for CC
A
(n)
CC
A
(σ
1
···σ
|x) gf for the number of Carlitz compositions that
start with σ
1
···σ
CC
A
(m; n) number of Carlitz compositions of n with m
parts in A
CC
A
(x, y) gf for CC
A
(m; n)
CP
A
(n) number of palindromic Carlitz compositions
of n in A
CP
A
(x) gf for CP
A
(n)
CP
A
(σ
1
···σ
|x) gf for the number of palindromic Carlitz
compositions that start with σ
1
···σ
CP (m; n) number of n-color palindromic compositions
of n with m parts in N
D
differential operator
dro(σ)
number of drops in σ
D
τ
A
(x, y, q)
σ∈C
A
n
x
ord ( σ)
y
par( σ)
q
occ
τ
(ˆσ)
,ˆσ = aσ or ˆσ = σb
deg(i)
degree of vertex i
deg
+
(i) out-degree of vertex i
deg
−
(i) in-degree of vertex i
det(A)
determinant of matrix A
Δ(x)
characteristic polynomial
Δ(x)
transition function of automaton
E
set of states for automaton
E(τ,k)
set of states for automaton for avoidance of
pattern τ for words on alphabet [k]
e
i
i-th unit vector
E(x),E(x)
exponential gf
E(x, y)
exponential gf according to order and
statistic
→
s
σ
E(X) expected value or mean of random variable X
ε
equivalence class of empty word in automaton
f
n
shifted Fibonacci sequence
© 2010 by Taylor and Francis Group, LLC
Notation 449
Notation Definition
F
n
Fibonacci sequence
F (x)
gf of the Fibonacci sequence
F(T )
set of sequences in F that avoid
patterns from set T
G
graph
J(P )
set of order ideals of P
κ(σ)
core of σ
ξ
partially ordered generalized pattern
L[
→
x ]
set of polynomials in
→
x with coefficients in L
L[[
→
x ]]
set of formal power series in
→
x
L
n
Lucas sequence
l
A
(x, y) gf for the number of rises in the (palindromic)
compositions with parts in A
λ
τ
(n) number of compositions that are order-
isomorphic to τ
Λ
τ
(x) gf for λ
τ
(n)
λ
λ
1
,λ
2
,···,λ
k
poset of Young diagrams
lev(σ)
number of levels in σ
μ
mean of random variable X
μ
τ
content vector of τ
N(μ, σ
2
) Normal random variable with parameters μ, σ
2
N(0, 1) standard normal random variable
N
set of natural numbers = {1, 2, 3,...}
N
0
N ∪{0}
N(i)
neighborhood of vertex i
N
+
(i) set of out-neighbors of vertex i
N
−
(i) set of in-neighbors of vertex i
occ
τ
(σ) number of occurrences of τ in σ
occ
τ
(w) number of occurrences of τ in w
ord(σ)
order of σ
Ω
sample space
ω
ξ
(n, , s) number of occurrences of ξ among the
compositions of n with + k parts such that
the sum of the parts preceding the occurrence
is s
Ω
ξ
(x, y, u) gf for ω
ξ
(n, , s)
P(E)
probability that event E occurs
P (n)
number of palindromic compositions of n in N
P (x)
gf for P (n)
© 2010 by Taylor and Francis Group, LLC