Heubach S., Mansour T. Combinatorics of Compositions and Words
Подождите немного. Документ загружается.
346 Combinatorics of Compositions and Words
1 2 3
1.5
1.0
0.5
0.5
1.0
1.5
Τ11
FIGURE 8.2:Thecurve1− g(z)with|z| =0.6.
as n →∞,whereμ =0.3506012746 and σ
2
=0.1339166786. Moreover,
CC (m; n) ≈
A
(ρ
∗
)
n
exp
%
−
(m−nμ)
2
2nσ
2
&
√
2πnσ
,
as n →∞and m − nμ = O(
√
n),withA and ρ
∗
as in (8.26).
Proof The result follows immediately from Theorems 8.28 and 8.29, as in
the proof of Theorem 8.35. 2
8.5.1 Asym ptotics for the rightmost part
We now consider the rightmost (or last) part in Carlitz compositions. Louc-
hard and Prodinger [134] gave the following result.
Theorem 8.49 [134, Section 2.2] Let X
L
(n) denote the last part in a random
Carlitz composition of n. Then the asymptotic distribution for X
L
(n) is given
by
P(X
L
(n)=k) ≈
(ρ
∗
)
k
1+(ρ
∗
)
k
uniformly for all k as n →∞.Thus,
E(X
L
(n)) ≈
k≥1
k(ρ
∗
)
k
1+(ρ
∗
)
k
=2.5833049669.
Note that this is a very different result from the ones we have derived so
far. There is no dependence on n in the average value! We will explore this
phenomenon in Exercise 8.12.
Proof Let F (z,w,q) be the generating function for the number of Carlitz
compositions of n ≥ 1 according to order n,numberofpartsm and rightmost
© 2010 by Taylor and Francis Group, LLC
Asymptotics for Compositions 347
(or last) part σ
m
,thatis,
F (z,w,q)=
n≥1
m≥1
σ
1
σ
2
···σ
m
∈C
n,m
z
n
w
m
q
σ
m
.
Letting F (z, w,q|j) denote the generating function for the number of Carlitz
compositions of n ≥ 1withm parts whose rightmost part is j, we obtain that
F (z,w,q)=
j≥1
F (z,w,q|j)
= w(F (z, w, 1) + 1)
j≥1
z
j
q
j
− w
j≥1
F (z,w,1|j)z
j
q
j
=
zwq
1 − zq
CC (z,w) − wF(z, w,zq), (8.27)
wherewehaveexpressedthecompositionswithm parts that end with j as
compositions with one fewer part and any last part, subtracting off those that
end in jj . Iterating (8.27) gives
F (z,w,q)=
j≥1
(−1)
j−1
z
j
w
j
q
1 − z
j
q
CC (z,w)=:G(z,w,q)CC (z, w) (8.28)
since w
n
F (z,w,z
n
q) → 0asn →∞(why?). Setting w = 1 in (8.28) we
derive from Theorem 8.25 that
[z
n
]F (z,1,q) ≈
G(ρ
∗
, 1,q)
(ρ
∗
)
n+1
∂
∂z
g(z,1)
(
(
z=ρ
∗
, (8.29)
as n →∞, uniformly for q in some complex neighborhood of the origin.
Using Lemma 8.14 to compute the expected value proves difficult, so we will
use (8.29) instead. We obtain that
P(X
L
= k) ≈
[q
k
]([z
n
]F (z,1,q))
[z
n
]F (z,1, 1)
=
[q
k
]G(ρ
∗
, 1,q)
G(ρ
∗
, 1, 1)
.
The last equality in (8.25) yields that G(z, w,1) = g(z,w),andinparticular,
G(ρ
∗
, 1, 1) = g(ρ
∗
) = 1. Now let’s determine the numerator of P(X
L
= k).
Since
G(z,1,q)=
j≥1
i≥1
q
i
z
ij
(−1)
j−1
=
i≥1
q
i
z
i
1+z
i
,
we obtain that
[q
k
]G(ρ
∗
, 1,q)=
(ρ
∗
)
k
1+(ρ
∗
)
k
,
which completes the proof of the result for P(X
L
= k). The expected value
follows from Definition 8.6 and the numerical value is obtained by approxi-
mating the infinite sum by a finite one. 2
We leave it to the interested reader to prove a similar result for unrestricted
compositions.
© 2010 by Taylor and Francis Group, LLC
348 Combinatorics of Compositions and Words
8.5.2 Asym ptotics for the largest part
Knopfmacher and Prodinger [119] also derived asymptotics for the average
size of the largest part in Carlitz compositions.
Theorem 8.50 [119, Section 4] Let X
max
(n) denote the largest part in a
random Carlitz composition of n.Then,
E(X
max
(n)) ≈ log
1/ρ
∗
n +0.64311 + d(log
1/ρ
∗
0.60829n),
where ρ
∗
=0.571349 and d(x) is a function that has period one, mean zero,
and small amplitude.
Comparing this result to Theorem 8.39 we see that the average largest parts
in compositions and Carlitz compositions, respectively, tend to infinity at the
same rate (up to a multiplicative constant).
Proof We know that
CC (z)=
1
1 −
j≥1
(−1)
j−1
z
j
1−z
j
=
1
1 − g(z)
,
with a dominant simple pole at ρ
∗
=0.571349. Next, we derive the generating
function CC
[h]
(z) for the number of Carlitz compositions of n with parts less
than or equal to h,andletCC
[h]
(z|j) be the generating function for those
compositions that end with j.Then
CC
[h]
(z)=1+
h
j=1
CC
[h]
(z|j). (8.30)
Clearly,
CC
[h]
(z|j)=z
j
+ z
j
h
i=1,i=j
CC
[h]
(z|i)=z
j
CC
[h]
(z) − z
j
CC
[h]
(z|j)
which yields
CC
[h]
(z|j)=
z
j
1+z
j
CC
[h]
(z). (8.31)
Combining (8.30) and (8.31) results in
CC
[h]
(z)=1+
h
j=1
z
j
1+z
j
CC
[h]
(z),
© 2010 by Taylor and Francis Group, LLC
Asymptotics for Compositions 349
which can be solved for CC
[h]
(z):
CC
[h]
(z)=
1
1 −
h
j=1
z
j
1+z
j
=
1
1 −
i≥1
(−1)
i−1
h
j=1
(z
i
)
j
=
1
1 −
i≥1
(−1)
i−1
z
i
− z
i(h+1)
1 − z
i
=
1
1 − g
h
(z)
.
Following the steps in the proof of Theorem 8.39 we obtain that the probability
for a random Carlitz composition to have largest part less than or equal to h
is approximated by
(1 + ε
h
)
−n
≈
1 −
1
(1 − ρ
∗
)g
(ρ
∗
)
(ρ
∗
)
h
n
with ρ
∗
=0.571349 and g
(ρ
∗
)=3.83517756. Substituting these values
into (8.16) gives the desired result. 2
8.5.3 Asymptotics for the number of distinct parts
We now present results on the average number of distinct parts in a random
Carlitz composition obtained by Goh and Hitczenko [73]. Their proof is dif-
ferent from the proof of Theorem 8.43 for the same statistic for unrestricted
compositions. We will give an outline of the proof by Goh and Hitczenko
which draws upon some of the ideas in the proofs of Theorems 8.39 and 8.50.
Theorem 8.51 [73, Theorem 1] The expected value of the number of distinct
parts in a random Carlitz composition of n as n →∞is given by
E(D
n
)=1.786495 logn − 2.932545 + d(ρ
∗
log(n/g
(ρ
∗
))) + o(1),
where the amplitude of d is bounded by 0.588234 · 10
−7
,andρ
∗
=0.571349 is
the pole of CC (z).
Proof We start by rewriting the expression for D
n
.LetB
j
be the event
that a composition has at least one part of size j.Thenwecanwrite
D
n
=
n
j=1
I
B
j
and therefore
E(D
n
)=
n
j=1
P(B
j
)=
n
j=1
(1 − P(B
c
j
)) =
n
j=1
1 −
CC
N\{j}
(n)
CC (n)
, (8.32)
© 2010 by Taylor and Francis Group, LLC
350 Combinatorics of Compositions and Words
where B
c
j
denotes the complement of B
j
, that is, the event that the compo-
sition does not contain the part j.LetCC
¯
j
(n) be the number of Carlitz com-
positions of n that do not use the part j. Then Example 4.8 with A = N\{j}
yields that the corresponding generating function is given by
CC
¯
j
(z)=
1
1+
z
j
1+z
j
−
i≥1
z
i
1+z
i
=
1
1 − g
j
(z)
,
where
g
j
(z)=g(z) −
z
j
1+z
j
. (8.33)
We now express the asymptotics for CC
¯
j
(n) in terms of those for CC (n). In
Section 8.5 we showed that CC (z)=
1
1−g(z)
has a unique singularity in the
disc |z|≤0.6 which occurs at ρ
∗
=0.571349. (Actually, this can be shown
to be true also for the larger disk |z| < 0.663.) Since g(z)andg
j
(z)donot
differ by too much, the functions g
j
(z) will also have a unique singularity, at
least for values of j that are sufficiently large. In fact, on the disc |z| < 0.663
and for j ≥ 6, the equation g
j
(z) = 1 has a unique real simple root ρ
j
in
the interval [0, 1]. Moreover, there exists δ>0 such that for all j ≥ 6the
following properties hold (see [73, Appendix]):
(1) 0 <ρ
j
≤ ρ
∗
+ δ,
(2) all roots ζ of the equation g
j
(z) = 1 other than ρ
j
satisfy |ζ|≥ρ
∗
+2δ,
(3) the ρ
j
are strictly decreasing and ρ
j
→ ρ
∗
as j →∞,thatis,ρ
j
= ρ
∗
+ε
j
where ε
j
= o(1).
Since g
j
(ρ
j
) = 1 by definition of ρ
j
, (8.33) together with ρ
j
= ρ
∗
+ ε
j
implies
that
1=g(ρ
∗
+ ε
j
) −
(ρ
∗
+ ε
j
)
j
1+(ρ
∗
+ ε
j
)
j
= g(ρ
∗
+ ε
j
) −
(ρ
∗
)
j
(1 + ε
j
/ρ
∗
)
j
1+(ρ
∗
)
j
(1 + ε
j
/ρ
∗
)
j
= g(ρ
∗
+ ε
j
)+
∞
i=1
−(ρ
∗
)
j
(1 + ε
j
/ρ
∗
)
j
i
.
Expanding the right-hand side into its Taylor series results in
1=g(ρ
∗
)+g
(ρ
∗
)ε
j
+ O(ε
2
j
) − (ρ
∗
)
j
(1 + ε
j
/ρ
∗
)
j
+ O((ρ
∗
)
2j
). (8.34)
Using (1 + ε
j
/ρ
∗
)
j
≈ 1andg(ρ
∗
) = 1, we solve (8.34) for ε
j
to obtain that
ρ
j
= ρ
∗
+ ε
j
= ρ
∗
+
(ρ
∗
)
j
g
(ρ
∗
)
+ o((ρ
∗
)
j
) (8.35)
which is sufficient for our needs. Let A
j
=
−1
g
j
(ρ
j
)
be the residue of
1
1−g
j
(z)
at
z = ρ
j
. Then the function
1
1−g
j
(z)
−
A
j
z−ρ
j
is analytical for |z|≤ρ
∗
+ δ and
© 2010 by Taylor and Francis Group, LLC
Asymptotics for Compositions 351
employing Theorem E.7 (the Cauchy coefficient formula) we get that
CC
¯
j
(n)=
−A
j
ρ
j
(ρ
j
)
−n
+ O((ρ
∗
+ δ)
−n
) (8.36)
similar to the proof of Theorem 8.24. Since g
j
(z)=g(z) −
z
j
1+z
j
we obtain
that g
j
(z)=g
(z) −
jz
j−1
(1 + z
j
)
2
, and together with (8.35) this results in
A
j
= −
1
g
(ρ
∗
)
+ O(j(ρ
∗
)
j
).
Substituting this value of A
j
and (8.35) into (8.36), we obtain that
CC
¯
j
(n)=
1
g
(ρ
∗
)
+ O(j(ρ
∗
)
j
)
1
%
ρ
∗
+(ρ
∗
)
j
1+o(1)
g
(ρ
∗
)
&
n+1
+ O((ρ
∗
+ δ)
−n
)
for some δ>0 (universally for j ≥ 6). This expression can now be used
in (8.32). Goh and Hitczenko established that (see [73, Lemma 3])
E(D
n
)=
n
j=1
1 −
CC
N\{j}
(n)
CC (n)
=
∞
j=0
(1 − (1 − (ρ
∗
)
j
M)
n
)+o(1) (8.37)
as n →∞,withM =1/g
(ρ
∗
). The proof of this lemma is rather techni-
cal, but the benefit is that we are back to a sum that we have encountered
previously, namely in (8.15). Therefore,
E(D
n
) ≈ log
1/ρ
∗
n +log
1/ρ
∗
M −
γ
log ρ
∗
+
1
2
+ d(log
1/ρ
∗
nM).
Substituting the values for ρ
∗
and M and simplifying gives the statement of
the theorem. For the more detailed bounds on the function d see [73]. 2
8.6 A word on the asymptotics for words
The astute reader may wonder why there is no chapter on the asymptotics
for words. The simple answer is that for words, the asymptotics are much
easier to obtain or are not very interesting. For example, the average number
of parts in a k-ary word of length n is always n. Some of the other statistics,
for example the largest part and the rightmost part, are very easy to obtain.
© 2010 by Taylor and Francis Group, LLC
352 Combinatorics of Compositions and Words
Example 8.52 Let X
L
(n) be the last part in a k-ary word of length n.Then
the number of words for which the last part is j is given by k
n−1
,whilethe
total number of words is given by k
n
, and therefore,
P(X
L
(n)=j)=
1
k
with E(X
L
(n)) =
k
j=1
j
1
k
=
k +1
2
.
Almost as easy is the determination of the average size of the largest part. Let
X
max
(n) be the largest part in a k-ary word of length n.Then
P(X
max
(n)=i)=
k
i
− k
i−1
k
n
,
and
E(X
max
(n)) =
n
i=1
i
k
i
− k
i−1
k
n
=
1 − (n +1)k
n
+ nk
n+1
k
n
(k − 1)
.
8.7 Exercises
Exercise 8.1 Let X
max
(n) denote the largest part in a random composition
of n.UseMathematica or Maple to compute the probability distribution of
X
max
(n) for n =1, 2,...,10 and then use the distributions to compute the
expected value and the variance of X
max
(n) for n =1, 2,...,10.
Exercise 8.2 Derive the asymptotic behavior for the average number of rises
in all palindromic compositions of n.
Exercise 8.3 Derive Equation (8.4), namely that
[x
n
]
∂
k
∂y
k
C(x, y)
(
(
(
(
y=1
= k! · 2
n−1−k
2
n
k
−
n − 1
k
for C(x, y)=(1− x)/(1 − x − xy).
Exercise 8.4 Derive the asymptotic behavior for the average number of rises
in all Carlitz compositions of n.
Exercise 8.5 Derive results analogous to those in Theorem 8.35 for the pat-
terns peak and valley.
Exercise 8.6 Derive the asymptotic behavior for the number of compositions
with r occurrences of the pattern 111 given in Example 8.38.
© 2010 by Taylor and Francis Group, LLC
Asymptotics for Compositions 353
Exercise 8.7 Show that the function
f
h
(z)=
m≥0
(z + z
2
+ ···+ z
h
)
m
=
1
1 −
z(1−z
h
)
1−z
=
1 − z
1 − 2z + z
h+1
has a simple pole as its dominant singularity. (Hint: use Rouch´e’s Theorem.)
Exercise 8.8 Let
c(n) be the number of Carlitz compositions of n with parts
in N ∪{0}.
(1) Find an explicit formula for the generating function
n≥0
c(n)z
n
.
(2) Prove that there is a dominant singularity for the generating function at
ρ =0.386960.
(3) Show that
c(n) ≈ 1.337604 ·(2.584243)
n
.
Exercise 8.9 Let C
P
(n) be the number of compositions of n whose parts are
prime numbers (that is, the parts are in P = {2, 3, 5, 7, 11, 13, 17, 19,...}).
(1) Find an explicit formula for the generating function
n≥0
C
P
(n)z
n
.
(2) Prove that C
P
(n) ≈ 3.293208186(1.476228784)
n
.
Exercise 8.10 Show that
n
1
k=n
0
C
k
+
2
n
≤
˜
C
√
n log n
n
→ 0 where n
0
and n
1
are
defined by (8.21) and (8.22).
Exercise 8.11 This exercise explores how to create random compositions us-
ing Mathematica or Maple.
(1) Write a function that creates the compositions of n. (In Mathematica,
you may use the function comps[n] defined in Example 8.4.) Use this
function to create the compositions of n =10and then create a random
sample of 200 compositions of n =10(by randomly selecting from all
compositions of n =10).
(2) Write a function that creates a random composition of n using the
method described in Proposition 8.42. (Hint: create a sequence of geo-
metric random variables until their sum becomes greater or equal to n
and then adjust the last value.) Now create 200 (random) compositions
of n =10.
(3) For each of the samples created in Parts (1) and (2) and the complete
set of compositions of n =10, enumerate the number of compositions
according to the largest part. Draw a bar chart for each of the three sets
of data and compare.
© 2010 by Taylor and Francis Group, LLC
354 Combinatorics of Compositions and Words
Exercise 8.12 This exercise explores the surprising result that the average
size of the last part of a Carlitz composition of n does not depend on n.
(1) Write a program in Maple or Mathematica to recursively create the Car-
litz compositions of n.
(2) Use this program to compute the probability distribution for the random
variable X
L
(n), the last part of a random Carlitz composition. That is,
compute P (X
L
(n)=k) for k =1, 2,...,n by directly enumerating the
Carlitz compositions according to the last part.
(3) Use Definition 8.6 and the probabilities computed in Part (2) to compute
the average size of the last part. Compare the expectation that you have
computed to the approximation given in Theorem 8.49.
Exercise 8.13
∗
In Exercises 6.9 and 6.10 we gave the generating functions
for the number of k-ary smooth and k-ary smooth cyclic words of length n.
Compute the asymptotic behavior for the number of k-ary smooth and k-ary
smooth cyclic words of length n as n →∞.
Exercise 8.14
∗
In Exercise 6.13 we gave the generating function for the num-
ber of smooth partition words of [n]. Show that the number of smooth partition
words of [n] with exactly k blocks is asymptotically given by
4
k +1
cos
2
π
2(k +1)
1+2cos
π
k +1
n−1
as n →∞.
Exercise 8.15
∗
A strong record in a word w
1
···w
n
is an element w
i
such
that w
i
>w
j
for all j =1, 2,...,i−1(that is, w
i
is strictly larger than all the
letters to the left of it).Aweak record is an element w
i
such that w
i
≥ w
j
for all j =1, 2,...,i − 1(that is, w
i
is greater than or equal to the letters
to the left of it). Furthermore, the position i is called the position of the
strong record (weak record). We denote the sum of the positions of all strong
(respectively, weak) records in a word w by srec(w)(respectively, wrec(w)).
Prodinger [165] originally studied the number of strong and weak records in
samples of geometrically distributed random variables. More recently, he gave
results on the expected value of the sum of the positions of strong records in
random geometrically distributed words of length n [166]. Prove that
(1) the average sum of the positions of the strong records E(X
srec
(n)) in
compositions of n has the asymptotic expansion
E(X
srec
(n)) =
n
4log2
1+δ (log
2
n)
+ o(n);
© 2010 by Taylor and Francis Group, LLC
Asymptotics for Compositions 355
(2) the average sum of the positions of the weak records E(X
wrec
(n)) in
compositions of n has the asymptotic expansion
E(X
wrec
(n)) =
n
2log2
1+δ (log
2
n)
+ o(n),
where δ(x) is a periodic function of period one, mean zero and small amplitude,
given by the Fourier series
δ(x)=
k=0
2kπı
log 2
Γ
−1 −
2kπı
log 2
e
2kπıx
.
Exercise 8.16
∗
We say that a word w = w
1
w
2
···w
n
has an ascent of size d
or more if w
i+1
≥ w
i
+ d for some i. For example, there are three ascents of
size two or more in the 4-ary words of length two, namely 13, 14,and24.Let
f
d
(n, j, s) be the number of compositions of n with last part j and s ascents
of size d or more. Define F
d
(z,u, v)=
n,j≥1
s≥0
f
d
(n, j, s)z
n
u
j
v
s
.
(1) Prove that the generating function F
d
(z,u, v) satisfies
F
d
(z,u, v)=
zu
1 − zu
(F
d
(z,1,v)+1)−
(1 − v)z
d
u
d
1 − zu
F
d
(z,zu, v).
(2) Iterate the recurrence in (1) to obtain that
F
d
(z,v):=1+F
d
(z,1,v)=
1
1 − G
d
(z,v)
where
G
d
(z,v)=
i≥0
(−1)
i
z
i+1
(1 − v)
i
z
d(i+1)i/2
i
k=1
(1 − z
k
)
.
(3) Let X
d
asc
(n) be the number of ascents of size d or more in a random
composition of n.Derivefrom(2) that for n ≥ d,
E(X
d
asc
(n)) =
2
−d
9
(3n − 3d − 2) +
2
9
(−1)
n−d
2
n
and
Var(X
d
asc
(n)) =
2
−d
3
n
1 −
2
−d
9
(13 + 6d)+
8 · 2
−2d
7
.
(4) Derive from (2) that the distribution of X
d
asc
(n) converges to a Gaus-
sian distribution with a rate of convergence of O(1/
√
n) with mean and
variance given in (3).
© 2010 by Taylor and Francis Group, LLC