Printer Friendly

Descents after maxima in compositions.

1 Introduction

Compositions of n are finite sequences of positive integers [([[sigma].sub.i]).sup.k.sub.i = 1] with k parts such that

[[sigma].sub.1] + [[sigma].sub.2] +... + [[sigma].sub.k] = n.

We define the first maximum om to be that part satisfying [[sigma].sub.m] > [[sigma].sub.i] for all i with 0 < i < m and [[sigma].sub.m] > [[sigma].sub.i] for all i such that m [less than or equal to] i [less than or equal to] k. Informally, the first maximum is the part which is larger than any parts to its left and not less than any parts to its right.

The variable of interest here is the size of the descent after the first maximum. We define the descent to be

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

where k is the number of parts.

Analogously we define the last maximum and the descent following it.

Two examples for the compositions of 17 illustrating these descents are:

Firstly, 135143. There is only one maximum, [[sigma].sub.3] = 5, so clearly the descent after the first or the last maximum is the same; it is 4.

Secondly, 13 3 5 5. There are two consecutive maxima where [[sigma].sub.4] = [[sigma].sub.5] = 5. The descent after the first maximum is 0 whereas the descent after the last maximum is 5.

Much recent work has been done on compositions. For example, see the book [9] and [1, 2, 7, 10]. In particular, ascents and descents in compositions were studied in [3] and maxima have been studied in [12].

We obtain generating functions for the descents occurring immediately after the first and the last maxima, by splitting these compositions into blocks that occur before and after these maxima. From this, we obtain generating functions for the average descents after the first or last maximum in compositions of n.

Using the Mellin transform, we find asymptotic expressions for these averages. In Section 5, we specify a simple bijection between the compositions of n in order to show that, on average, the descent after the last maximum is greater than the descent after the first maximum for compositions where n > 1.

2 Descent after the first maximum

2.1 Symbolic decomposition

We split the compositions of n into 2 cases, depending on where the first maximum occurs. It can either be before or at the end. Fixing h as the height of the maximum, we represent these cases symbolically in the diagram below:

In both cases, the three sub-compositions [[sigma].sub.1] ... [[sigma].sub.i-1], [[sigma].sub.i+2] ... [[sigma].sub.k] and [[sigma].sub.1] ... [[sigma].sub.k-1] allow the possibility of the empty composition. In the first case, if the sub-composition [[sigma].sub.1] [[sigma].sub.2] ... [[sigma].sub.i-1] is empty, the first maximum is at the start and the part ensures [[sigma].sub.i-1] that the maximum is before the end. The second case indicates that the only maximum occurs at the end.

2.2 Generating function for the descent after the first maximum

Our aim is to find the generating function F(x, y, u) where x counts the size of the composition, y the number of parts and u the size of the descent after the first maximum. (This, by symmetry, is equivalent to the generating function for the size of the ascent before the last maximum).

We need the following well-known lemma, see [8, 9].

Lemma 1 The generating function for compositions with largest part less than or equal to h where h [greater than or equal to] 0, is

[C.sub.h](x,y) = 1/[1 - y [[summation].sup.k.sub.j=1][x.sup.j]] = 1 - x/1 - x - xy + y[x.sup.h] + 1.

For a non-empty composition, let the size of the first maximum be h [greater than or equal to] 1. Firstly, consider the left case in Figure 1, the generating function for the single part [[sigma].sub.i+1] that is situated just after the first maximum is

y(x[u.sup.h-1] + [x.sup.2][u.sup.h-2] + ... + [x.sup.h]) = xy([u.sup.h] - [x.sup.h])/u -x.

Incorporating this term, the generating function [F.sub.h](x, y, u) that covers both cases shown in Figure 1 is

[F.sub.h](x,y,u) = [C.sub.h-1](x,y)y[x.sup.h] x xy([u.sup.h] - [x.sup.h])/u - x x [C.sub.h](x,y) + [C.sub.h-1](x,y)y[x.sup.h][u.sup.h]. (2.1)

Since this is for a fixed h, we need to sum over all possible values of h. Thus

F(x, y, u) = 1 + [[infinity].summation over h = 1][F.sub.h](x, y, u) = 1 + [[infinity].summation over h = 1] [C.sub.h-1](x,y)y[x.sup.h]([u.sup.h] + xy [[u.sup.h] - [x.sup.h]]/u - x [C.sub.h](x,y))

where the first term is for the empty composition. Thus by Lemma 1, we have our first result:

Theorem 1 The generating function for compositions of n where x counts the size of the composition, y the number of parts and u the size of the descent after the first maximum is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Putting y = 1, i.e., ignoring the number of parts, the generating function becomes

F(x, 1, u) = 1 + [[infinity].summation over h = 1] 1 - x/1 - 2x + [x.sup.h] [x.sup.h] ([u.sup.h] + x [[u.sup.h] - [x.sup.h]]/u - x [1 - x]/[1 - 2x + [x.sup.h+1]]). (2.2)

3 Sum of the descents after the first maximum

We are now in a position to find the sum of the descents after the first maximum in all the compositions of n. This is given by [[x.sup.n]][partial derivative]F(x,1,u)/[partial derivative]u [|.sub.u=1].

The derivative obtained from (2.2) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3.1)

We simplify this series by considering the finite sum to N and thereafter choosing N sufficiently large.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3.2)

To find the coefficient of [x.sup.n] in A(x), we may choose any N with N [greater than or equal to] n. Since we are only interested in the terms up to [x.sup.n], the last term 1 -[N.sub.x]/1 - 2x +[x.sup.N] + 1 can be replaced by 1 - Nx/1 - 2x. Thus, we wish to find the coefficient of [x.sup.n] in

[f.sub.N](x) := [1 + x - [x.sup.2]/1 - x] - [1 - Nx/1 - 2x] - [N.summation over h = 2] [x - (h + 1)[x.sup.h] + h[x.sup.h + 1]/1 - 2x + [x.sup.h]], (3.3)

where N [greater than or equal to] n. Here [[x.sup.n]][f.sub.N](x) = [[x.sup.n]][A.sub.N](x) = [[x.sub.n]]A(x) for n [less than or equal to] N.

For example, for N = 10, both series expansions for [f.sub.N](x) and A(x) begin with

x + 2[x.sup.2] + 6[x.sup.3] + 13[x.sup.4] + 29[x.sup.5] + 61[x.sup.6] + 131[x.sup.7] + 274[x.sup.8] + 576[x.sup.9] + 1199[x.sup.10]. (3.4)

We illustrate what is counted by the term 13[x.sup.4] in (3.4) in the table below:

Compositions of n = 4                 1111   211   121   112   13

Size of descent after first maximum    0      1     1     2     3

Compositions of n = 4                 31    22    4   Total

Size of descent after first maximum    2     0    4    13


3.1 Asymptotics

We rewrite the generating function (3.3) in the form

[f.sub.N](x) := [1 + x - [x.sup.2]/1 - x] + [-1 + x/1 - 2x] + [N.summation over h = 2] ([x/1 - 2x] - [x/1 - 2x + [x.sup.h]]) + [N.summation over h = 2] [(h + 1)[x.sup.h] - h[x.sup.h+1]/1 - 2x + [x.sup.h]].

The coefficients of [x.sup.n] in the first two terms of [f.sub.N](x) are 1 and -[2.sup.n -1], respectively for n > 1.

We next consider [[summation].sup.N.sub.h=2]([x/1 - 2x] - [x/1 - 2x + [x.sup.h]]). For h > 2, let [[rho].sub.h] be the smallest positive root of 1 2x + [x.sup.h] that lies between 1/2 and 1. An application of the principle of the argument shows such a root [[rho].sub.h] exists, with all other roots being of larger modulus. By dominant pole analysis, see [5, 6],

[q.sub.n,h] := [[x.sup.n]] [x/1 - 2x + [x.sup.h]] ~ [c.sub.h][[rho].sub.h.sub.-n] with [c.sub.h] = 1/2 - h[[rho].sup.h- 1.sub.h],

for large n.

The denominator 1 - 2x + [x.sup.h] behaves like a perturbation of 1 - 2x near x = 1/2, so one expects [[rho].sub.h] to be approximated by 1/2 as h [right arrow] [infinity]. By "bootstrapping" we find that

[[rho].sub.h] = 1/2(1 + [2.sub.-h] + O(h[2.sup.-2h])) (3.5)

and hence [c.sub.h] = 1/2 (1 + O(h[2.sup.-h])). As in Knuth [11] or Chapter 5 of [6], the dominant terms of [[summation].sup.n.sub.h=2][q.sub.n,h] occurs for a restricted range of h such as [n.sup.-3] [less than or equal to] [2.sup.-h] [less than or equal to] logn/n, for which

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Again, as in Knuth [11], we may incorporate the asymptotically small tails of the sums to show

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For x [member of] R, the Mellin transform of the function g(x) is

g*(s) = [[integral].sup.[infinity].sub.0] g(x)[x.sup.s-1]dx = ([summation over k [greater than or equal to]2] [2.sup.sh]) [GAMMA](s) = [2.sup.2s]/1 - [2.sup.s] [GAMMA](s), where - 1 < Re(s) < 0.

Here, we have used the fact that the Mellin transform of 1 - [e.sup.-x] is [GAMMA](s) = [[integral].sup.[infinity].sub.0] [e.sup.-x][x.sup.s-1]dx, for -1 < Re(s) < 0. To estimate the sum g(n) and hence [f.sub.n] we use the Mellin inversion formula,

g(x) = 1/2[pi]i [[integral].sup.-1/2+i[infinity].sub.-1/2-i[infinity]] g*(s)[x.sup.-s]ds.

We move the contour of integration to the right and must compute some residues as compensation.

Let [[chi].sub.k] = 2k[pi]i/log 2. There are simple poles of the integrand at s = [[chi].sub.k] for each k [member of] Z \ {0}, with negative residue

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For s = 0, we have a double pole with negative residue

[log.sub.2]x - 3/2 + [gamma]/log2,

where [gamma] is Euler's constant.

Combining the contributions for all k [member of] Z, we find that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

There remains to compute

[r.sub.n] := [[x.sup.n]][N.summation over h = 2](h + 1)[x.sup.h] + h[x.sup.1+h]/1 - 2x + [x.sup.h] = O ([[x.sup.n]][n.summation over h = 2] h[x.sup.h]/1 - 2x + [x.sup.h]).

As before, we can show that for the dominant range of terms in 2 [less than or equal to] h [less than or equal to] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Estimating the latter sum using Mellin transforms yields

[r.sub.n] = O([2.sup.n]logn/n).

For the mean value, we must divide by the number ([2.sup.n-1]) of compositions of n. In particular \ [r.sub.n]/[2.sup.n-1] [right arrow] 0 and we find

Theorem 2 The average descent after the first occurrence of the maximum in a composition of n is asymptotic to

[log.sub.2]n - 5/2 + [gamma]/[log.sub.2] - [delta]([log.sub.2]n) as n [right arrow][infinity]

where [delta](x) is a continuous periodic function of period 1, mean zero, small amplitude and Fourier expansion

[delta](x) = [summation over k [not equal to] 0][GAMMA]([[chi].sub.k])[e.sup.-2k[pi]ix].

4 Descent after the last maximum

Up to now, we have considered the descents after the first maximum in compositions of n. In this section, we consider the descents after the last maximum. A comparison of the series expansion (3.4), for the sum of descents after the first maximum, and (4.3) below, for the sum of descents after the last maximum shows that the two problems are not equivalent.

In symbolic notation, we have two cases depending on whether the last maximum occurs at the end or not. For the left case in Figure 2, we need the generating function for the single part of size less than h that immediately follows the maximum. This is given by

y(x[u.sub.h-1] + [x.sup.2][u.sup.h-2] +... + [x.sup.h-1]u) = yux [u.sup.h-1] - [x.sup.h-1]/u - x,

where x marks the size of the part, y the number of parts and u the size of the descent after the last maximum. Thus, combining the two cases and summing over h we obtain the generating function G(x, y, u) analogous to F(x, y, u) in Section 2.

G(x,y,u) = 1 + [[infinity].summation over h = 1] [C.sub.h](x,y)y[x.sup.h]([u.sup.h] + [C.sub.h-1](x,y)yux [u.sup.h-1] - [x.sup.h-1]/u - x),

where G(h) is from Lemma 1. After substituting y =1 and the expressions for [C.sub.h](x, 1) and [C.sub.h-1](x, 1),

we have

G(x,1,u) = 1 + [[infinity].summation over h = 1] [(1 - x)[x.sup.h] ([u.sup.h] + ux(1-x)([u.sup.h-1] - [x.sup.h-1])/u - x)(1 - 2x + [x.sup.h])]/1 - 2x + [x.sup.h+1]

we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then the generating function for the sum of the descents after the last maximum is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus we have shown

Theorem 3 The generating function for the sum of the descents after the last maximum in compositions of n is

[[infinity].summation over h = 1] ([h + x - hx/x] + [x(2 - h)/1 - 2x + [x.sup.h]] - [h + x - 3hx + h[x.sup.2]/x(1 - 2x + [x.sup.h+1])])

where x marks the size of the composition.

To proceed with our calculations, we let the upper limit of the sum be N and later choose N sufficiently large. Thus, we consider

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.1)

for N [greater than or equal to] n. This has the same coefficient of [x.sup.n] as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4.2)

Thus [[x.sup.n]]B(x) = [[x.sup.n]][b.sub.N](x) for N [greater than or equal to] n. For example, for N = 10, the series expansion for the expressions for B(x) and [b.sub.10](x) both begin with

x + 3[x.sup.2] + 7[x.sup.3] + 16[x.sup.4] + 34[x.sup.5] + 73[x.sup.6] + 152[x.sup.7] + 318[x.sup.8] + 658[x.sup.9] + 1360[x.sup.10]. (4.3)

The coefficient of [x.sup.4] is illustrated in the table below:

Compositions of n = 4                1111   211   121   112   13

Size of descent after last maximum    1      1     1     2     3

Compositions of n = 4                31    22    4   Total

Size of descent after last maximum    2     2    4    16


4.1 Asymptotics

Here, we use Mellin transforms to study the average size of the descent after the last maximum in a composition of n.

Theorem 4 The average descent after the last occurrence of the maximum in a composition of n is asymptotic to

[log.sub.2]n - 5/2 + [gamma]/[log.sub.2] - [delta]([log.sub.2]n)

where [delta](x) is a continuous periodic function of period 1, mean zero, small amplitude and Fourier expansion

[dleta](x) = [summation over k [not equal to] 0][GAMMA]([[chi].sub.k])[e.sup.-2k[pi]ix].

Proof: We rewrite the generating function in (4.2) in the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the coefficients of [x.sup.n] in the first two terms are 1 and - [2.sup.n-1] respectively for n [greater than or equal to] 1. Given n we choose N such that N [greater than or equal to] n.

As before, let [[rho].sub.h] = 1/2(1 + [2.sup.-h] + O(h[2.sup.-2h])) be the smallest positive root of 1 - 2x + [x.sup.h]. Then

[[x.sup.n]](- [1 - 3x + [x.sup.2]/x(1 - 2x)]) = [2.sup.n-1]

and

[[??].sub.n,h] := [[x.sup.n]](- [1 - 3x + [x.sup.2]/x(1 - 2x + [x.sup.h])]) ~ [C.sub.h][[rho].sup.-n.sub.h]

with

[C.sub.h] = 1/2(1 + O(h[2.sup.-h])).

Thus, once again [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for the dominant range of h with h [less than or equal to] n. Then, for any n and N chosen such that N [greater than or equal to] n, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This is precisely the same as the sum estimated by Mellin transforms in the proof of Theorem 2.

Also as in the proof of Theorem 2, we find

[[x.sup.n]] [N.summation over h = 2] [h[x.sup.h] + [x.sup.h+1] - h[x.sup.h+1]/x(1 - 2x + [x.sup.h])] = O([2.sup.n] logn/n).

Dividing by [2.sup.n-1] to obtain the mean value yields the same asymptotic result as in Theorem 2. ?

Remark: Even though we have the same asymptotic results in Theorems 2 and 4, the series expansions (3.4) and (4.3) illustrate the fact that the sum of descents are in fact greater in the case of the last maximum, than they are for the first maximum, for n > 1.

5 Bijection to show that on average the descent after the last maximum is greater than the descent after the first

In this section, we show with the use of a simple bijection f between the compositions of n > 1, that the average descent after the last maximum is greater than the average descent after the first maximum.

The bijection is defined as follows:

The composition is mapped to itself if it is one of the following 3 types:

Type 1: the composition has only one maximum.

Type 2: the composition has 2 or more maxima, where one of them occurs at the end.

Type 3: the composition has 2 or more maxima, none of which occur at the end and the first maximum is immediately followed by a maximum.

However, if we have

Type 4: the composition has 2 or more maxima, none of which occur at the end and the first one is not followed immediately by a maximum, then the bijection swaps the positions of the two elements which occur after the first and last maxima and preserves the rest.

We illustrate the bijection for a composition of type 4 below.

Consider the composition 26136651. It has 3 maxima, none occur at the end and the first maximum [[sigma].sub.2] = 6 is not followed directly by another maximum. We swap [[sigma].sub.3] = 1 with [[sigma].sub.7] = 5 and therefore the composition is mapped to 26536611 as illustrated using bargraphs below:

We define [F.sub.i] (resp. [L.sub.i]) to be the sum of the descents after the first (resp. last) maximum of compositions of type i = 1,2,3,4. Thus, for i = 1 and 4 we have [F.sub.i] = [L.sub.i] and for i = 2 and 3 we have [F.sub.i] < [L.sub.i].

So, collectively, we have

[partial derivative]F/[partial derivative]u[|.sub.u=1] = [4.summation over i = 1][F.sub.i], and [partial derivative]G/[partial derivative]u[|.sub.u=1] = [4.summation over i = 1][L.sub.i]

for the first descents and last descents respectively.

It is clear that f is a bijection on each of the disjoint types. Thus

[partial derivative]G/[partial derivative]u[|.sub.u=1] - [partial derivative]F/[partial derivative]u[|.sub.u=1] = ([L.sub.2] - [F.sub.2]) + ([L.sub.3] - [F.sub.3]) > 0

which is our required result.

References

[1] M. Archibald and A. Knopfmacher, The largest missing value in a composition of an integer, Discrete Math. 311 (2011), 723-731.

[2] M. Bona and A. Knopfmacher, On The Probability that certain compositions have the same number of parts, Annals of Combinatorics 14 (2010), 291-306.

[3] C. Brennan and A. Knopfmacher, The distribution of ascents of size d or more in compositions of n, Discrete Mathematics and Theoretical Computer Science 11:1 (2009), 1-10.

[4] P. Chinn and S. Heubach and R. Grimaldi, Rises, levels, drops and "+" signs in compositions: extensions of a paper by Alladi and Hoggart, The Fibonacci Quarterly 3:41 (2003), 229-239.

[5] P. Flajolet, X. Gourdon and P. Dumas, Mellin transforms and asymptotics: Harmonic sums, Theoretical Computer Science 144 (1995), 3-58.

[6] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[7] S. Heubach, A. Knopfmacher, M. Mays and A. Munagi, Inversions in compositions of integers, Quaestiones Mathematicae 34 (2011), 187-202.

[8] S. Heubach, T. Mansour, Compositions of n with parts in a set, Congressus Numerantium 168, (2004), 127-143.

[9] S. Heubach, T. Mansour, Combinatorics of compositions and words, Discrete Mathematics and its applications, CRC press, Taylor and Francis group, 2010.

[10] A. Knopfmacher and M. E. Mays, Compositions with m distinct parts, Ars Combinatoria 53 (1999), 111-128.

[11] D. E. Knuth, The average time for carry propagation, Indagationes Math. 40 (1978), 238-242.

[12] A. M. Odlyzko and B. Richmond, On the compositions of an integer, Lecture Notes in Mathematics, 829 (1980), 199-210.

Aubrey Blecher, Charlotte Brennan, Arnold Knopfmacher

The John Knopfmacher Centre for Applicable Analysis and Number theory, School of Mathematics, University of the Witwatersrand, Private Bag 3, Johannesburg, South Africa.

received 21stMay 2013, revised 10th Feb. 2014, accepted 17th Feb. 2014.

(i) Emails: Aubrey.Blecher@wits.ac.za, Charlotte.Brennan@wits.ac.za,

Arnold.Knopfmacher@wits.ac.za
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Author:Blecher, Aubrey; Brennan, Charlotte; Knopfmacher, Arnold
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Report
Geographic Code:6SOUT
Date:Jan 1, 2014
Words:3788
Previous Article:Computation with no memory, and rearrangeable multicast networks.
Next Article:Graphs where every k-subset of vertices is an identifying set.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters