Journal of Algebra Combinatorics Discrete Structures and Applications (JACODESMATH, Yildiz Technical University - YTU)

oai:ojs2.jacodesmath.com:article/1In this study, we consider linear and especially cyclic codes over the non-chain ring $Z_{p}[v]/\langle v^{p}-v\rangle$ where $p$ is a prime. This is a generalization of the case $p=3.$ Further, in this work the structure of constacyclic codes are studied as well. This study takes advantage mainly from a Gray map which preserves the distance between codes over this ring and $p$-ary codes and moreover this map enlightens the structure of these codes. Furthermore, a MacWilliams type identity is presented together with some illustrative examples

Bayram, Ayşegül

Siap, Irfan

English

Cyclic and constacyclic codes over a non-chain ring

We discuss tilings of a grid (of size n × 2) with dominoes of size 2 × 1. Parameters that might be called "longest run" are investigated, in terms of generating functions and also asymptotically. Extensions are also mentioned

Oliver, Kamilla

Prodinger, Helmut

JACODESMATH / ISSN 2148-838X
J. Algebra Comb. Discrete Appl.
1(1) • 19-27
Received: 18 May 2014; Accepted: 24 June 2014
DOI 10.13069/jacodesmath.09554
Journal of Algebra Combinatorics Discrete Structures and Applications
Horizontal runs in domino tilings
Research Article
Kamilla Oliver1∗, Helmut Prodinger2∗∗
1. 91502 Erlangen, Germany
2. Department of Mathematics, University of Stellenbosch 7602, Stellenbosch, South Africa
Abstract: We discuss tilings of a grid (of size n×2) with dominoes of size 2×1. Parameters that might be called
“longest run” are investigated, in terms of generating functions and also asymptotically. Extensions
are also mentioned.
2010 MSC: 05A15, 68R05
Keywords: Tiling, Generating function, Asymptotic, Bootstrapping, Mellin transform, Fibonacci numbers
1. Introduction
Donald Knuth [3] included tilings of an n × 2-rectangle using 2 × 1-sized tiles (“dominoes”) as an
introductory example of the use of generating functions. If Tn is the number of these tilings, then
Tn = Tn−1 + Tn−2, since we have two choices to start: one vertical domino, leaving an (n − 1) × 2-
rectangle, or two horizontal dominos, leaving an (n − 2) × 2-rectangle. Since T0 = 1 and T1 = 1, this
leads to Tn = Fn+1 (a Fibonacci number).
Here is one particular tiling of a 20× 2-rectangle:
Denoting T the family (=set) of all tiled n× 2-rectangles, for n ≥ 0, then we can write a symbolic
equation:
T = + T + T
∗ E-mail: olikamilla@gmail.com,
This author did most of her research while visiting the University of Stellenbosch in September 2013. She thanks
the department of mathematics for its hospitality.
∗∗ E-mail: hproding@sun.ac.za,
This author was supported by an incentive grant of the NRF of South Africa.
19
Horizontal runs in domino tilings
With the generating function
T (z) :=
∑
n≥0
Tnz
n,
the symbolic equation translates directly into
T (z) = 1 + zT (z) + z2T (z) =
1
1− z − z2 .
This equation is simple enough that, with partial fraction decomposition, one finds an explicit form
Tn =
1√
5
[(
1 +
√
5
2
)n+1
−
(
1−√5
2
)n+1]
.
The number
α :=
1 +
√
5
2
is called the golden ratio; it is one of the most important constants in mathematics. In terms of asympotics
it is dominating:
Tn ∼ 1√
5
(
1 +
√
5
2
)n+1
.
If one cannot resort to an explicit expression as above, one looks at the dominating singularity and writes
T (z) ∼ C
1− αz as z →
1
α
.
The constant C may be computed as
C = lim
z→ 1α
1− αz
1− z − z2 =
α√
5
.
In this paper, we are interested in the (consecutive) sequence of horizontal dominoes in a tiling. We
are looking for the longest substructure of the type in the figure.
We will indicate in Section 2 how the expected value of this parameter may be computed. Then, in
Section 3, we change our setting to tilings of n × 3 rectangles. Things become more involved, but it is
highly instructive to see how one has to deal with the difficulties. For more material of a similar type we
refer to [8].
2. The longest horizontal run in tilings of n× 2-rectangles
As the first step of our analysis, we decompose a tiled rectangle according to (maximal) runs of
horizontal dominoes. We indicate this for the example from the introduction: We see here runs of 3, 1,
and 2 (stacked) horizontal dominoes. So our parameter is 3 for this example. Various runs of length 0 are
20
K. Oliver, H. Prodinger
not indicated. Based on this (unique!) decomposition, we introduce T <h, the family of tiled dominoes
where the (maximal) run parameter is < h, we find
T <h =
<h( <h)∗
.
For completeness, we mention that the ‘∗’ operator (Kleene’s star in language theory) produces sequences.
If A is a set, then A∗ = A0 ∪ A1 ∪ A2 ∪ · · · , i.e., all sequences that can be formed from elements of A.
This operation is also useful when one deals with generating functions. If f(z) is the generating function
associated to A, so that the coefficient of zn (written as [zn]f(z)) counts the number of elements of size
n in A, then 11−f(z) is the generating function associated to A
∗. For general background we would like
to mention the book [2].
Here,
<h
=
h−1⋃
i=0
i
.
The lefthand side describes repetitions of with at most h− 1 elements; the righthand side splits the
repetitions into the various possibilities from i = 0, 1, . . . , h − 1 . In terms of generating functions, the
last expression translates into
1 + z2 + z4 + · · ·+ z2(h−1) = 1− z
2h
1− z2 .
Consequently, we get
T<h(z) =
1− z2h
1− z2
1
1− z(1−z2h)1−z2
=
1− z2h
1− z − z2 + z2h+1 .
One can see from this that, as h → ∞, which means no more restrictions on the run lengths, we find
again the generating function
T (z) =
1
1− z − z2 .
Further,
T≥h(z) := T (z)− T<h(z) = 1
1− z − z2 −
1− z2h
1− z − z2 + z2h+1
=
1− z2
1− z − z2
z2h
1− z − z2 + z2h+1 .
There is a dominant root ρh of 1− z − z2 + z2h+1, which is close to 1/α. So we set ρh := 1/α + εh and
continue
1− 1
α
− εh − 1
α2
− 2εh
α
+ α−2h−1 ∼ 0,
or
εh ∼
√
5α−2h−1.
21
Horizontal runs in domino tilings
We write
1− z − z2 + z2h+1 ∼
(
1− z
ρh
)
C,
and find
C = lim
z→ρh
1− z − z2 + z2h+1
1− zρh
∼
√
5
α
.
Now we can read off coefficients:
[zn]T≥h(z) ∼ α
n+1
√
5
− [zn] α√
5
1
1− z/ρh
=
αn+1√
5
− α√
5
ρ−nh
∼ α
n+1
√
5
− α√
5
( 1
α
+
√
5α−2h−1
)−n
=
αn+1√
5
− α
n+1
√
5
(
1 +
√
5α−2h
)−n
∼ α
n+1
√
5
− α
n+1
√
5
(
1−
√
5α−2h
)n
∼ α
n+1
√
5
− α
n+1
√
5
e−
√
5n/α2h .
Normalization leads to
[zn]T≥h(z)
Tn
∼ 1− e−
√
5n/α2h .
In order to compute the average value of our parameter, one has to sum this:∑
h≥1
(
1− e−
√
5n/α2h
)
.
It is very well understood how to get asymptotics for
f(x) :=
∑
h≥1
(
1− e−x/α2h
)
as x→∞, see [1]. One computes the Mellin transform
f∗(s) =
∑
h≥1
α2hs · Γ(s) = − α
2s
1− α2sΓ(s),
valid in 〈−1, 0〉 (the fundamental strip). Then one employs the inversion formula
f(x) = − 1
2pii
∫ − 12+i∞
− 12−i∞
α2s
1− α2sΓ(s)x
−sds,
shifts the line of integration to the right and takes the residues (with a negative sign) into account. The
contribution from the pole at s = 0 is
1
2
logα x+
γ
2 logα
− 1
2
.
22
K. Oliver, H. Prodinger
There is also a contribution coming from the simple poles at s = kpiilogα :
− 1
2 logα
∑
k 6=0
Γ
( kpii
logα
)
e−kpii·logα x.
This is a periodic function of small amplitude. Such functions occur frequently when one analyses run
statistics, see [8]. Altogether we found for the average of our parameter the asymptotic formula
1
2
logα n+
1
4
logα 5 +
γ
2 logα
− 1
2
− δ(
√
5n),
with
δ(x) := − 1
2 logα
∑
k 6=0
Γ
( kpii
logα
)
e−kpiix.
Let us emphasize that the paper [8] has many similar results, and concrete error terms and estimates
are worked out. Here, for the benefit of the reader, we suppress technical details and just stick to the
main ideas.
3. Tilings of n× 3-rectangles
Let us start with an example of a 20× 3-rectangle:
It decomposes in a natural way as follows:
Figure 1. Decomposition into blocks
The individual (maximal) blocks are of 3 types, as indicated in the figure:
Figure 2. First type
23
Horizontal runs in domino tilings
Figure 3. Second type
Figure 4. Third type
Again, we will look at
Figure 5. Maximal sequence of horizontal dominoes present (2 layers)
Let the three types with a sequence of exactly i horizontal (stacked) dominoes be denoted by F i,
G i, H i, then the family of dominoes with our run parameter < h can be described by
T <h =
(h−1⋃
i=0
F i
)[(h−1⋃
i=0
G i ∪
h−1⋃
i=0
H i
)(h−1⋃
i=0
F i
)]∗
.
In terms of generating functions (the variable z marks the length of the domino), we have the following:
h−1⋃
i=0
F i −→ 1 + z2 + · · ·+ z2(h−1) = 1− z
2h
1− z2 ,
h−1⋃
i=0
G i −→ z2 + · · ·+ z2h = z
2(1− z2h)
1− z2
and
h−1⋃
i=0
H i −→ z2 + · · ·+ z2h = z
2(1− z2h)
1− z2 .
Consequently
T<h(z) =
1− z2h
1− z2
1
1− 2z
2(1− z2h)
1− z2
1− z2h
1− z2
=
(1− z2)(1− z2h)
1− 4z2 + z4 + 4z2h+2 − 2z4h+2 .
24
K. Oliver, H. Prodinger
In the limit h→∞ (no restrictions), we find
T (z) =
1− z2
1− 4z2 + z4 ,
which was already derived in [3] using a different method. These functions only depend on z2, which is
clear, since a tiled n× 3-rectangle is only possible for even n. Thus we set w := z2 and work with
R<h(w) =
(1− w)(1− wh)
1− 4w + w2 + 4wh+1 − 2w2h+1
and
R(w) =
1− w
1− 4w + w2 .
There is a dominant root at w = 1/ρ with ρ = 2 +
√
3, and
R(w) ∼ 3−
√
3
6
1
1− ρz ,
and so
[wn]R(w) ∼ 3−
√
3
6
ρn.
There is a dominant root ωh = 1ρ + εh of
1− 4w + w2 + 4wh+1 − 2w2h+1.
One application of bootstrapping results in
εh =
2√
3ρh+1
.
From a historical point of view, it is interesting to point out that this procedure appeared for the first
time in [6].
A computation that is analogous to the one in the previous section yields
[wn]T≥h(z) ∼ 3−
√
3
6
ρn − 3−
√
3
6
ω−n
∼ 3−
√
3
6
ρn − 3−
√
3
6
(1
ρ
+ εh
)−n
=
3−√3
6
ρn − 3−
√
3
6
ρn
(
1 +
2√
3ρh
)−n
∼ 3−
√
3
6
ρn − 3−
√
3
6
ρn
(
1− 2√
3ρh
)n
.
Normalization leads to
[wn]T≥h(z)
[wn]T (z)
∼ 1− e− 2n√3ρh .
To compute the average, we need to evaluate∑
h≥1
(
1− e−x/ρh
)
,
with x = 2n/
√
3. The asymptotic evaluation is as before:
logρ n+ logρ 2−
1
2
logρ 3 +
γ
log ρ
− 1
2
− 1
log ρ
∑
k 6=0
Γ
(2kpii
log ρ
)
e−2piik·logρ(2n/
√
3 ).
25
Horizontal runs in domino tilings
4. The longest vertical run in tilings of n× 2-rectangles
For completeness, we briefly discuss how one can attack the parameter “longest vertical run.”
We introduce T <h, the family of tiled dominoes where the (maximal) run parameter is < h, we find
T <h =
<h
(
<h
)∗
.
In terms of generating functions, this means
T<h(z) =
1− zh
1− z − z2 + zh+2 .
We set again ρh = 1/α+ εh, and find
εh ∼ 1√
5
1
αh+2
.
Further,
[zn]T≥h(z)
Tn
∼ 1− e
√
5n/αh+1 .
The expected value is to be evaluated as ∑
h≥1
(
1− e−x/αk
)
,
with x =
√
5
α n. The asymptotic evaluation is
logα n+
1
2
logα 5 +
γ
logα
− 3
2
− 1
α
∑
k 6=0
Γ
( 2kpii
logα
)
e−2piik·logα(n
√
5/α);
n refers to the length of the tiled rectangle.
The case of an n×3-rectangle and runs of vertical tiles can also be done, but is a bit more elaborate.
It leads to a similar type of result.
5. Conclusion
We have demonstrated how to deal with runlength parameters: First, symbolic equations lead to
explicit forms of the associated generating functions. Then, one identifies the dominant singularity and
finds an approximate expression for the coefficients. The average value that one wants to compute is then
asymptotically described by a series. To work out asymptotics for this sum, the Mellin transform [1, 2]
is used. This series of operations works also in other contexts. A few references for further reading
are [4, 5, 7].
References
[1] P. Flajolet, X. Gourdon, P. Dumas, Mellin transforms and asymptotics: Harmonic sums, Theoretical
Computer Science 144, 3-58, 1995.
26
K. Oliver, H. Prodinger
[2] P. Flajolet, R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009.
[3] R. Graham, D. E. Knuth, O. Pathasnik, Concrete Mathematics, second edition, Addison Wesley,
Reading, 1994.
[4] C. Heuberger, H. Prodinger, Carry propagation in signed digit representations, European J. Combin,
24(3), 293-320, 2003.
[5] A. Knopfmacher, H. Prodinger. On Carlitz compositions, European J. Combin, 19(5), 579-589, 1998.
[6] D. E. Knuth, The average time for carry propagation, Nederl. Akad. Wetensch. Indag. Math., 40(2),
238-242, 1978.
[7] G. Louchard, H. Prodinger, Asymptotics of the moments of extreme-value related distribution func-
tions, Algorithmica, 46, 431-467, 2006.
[8] H. Prodinger, S. Wagner, Bootstrapping and double-exponential limit laws, submitted, 2012.
27


Horizontal runs in domino tilings

This paper investigates the ergodicity and the power rule of the topological pressure of a cellular automaton. If a cellular automaton is either leftmost or rightmost premutive (due to the terminology given by Hedlund [Math.~Syst.~Theor.~3, 320-375, 1969]), then it is ergodic with respect to the uniform Bernoulli measure. More than that, the relation of topological pressure between the original cellular automaton and its power rule is expressed in a closed form. As an application, the topological pressure of a linear cellular automaton can be computed explicitly

Not a member yet

Cyclic and constacyclic codes over a non-chain ring

Horizontal runs in domino tilings

Some properties of topological pressure on cellular automata

194

213