Inversions and Parity in Compositions of Integers

M. Archibald, A. Blecher, and A. Knopfmacher

The John Knopfmacher Centre for Applicable Analysis and Number Theory

University of the Witwatersrand Johannesburg South Africa

             Margaret.Archibald@wits.ac.za
               Aubrey.Blecher@wits.ac.za
             Arnold.Knopfmacher@wits.ac.za

M. E. Mays West Virginia University Morgantown, WV 26506-6310 USA

               Michael.Mays@mail.wvu.edu

Abstract

A composition of a positive integer n is a representation of n as an ordered sum of positive integers a_{1} + a_{2} + ⋯ + a_{m} = n. There are 2^{n−1} unrestricted compositions of n, which can be classified according to the number of inversions they contain. An inversion in a composition is a pair of summands {a_{i}, a_{j}} for which i < j and a_{i} > a_{j}. We consider compositions of n counted according to whether they contain an even number or an odd number of inversions, and include results on compositions where the first part occurs with odd multiplicity. The following statistics are also computed for compositions of n: total number of inversions, total sum of inversion sizes, and number of inversions of size d or more.

1 Introduction

A composition of the positive integer n is a representation of n as an ordered sum of positive integers n = a_{1} + a_{2} + ⋯ + a_{m}. An inversion in a composition is a pair of summands {a_{i}, a_{j}} for which i < j and a_{i} > a_{j}. For example, the five part composition of nine given as 9 = 1+3+2+1+2 has four inversions, comparing the second summand to the third, fourth, and fifth, and comparing the third summand to the fourth. The set of compositions of n is called C(n).

Firstly, we extend results from Heubach et al. [2] to account for patterns inherent in Tables 1 and 2 for the statistic

ic_{r}(n) = number of compositions of n with r inversions.

In this paper we consider the cases r even (Ev(n)) and r odd (Od(n)) and the sum on all values of r.

The discussion on the parity of the number of inversions has the effect of extending “even” and “odd,” as usually applied to permutations, to permutations of multisets.

A partition of n written in standard nondecreasing order is a composition with no inversions (ic_{0}(n) = p(n)) and hence is even. More generally, the number of inversions in a composition can be seen as a measure of the degree to which a composition differs from a partition.

In addition, ic_{1}(n) is discussed in Heubach et al. [2] and described in \underline{A058884} as “partial sums of the partition function p(n) with the last term subtracted.” This means, for example, ic_{1}(6) = 8 is given by the column 0 entries 1 + 1 + 2 + 3 + 5 + 7 − 11. Knopfmacher et al.

[4] also study ic_{1}(n) to ic_{5}(n).

This paper is divided into five sections. In Section 2, we study the frequency of compositions with an odd or even number of inversions. We follow that up with the total number of inversions in all compositions of n (Section 3). By considering the size of each inversion in Section 4, we sum the size of all inversions across compositions of n, and then sum inversions of size d or more in Section 5. Finally, in Section 6, we return to the idea of parity and study compositions with the first part occurring with odd multiplicity.

2 Relative frequency of even and odd compositions

A table of values of ic_{r}(n) is provided in Table 1. Rows are indexed by n, columns are indexed by r, and table entries give values for ic_{r}(n). We are interested in row sums of values in the even columns and in the odd columns, consolidated in the last columns Ev and Od. Knopfmacher et al. [4] analyse table entries column by column to derive generating function identities and consider asymptotic results.

Values of | Ev(n)| (resp., | Od(n)|) can be recovered by summing the entries in row n of Table 1 for the columns with even (odd) indices. We see the first few values for the compositions in Ev(n) in Table 2.

\begin{matrix}n\r & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & … & Ev & Od \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … & 1 & 0 \\ 2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … & 2 & 0 \\ 3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … & 3 & 1 \\ 4 & 5 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & … & 6 & 2 \\ 5 & 7 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & … & 10 & 6 \\ 6 & 11 & 8 & 7 & 4 & 2 & 0 & 0 & 0 & 0 & 0 & … & 20 & 12 \\ 7 & 15 & 15 & 14 & 10 & 6 & 3 & 1 & 0 & 0 & 0 & … & 36 & 28 \\ 8 & 22 & 23 & 26 & 21 & 17 & 10 & 6 & 2 & 1 & 0 & … & 72 & 56 \\ 9 & 30 & 37 & 44 & 42 & 36 & 27 & 19 & 11 & 6 & 3 & … & 136 & 120 \\ 10 & 42 & 55 & 73 & 74 & 73 & 60 & 50 & 34 & 24 & 13 & … & 272 & 240 \\ 11 & 56 & 83 & 115 & 128 & 133 & 123 & 109 & 87 & 68 & 48 & … & 528 & 496 \\ 12 & 77 & 118 & 177 & 209 & 235 & 230 & 223 & 192 & 166 & 129 & … & 1056 & 992 \end{matrix}

Table 1: Compositions with r inversions, ic_{r}(n)

The sequence of values Ev(2n−1) : 1, 3, 10, 36 … appears in the On-Line Encyclopedia of Integer Sequences (OEIS) as \underline{A007582}. There are several interesting combinatorial contexts mentioned there, but none explicitly involves compositions. We also find Ev(n) at \underline{A005418}, Ev(2n) at \underline{A063376}, and corresponding sequences of odd compositions at \underline{A032085}, \underline{A006516}, and \underline{A020522}.

First we account for the entries in Table 2.

Theorem 1. Let n be a positive integer. Then

(1) | Ev(2n)| = 2| Ev(2n − 1)|;

(2) | Ev(2n + 1)| = 2| Ev(2n)| − 2^{n−1};

(3) | Od(2n)| = 2| Od(2n − 1)|;

(4) | Od(2n + 1)| = 2| Od(2n)| + 2^{n−1}.

Proof. We consider a process to construct compositions of size m + 1 from compositions of size m, and explore how the process affects the parity of the compositions before and after. First we consider claim (1), where m = 2n − 1.

We construct compositions of 2n by starting with a composition of size 2n − 1 and applying two processes:

(a) Prepend a 1, so, e.g., 3 + 3 + 1 → 1 + 3 + 3 + 1

(b) Augment the first summand by 1, so, e.g., 3 + 3 + 1 → 4 + 3 + 1

\begin{matrix}n & | Ev(n)| & | Ev(n)|/|C(n)| \\ 1 & 1 & 1. \\ 2 & 2 & 1. \\ 3 & 3 & 0.75 \\ 4 & 6 & 0.75 \\ 5 & 10 & 0.625 \\ 6 & 20 & 0.625 \\ 7 & 36 & 0.5625 \\ 8 & 72 & 0.5625 \\ 9 & 136 & 0.53125 \\ 10 & 272 & 0.53125 \\ 11 & 528 & 0.515625 \\ 12 & 1056 & 0.515625 \\ 13 & 2080 & 0.5078125 \\ 14 & 4160 & 0.5078125 \\ 15 & 8256 & 0.50390625 \end{matrix}

Table 2: Compositions of even parity

This is a familiar construction. See, for example, work by Tripathi [8], which will be used in various forms throughout this paper.

It is clear that the two processes yield distinct compositions of 2n and that the total number of compositions is equal to 2^{2n−2} + 2^{2n−2} = 2^{2n−1}, the number of compositions of 2n, so all compositions of 2n are uniquely accounted for. Also, process (a) does not introduce any inversions, so the number of even compositions of 2n arising from application of process (a) matches | Ev(2n − 1)|.

For process (b), it may be that an even composition is mapped to an even composition, in which case the correspondence is preserved. We analyse the situation if an even composition is mapped to an odd composition or an odd composition is mapped to an even composition via a general observation that will be useful later.

At this stage it is important to note that if we consider a_{1} + a_{2} + ⋯ + a_{k} ∈ C(m) such that (a_{1} +1)+a_{2} +⋯+a_{k} ∈ C(m+1) has a different parity, then a_{1} occurs an even number of times. This is because there is no change in the number of inversions arising from the parts a_{2}, a_{3}, …, a_{k}, and any inversion between a_{1} and a later summand remains an inversion between a_{1} + 1 and that later summand, so the only change in the inversion count comes from comparing a_{1} + 1 with later occurrences of size a_{1}. If the parity is to change, there must be an odd number of later occurrences of size a_{1}, hence there were an even number of occurrences of parts of size a_{1} in the original composition.

Returning to the analysis of process (b), consider a parity-changing composition a_{1} + a_{2} + ⋯ + a_{k}. Look for the first pair of summands (a_{2}, a_{3}), (a_{4}, a_{5}), … that are distinct. Such a pair has to exist, or else the even number of occurrences of a_{1}, and the duplicated entries in each pair, adds up to an even number, and we started with 2n−1, an odd number. Define a bijection on the parity-changing compositions of 2n − 1 by switching the summands in this pair. This provides a one to one correspondence between the even → odd and the odd → even compositions, guaranteeing they are equinumerous, so process (b) generates as many even compositions of 2n as there were even compositions of 2n − 1. Thus the even composition count of process (a) and process (b) guarantees that | Ev(2n)| = 2| Ev(2n − 1)|.

Now we consider claim (2), by starting with C(2n). Process (a) and process (b) still apply to generate all compositions of 2n+1. Again process (a) preserves the inversion count of the composition of 2n. For process (b), the lemma lets us focus on parity-changing compositions characterized by an even number of occurrences of the first summand in the composition of 2n. In this case, however, the bijection between even and odd compositions of 2n might fail, in the case that there are no pairs of summands (a_{2}, a_{3}), (a_{4}, a_{5}), … that are distinct. For the bijection to fail, it must be the case that, since there are an even number of occurrences of size a_{1}, the last summand must be of size a_{1}, and the shape of the composition is

a_{1} + a_{2} + a_{2} + a_{4} + a_{4} + ⋯ + a_{l} + a_{l} + a_{1}.

There are as many ways this can happen as there are compositions a_{1} + a_{2} + ⋯ + a_{l} of n, which is 2^{n−1}. All of these send an even composition of 2n to an odd composition of 2n + 1 via process (b). Hence there is a deficit of 2^{n−1} even compositions among the compositions of 2n + 1, and overall we have | Ev(2n + 1)| = 2| Ev(2n)| − 2^{n−1}.

Claims (3) and (4) about Od(n) follow since | Od(n)| + | Ev(n)| = |C(n)| = 2^{n−1}.

We solve the recurrences from Theorem 1, to obtain

Corollary 2. Formulas for the parity counting composition functions for n ≥ 1 are as follows:

(1) | Ev(2n)| = 2^{2n−2} + 2^{n−1};

(2) | Ev(2n − 1)| = 2^{2n−3} + 2^{n−2};

(3) | Od(2n)| = 2^{2n−2} − 2^{n−1};

(4) | Od(2n − 1)| = 2^{2n−3} − 2^{n−2}.

We use the formulas above to observe that, asymptotically, the number of even and odd compositions match.

Corollary 3. lim_{n→∞} \frac{| Ev(n)|}{|C(n)|} = lim_{n→∞} \frac{| Od(n)|}{|C(n)|} = \frac{1}{2}.

3 Total number of inversions

Let ic(n) denote the total number of inversions in all compositions of n. Then

ic(n) = ∑_{r=1}^{n} ic_{r}(n)

(see Table 1). The sequence generated by this formula is in the OEIS as \underline{A189052}.

For the theorem that follows, we need the following result which we include as a lemma and which can also be found in books by Heubach and Mansour [3] or Sedgewick and Flajolet [6].

Lemma 4. The total number of parts of size one in all compositions of n is

u(n) := \begin{cases}(n + 2)2^{n−3}, & for n ≥ 2; \\ 1, & for n = 1. \end{cases}  (1)

This appears in the OEIS as \underline{A045623}.

Proof. First, create a composition of n+1 from a composition of n by either appending a part of size one to the end of the composition or adding one to the last part in the composition. In this way we create a recurrence for u(n) (valid for n ≥ 2) as follows.

u(n + 1) = \underbrace{u(n) + 2^{n−1}}_{append a one} + \underbrace{u(n) − 2^{n−2}}_{add one to last part},  (2)

where

u(2) = 2.

This recurrence holds since the number of ones in all compositions of n+1 is the same as the number of ones in all compositions of n, but there is an additional one for each composition of n (of which there are 2^{n−1}). Also, adding one to the last part of a composition of n decreases the total number of ones by one for each composition of n which originally ended in a one. There are 2^{n−2} of these, as half of all compositions of n must end in a one.

Simplifying the recurrence in Equation (2) above, we get

u(n + 1) = 2u(n) + 2^{n−2},

and solving it gives the result in Lemma 4.

Theorem 5. The total number of inversions in all compositions of n is

ic(n) = \frac{2^{n−4}}{27} (9n^{2} − 3n − 22) − \frac{2}{27}(−1)^{n}.  (3)

Heubach et al. [2] derived this expression via generating functions. We are now able to give a more combinatorial proof.

Proof. We use a similar method to that used in Theorem 1, and make use of the following two procedures for creating a composition of n+1 from a composition of n. In this case, it is more convenient to append and add to the end rather than the beginning of the composition.

Let π be a composition of n and denote a composition which ends in a part of size a as π|a. We construct π′ (a composition of n + 1) from π as follows:

(a) append a part of size one to the end of π

(b) add one to the last part of π

In the first procedure the number of additional inversions is the total number of parts in π minus the total number of parts of size one in π.

In the second procedure the number of inversions of π|a (for a fixed a) decreases by the number of parts in π of size a + 1 which is the same as the number of parts of size a + 1 in π′ (excluding the last part).

Before continuing, we note that the number of parts of size a + 1 in compositions of n − a is equinumerous with the number of parts of size one in compositions of n − 2a, for 1 ≤ a. For each part of size a + 1 in a composition of n − a, subtract a from that part. This gives a part size of one in a composition which is now of size n − 2a. Conversely, for any part of size one in a composition of n − 2a, a can be added to that part to get a part of size a + 1 in what is now a composition of n − a.

We use this bijection and combine the two procedures above over all compositions of n to get the following recursion:

ic(n + 1) = \underbrace{ic(n) + (n + 1)2^{n−2} − u(n)}_{Procedure 1} + \underbrace{ic(n) − ∑_{a=1}^{⌊ \frac{n}{2} ⌋} u(n − 2a)}_{Procedure 2}  (4)

which can be simplified to

ic(n + 1) = 2 ic(n) + (n + 1)2^{n−2} − ∑_{a=0}^{⌊ \frac{n}{2} ⌋} u(n − 2a).  (5)

Because the formula for u(n) in Equation (1) only holds for n ≥ 2, we exclude the upper limit of the sum on a to evaluate:

∑_{a=0}^{⌊ \frac{n}{2} ⌋−1} u(n − 2a) = (n + 2)2^{n−3} ∑_{a=0}^{⌊ \frac{n}{2} ⌋−1} 2^{−2a} − 2^{n−2} ∑_{a=0}^{⌊ \frac{n}{2} ⌋−1} a2^{−2a}

= \frac{1}{9}2^{n−1−2⌊ \frac{n}{2} ⌋}((4^{⌊ \frac{n}{2} ⌋} − 1)(4 + 3n) + 6⌊\frac{n}{2}⌋)

= \frac{2^{n}}{18}(4 + 3n − 4 · 2^{−2⌊ \frac{n}{2} ⌋} − 3n2^{−2⌊ \frac{n}{2} ⌋} + 6⌊\frac{n}{2}⌋2^{−2⌊ \frac{n}{2} ⌋}),

and note that the last term in the sum on a is

u (n − 2⌊\frac{n}{2}⌋) = \begin{cases}u(n − 2\frac{n}{2}), if n is even; \\ u(n − 2\frac{n−1}{2}), if n is odd; \end{cases}

= \begin{cases}u(0), if n is even; \\ u(1,) if n is odd; \end{cases}

= \begin{cases}0, if n is even; \\ 1, if n is odd. \end{cases}

We make use of the Kronecker delta function to express this, and write

δ_{n} := \begin{cases}0, if n is even; \\ 1, if n is odd. \end{cases}

Hence the recursion for the function ic(n) becomes

ic(n + 1) =2 ic(n) + (n + 1)2^{n−2}
− \frac{2^{n}}{18}(4 + 3n − 4 · 2^{−2⌊ \frac{n}{2} ⌋} − 3n2^{−2⌊ \frac{n}{2} ⌋} + 6⌊\frac{n}{2}⌋2^{−2⌊ \frac{n}{2} ⌋}) − δ_{n}  (6)

which can be solved (noting that ic(2) = ic(1) = 0) to get

ic(n + 1) =2^{n−2} ∑_{i=0}^{n−2}(i + 3) − ∑_{i=0}^{n−2} δ_{n−i}2^{i}

− \frac{2^{n}}{18} ∑_{i=2}^{n} (4 + 3i − 4 · 2^{−2⌊ \frac{i}{2} ⌋} − 3i2^{−2⌊ \frac{i}{2} ⌋} + 6⌊\frac{i}{2}⌋2^{−2⌊ \frac{i}{2} ⌋}).

The three sums involving the floor function are most easily evaluated by splitting the sum into two cases: odd and even. In this way we calculate:

∑_{i=2}^{n} 2^{−2⌊ \frac{i}{2} ⌋} = \begin{cases}2 ∑i=1^{\frac{n−1}{2}} 2^{−2i}, & for n odd; \\ 2 ∑i=1^{\frac{n−2}{2}} 2^{−2i} + 2^{−n}, & for n even; \end{cases}  (7)

= \begin{cases}\frac{2}{3} − \frac{4}{3·2^{n}} , & for n odd; \\ \frac{2}{3} − \frac{5}{3·2^{n}} , & for n even; \end{cases}  (8)

and similarly:

∑_{i=2}^{n} i2^{−2⌊ \frac{i}{2} ⌋} = \begin{cases}\frac{1}{9·2^{n}} (−26 + 19 · 2^{n} − 12n), & for n odd; \\ \frac{1}{9·2^{n}} (−28 + 19 · 2^{n} − 15n), & for n even; \end{cases}  (9)

and

∑_{i=2}^{n} ⌊\frac{i}{2}⌋2^{−2⌊ \frac{i}{2} ⌋} = \begin{cases}\frac{2}{92^{n}} (−5 + 2^{2+n} − 3n), & for n odd; \\ \frac{1}{92^{n+1}} (−16 + 2^{4+n} − 15n), & for n even. \end{cases}  (10)

Again a parity split is useful for

∑_{i=0}^{n−2} δ_{n−i}2^{i} = \begin{cases}∑i=0^{\frac{n−3}{2}} 2^{2i}, & for n odd; \\ ∑i=0^{\frac{n−4}{2}} 2^{2i+1}, & for n even; \end{cases}  (11)

= \begin{cases}\frac{1}{6}(2^{n} − 2), & for n odd; \\ \frac{1}{6}(2^{n} − 4), & for n even. \end{cases}  (12)

We can now put all of these together. We leave it as two separate cases to simplify and then combine the answer into one. Note also that the above formula was for ic(n + 1) so odd is even and even is odd. This gives (for n odd)

ic_{odd}(n) = \frac{1}{216} (9 2^{n}n^{2} + 15 2^{n}n − 16 (2^{n} − 1))

and for n even

ic_{even}(n) = \frac{1}{216} (9 2^{n}n^{2} + 15 2^{n}n − 16 (2^{n} + 1))

which only differ in the constant term and thus together give

ic(n) = \frac{2^{n−4}}{27} (9n^{2} − 3n − 22) − \frac{2}{27}(−1)^{n}

(the result in Theorem 5) which corresponds to the result obtained by algebraic methods by Heubach et al. [2].

4 Sum of inversion sizes

In this section we study the sum of inversions sizes over all compositions of n. For example, the composition 4232 has four inversions (\underline{42}32, \underline{4}2\underline{3}2, \underline{4}23\underline{2} and 42\underline{32}), with respective sizes 2 + 1 + 2 + 1 = 6.

Theorem 6. The sum of the sizes of all inversions across all compositions of n is

s(n) = \frac{1}{216} (9n^{2} · 2^{n} − 21n · 2^{n} + 8 · 2^{n} − 8(−1)^{n}) .  (13)

This corresponds to the sequence \underline{A102841} (shifted by three) in the OEIS under another description.

Proof. Let s(n) represent the total sum of inversions sizes in all compositions of n. We begin by creating a recursion for s(n) which is based on the usual construction, where in this case π is a composition of n which starts with a part of size k, for k fixed.

The sum of sizes of inversions in a composition of n starting with a k equals the sum of sizes of inversions in the corresponding composition of size n + 1 with a part of size one inserted at the beginning.

However, by adding a one to the first part of the composition (resulting in a composition of n + 1 which starts with a part of size k + 1) every part which is less than or equal to k contributes one more to the sum of all sizes of inversions.

Let d(n) be the number of parts of size less than or equal to the first part in the original composition of n, excluding the first part.

Then we have the following recursion:

s(n + 1) = 2s(n) + d(n).  (14)

To determine d(n), we construct a generating function f(x, u|k) for compositions starting with a k where x marks the size of the composition and u marks the number of parts in the composition of size 1, 2, …, k (excluding the first part) is

f(x, u|k) := \frac{x^{k}}{1 − (ux + ux^{2} + ⋯ + ux^{k−1} + ux^{k} + x^{k+1} + x^{k+2} + ⋯)}

= \frac{x^{k}}{1 − (u\frac{x−x^{k+1}}{1−x} + \frac{x^{k+1}}{1−x} )}.

Since we are interested in the number of parts less than or equal to k, we now differentiate with respect to u to get

\frac{∂}{∂u}f(x, u)|_{u=1} = \frac{x^{k}(\frac{x−x^{k+1}}{1−x} )}{(1 − (\frac{x−x^{k+1}}{1−x} + \frac{x^{k+1}}{1−x} ))^{2}}

= x^{k+1}(1 − x^{k})\frac{1 − x}{(1 − 2x)^{2}} .

Extracting coefficients, we get

[x^{n}]\frac{∂}{∂u}f(x, u)|_{u=1} = [x^{n−k}]\frac{x(1 − x)}{(1 − 2x)^{2}} − [x^{n−2k}]\frac{x(1 − x)}{(1 − 2x)^{2}}
= 2^{n−k−2}(n − k + 1) − 2^{n−2k−2}(n − 2k + 1).

Now we sum on k to n − 1 for the first term, giving 2^{n−2}(n − 1). For the second term, note that the upper limit of summation differs for odd and even n, so that the sum is \frac{1}{36}(−3n2^{n} + 5 · 2^{n} + 4(−1)^{n}). Hence we have

d(n) = \frac{n}{6}2^{n} − \frac{1}{9}2^{n} + \frac{1}{9}(−1)^{n}.

This can now be inserted into the recursion given in Equation 14, which yields

s(n + 1) = 2s(n) + \frac{n}{6}2^{n} − \frac{1}{9}2^{n} + \frac{1}{9}(−1)^{n}.  (15)

Solving this recursion (with s(1) = 0) gives the result of Theorem 6.

In order to prove Theorem 6, we made use of the statistic “the number of parts less than or equal to the first part”. It is interesting to note that this sequence is in the OEIS as \underline{A045883} under another description. Here we prove a bijection based on this observation.

Lemma 7. Each part of size less than or equal to the first part in a composition of n corresponds bijectively to a descent in a composition of n + 1.

Proof. The bijection is as per Figure 1 where the letters below the diagram indicate the positions of the shaded parts.

For example, the marked composition \underline{5}17\underline{5}432 of n = 27 would map to the marked composition 17\underline{65}432 of n + 1 = 28 (and back again). However, \underline{5}1754\underline{3}2 would map to 1754\underline{63}2 (and back again).

A s

1

B h ≤ h Composition of n A s

s − 1

B ≤ h Composition of n + 1 h + 1

Figure 1: Diagram illustrating bijection for Lemma 7.

5 Inversions of size d or more

Here we study the number of inversions of size d or more that occur in compositions of n.

Theorem 8. The total number of inversions of size d or more in compositions of n is

f(n, d) := \frac{1}{216} (2^{n−d} (9d^{2} − 3d(6n + 5) + 3n(3n + 5) − 16) + 16(−1)^{n−d}) .

Proof. Let D(n) be the total number of inversions of size greater than or equal to d in compositions of n.

Again we construct all compositions of n + 1 from compositions of n by (a) prepending a part of size one or (b) adding a one to the initial part of the composition.

Process (a) preserves each inversion and so does not change the total number of inversions. Process (b) adds a new d inversion for each part in a composition of n that is of size

k − (d − 1) where k is the size of the first part. To calculate the latter total we proceed as follows:

The generating function for compositions whose first part is of size k where u tracks the number of parts of size k − (d − 1) is

f(x, u|k) := \frac{x^{k}}{1 − (\frac{x}{1−x} − x^{k−(d−1)} + ux^{k−(d−1)})}.

Differentiating and setting u = 1 gives

\frac{∂}{∂u}f(x, u|k)|_{u=1} = \frac{x^{2k−d+1}}{(1 − \frac{x}{1−x})^{2}} ,

which we sum on k to get

∑_{k≥d} \frac{x^{2k−d+1}}{(1 − \frac{x}{1−x})^{2}} = \frac{(1 − x)x^{d+1}}{(1 + x)(1 − 2x)^{2}} .  (16)

Equation (16) is the generating function for new d inversions created by process (b).

Let r(n) := [x^{n}]\frac{(1−x)x^{d+1}}{(1+x)(1−2x)^{2}} . This is the number of new d inversions created by process (b).

Processes (a) and (b) together result in the recursion

D(n + 1) = 2D(n) + r(n)  (17)

Multiplying (17) by x^{n+1} and summing on n yields

∑_{n≥1} D(n + 1)x^{n+1} = 2 ∑_{n≥1} D(n)x^{n+1} + ∑_{n≥1} r(n)x^{n+1}

Now define T (x) := ∑_{n≥1} D(n)x^{n}. Therefore T (x) − D(1) = 2xT (x) + x\frac{(1−x)x^{d+1}}{(1+x)(1−2x)^{2}} . But

D(1) = 0 (compositions of 1 have no inversions). Hence T (x) = \frac{(1−x)x^{d+2}}{(1+x)(1−2x)^{3}} . Extracting the coefficient of x^{n} leads to the result stated in Theorem 8.

We note that the number of inversions of size d or more in compositions of n is the same as the number of inversions of size d + 1 or more in compositions of n + 1. This follows because f(n, d) − f(n + 1, d + 1) = 0 (where f(n, d) is given in Theorem 8). Consequently, the sequence in the OEIS given by \underline{A189052} is also relevant here, as it is the same sequence (shifted) as that for the total number of inversions.

As a related result, the next lemma shows (bijectively) that the number of inversions of size exactly d in compositions of n is equal to the number of inversions of size exactly d + 1 in compositions of n + 1.

Lemma 9. Each inversion of size d in a composition of n corresponds bijectively to an inversion of size d + 1 in a composition of n + 1.

Proof. The bijection is shown in Figure 2, where s and t indicate the positions of the shaded parts.

A B s t C d Composition of n A B s t C d + 1 Composition of n + 1

Figure 2: Illustration of bijection for Lemma 9.

6 Compositions with first part occurring an odd number of times

The proof of Theorem 1 suggests that it is of interest to study whether the multiplicity of the initial term in a composition is odd or even. By direct computation we find that the number of compositions with the multiplicity of the first part odd, grows for n ≥ 1 as

1, 1, 4, 4, 12, 18, 44, 72, 158, 288, 604, 1146, ….

This sequence is \underline{A331606} in the OEIS.

Subtracting the n-th term from 2^{n−1} gives the corresponding count for multiplicity of the first part even, which is sequence \underline{A331609} in the OEIS.

We have found two ways to construct a generating function for this sequence,

f(x) = x + x^{2} + 4x^{3} + 4x^{4} + 12x^{5} + · · · .

The first depends on an auxiliary function A(i, x) for compositions consisting of a first part i followed by any number of parts (including zero) of any size except i:

A(i, x) = x^{i} ∑_{r≥0} (\frac{x}{1 − x} − x^{i})^{r} .

To get all odd multiplicities for this first part we add an even number of A(i, x) summands, obtaining

\frac{A(i, x)}{1 − A^{2}(i, x)}.

The generating function comes by summing on i:

f(x) = ∑_{i≥1} \frac{A(i, x)}{1 − A^{2}(i, x)}.

Suppressing the auxiliary function A, we have

f(x) = ∑_{i=1}^{∞} \frac{(x − 1)x^{i}(1 − 2x + x^{i} − x^{i+1})}{(2x − 1)(1 − 2x + 2x^{i} − 2x^{i+1})}.

Alternatively, we can introduce an extra variable u to track the multiplicity of the first part: g(x, u) is the generating function in which the x^{n}u^{m} term has coefficient giving the number of compositions of n with first term of multiplicity m.

The generating function for any subsequent part (following the first part of size i) is

\frac{x}{1 − x} + (u − 1)x^{i},

so

g(x, u) := u ∑_{i=1}^{∞} \frac{x^{i}}{1 − (\frac{x}{1−x} + (u − 1)x^{i})}.

Then the number of compositions whose first part has odd multiplicity is generated by

g(x) = \frac{1}{2}(g(x, 1) − g(x, −1))

= \frac{x}{2(1 − 2x)} + ∑_{i=1}^{∞} \frac{(1 − x)x^{i}}{2(1 − 2x + 2x^{i} − 2x^{i+1})}.

We can verify that f(x) and g(x) represent the same generating function by considering the difference of the infinite series:

∑_{i=1}^{∞} \frac{(x − 1)x^{i} (x^{i+1} − x^{i} + 2x − 1)}{(1 − 2x) (−2x^{i+1} + 2x^{i} − 2x + 1)} − ∑_{i=1}^{∞} \frac{(1 − x)x^{i}}{2 (−2x^{i+1} + 2x^{i} − 2x + 1)}.

By combining corresponding summands, we have

∑_{i=1}^{∞} \frac{2(x − 1)x^{i}(−1 + 2x − x^{i} + x^{1+i}) + (2x − 1)(1 − x)x^{i}}{2(1 − 2x)(1 − 2x + 2x^{i} − 2x^{1+i})} .

When we simplify the numerator there is a common factor that cancels, and a geometric series is left which sums to

\frac{x}{2(1 − 2x)}

as required.

Theorem 10. The average proportion E_{n} of compositions of n in which the initial part has odd multiplicity satisfies

E_{n} = \frac{1}{2} + \frac{1}{(2 log 2)n} + \frac{1}{(2 log 2)n}δ (log_{2} n) + o(1/n),

where δ(x) is a periodic function of period 1 and mean 0 and small amplitude, which is given by the Fourier series

δ(x) = ∑_{k≠0} Γ (1 + χ_{k}) e^{2kπix}.

The complex numbers χ_{k} are given by χ_{k} = 2kπi/ log 2.

Proof. We use the second expression

g(x) = \frac{x}{2(1 − 2x)} + ∑_{i=1}^{∞} \frac{(1 − x)x^{i}}{2(1 − 2x + 2x^{i} − 2x^{i+1})}

for the total number of compositions in which the initial part has odd multiplicity. Hence the average proportion E_{n} of compositions of n in which the initial part has odd multiplicity satisfies

E_{n} = \frac{1}{2^{n−1}} [x^{n}]g(x) = \frac{1}{2} + \frac{1}{2^{n−1}} [x^{n}] ∑_{i=1}^{∞} \frac{(1 − x)x^{i}}{2(1 − 2x + 2x^{i} − 2x^{i+1})}.

Let ρ_{k} be the smallest positive root of the denominator polynomial 1 − 2x + 2x^{k} − 2x^{k+1} that lies between 1/2 and 1. An application of the principle of the argument or Rouche’s Theorem shows such a root to exist with all other roots of modulus greater than 3/5. By dominant pole analysis,

q_{n,k} := [x^{n}]\frac{(1 − x)x^{k}}{2(1 − 2x + 2x^{k} − 2x^{k+1})} = c_{k}ρ_{k}^{−n} + O ((\frac{5}{3})^{n})  (18)

with

c_{k} = \frac{(1 − ρ_{k})ρ_{k}^{k}}{2ρ_{k}(2 − kρ_{k}^{k−1} + 2(k + 1)ρ_{k}^{k})}

for large n but fixed k. The denominator polynomial 1 − 2x + 2x^{k} − 2x^{k+1} behaves like a perturbation of 1 − 2x near x = 1/2, so one expects ρ_{k} to be approximated by \frac{1}{2} as k → ∞. By “bootstrapping” we find that

ρ_{k} = \frac{1}{2} + 2^{−k−1} + O(k2^{−2k})  (19)

and hence c_{k} = \frac{1}{2^{k+2}} + O(k2^{−2k}). The use of this approximation can be justified for a wide range of values of k and n. For some examples, see the work of Gourdon and Prodinger [1] or Knuth [5].

To obtain the estimates for q_{n,k}, we look at three different ranges for the values of 2^{−k}. The dominant range is those k for which n^{−3} ≤ 2^{−k} ≤ \frac{log n}{n}. For such k we find

ρ_{k}^{−n} = (\frac{1}{2}(1 + 2^{−k} + O(k2^{−2k})))^{−n} = 2^{n} exp (−\frac{n}{2^{k}} ) (1 + O (\frac{kn}{2^{2k}} ))

whence

q_{n,k} = 2^{n−k−2} exp (−\frac{n}{2^{k}} ) (1 + O (\frac{k}{2^{k}} ) + O (\frac{kn}{2^{2k}} )) .

Then using the given upper and lower bounds on k,

q_{n,k} = 2^{n−k−2} (exp (−\frac{n}{2^{k}} ) + O (\frac{log^{3} n}{n})) .  (20)

Turning next to smaller values of k ≥ 2, that is, k such that 2^{−k} > \frac{log n}{n}, we find that now the coefficients q_{n,k} are relatively small, since for such k, q_{n,k} = O(\frac{2^{n−k}}{n}) as n → ∞. Finally we must consider the larger values of k ≤ n that is, k for which n^{−3} > 2^{−k}, or equivalently, k ≥ 3 log_{2} n. In this range we find that

q_{n,k} = 2^{n−k−2} (exp (−\frac{n}{2^{k}} ) + O (\frac{1}{n^{2}} )) .  (21)

Then combining the estimates for q_{n,k} over the range 2 ≤ k ≤ n above,

E_{n} − \frac{1}{2} = ∑_{k=2}^{n} \frac{q_{n,k}}{2^{n−1}}

∼ ∑_{k=2}^{n} 2^{−k−1} exp (−\frac{n}{2^{k}} )

∼ ∑_{k=0}^{∞} 2^{−k−1} exp (−\frac{n}{2^{k}} ) ,

as the additional tail sum ∑_{k>n} 2^{−k−1} exp (−\frac{n}{2^{k}} ) is exponentially small. It remains to estimate

the harmonic sum

h(n) := ∑_{k≥0} 2^{−k−1} exp (−\frac{n}{2^{k}} ) ,

as n → ∞. For this we use Mellin transforms and find (see [6, Appendix B.7, Equation (48)] ) that the Mellin transform h^{∗}(s) of h(x) is

h^{∗}(s) = \frac{1}{2}Γ[s]\frac{1}{1 − 2^{s−1}} for 0 < Re(s) < 1.

By the Mellin inversion formula, we then obtain an asymptotic estimate for h(n) from the negative residues of \frac{1}{2}Γ[s]\frac{1}{1−2^{s−1}} x^{−s} at the simple poles s = 1 and s = χ_{k} = 2kπi/ log 2, for integers k ≠ 0. This gives

h(n) = \frac{1}{(2 log 2)n} + \frac{1}{(2 log 2)n} ∑_{k≠0} Γ (1 + χ_{k}) n^{−χ_{k}} + o(1/n).  (22)

The asymptotic estimate for E_{n} follows.

Definition 11. Asymptotically we find that 1/2 of compositions of n have multiplicity of first part odd, but the fluctuations in the term of order n^{−1} illustrate the complexity of the problem.

7 Acknowledgments

This material is based upon work supported by the National Research Foundation under grant numbers 89147 (Archibald), BLEC 018 (Blecher) and 81021 (Knopfmacher). The last author thanks the John Knopfmacher Centre for Applicable Analysis and Number Theory at the University of the Witwatersrand.

References

[1] X. Gourdon and H. Prodinger, A generating function approach to random subgraphs of the n-cycle, Discrete Math. 169 (1997) 227–232.

[2] S. Heubach, A. Knopfmacher, M. E. Mays, and A. Munagi, Inversions in compositions of integers, Quaest. Math. 34 (2011) 1–16.

[3] S. Heubach and T. Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

[4] A. Knopfmacher, M. E. Mays, and S. Wagner, Compositions with a fixed number of inversions, Aequationes Math. 93, (2019) 601–617.

[5] D. E. Knuth, The average time for carry propagation, Indag. Math. 40 (1978) 238–242.

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

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2019.

[8] A. Tripathi, Six ways to count the number of integer compositions, Crux Mathematicorum, 39 (2) (2013) 84–88.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 11P81. Keywords: composition, partition, inversion, parity.

(Concerned with sequences \underline{A005418}, \underline{A006516}, \underline{A007582}, \underline{A020522}, \underline{A032085}, \underline{A045623}, \underline{A045883}, \underline{A058884}, \underline{A063376}, \underline{A102841}, \underline{A189052}, \underline{A331606}, and \underline{A331609}.)

Received May 10 2019; revised versions received January 22 2020; March 2 2020. Published in Journal of Integer Sequences, March 18 2020.

Return to Journal of Integer Sequences home page.