\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\DeclareMathOperator{\ic}{ic}
\DeclareMathOperator{\Od}{Od}
\DeclareMathOperator{\Ev}{Ev}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Inversions and Parity in \\
\vskip .1in
Compositions of Integers
}
\vskip 1cm
\large
M. Archibald, A. Blecher, and A. Knopfmacher \\
The John Knopfmacher Centre for
Applicable Analysis and Number Theory\\
University of the Witwatersrand\\
Johannesburg \\
South Africa \\
\href{mailto:Margaret.Archibald@wits.ac.za}{\tt Margaret.Archibald@wits.ac.za} \\
\href{mailto:Aubrey.Blecher@wits.ac.za}{\tt Aubrey.Blecher@wits.ac.za} \\
\href{mailto:Arnold.Knopfmacher@wits.ac.za}{\tt Arnold.Knopfmacher@wits.ac.za} \\
\ \\
M. E. Mays \\
West Virginia University\\
Morgantown, WV 26506-6310 \\
USA \\
\href{mailto:Michael.Mays@mail.wvu.edu}{\tt Michael.Mays@mail.wvu.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
A {\it composition\/} of a positive integer $n$ is a representation of $n$
as an ordered sum of positive integers $a_1+a_2+\dots+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 {\it 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.
\end{abstract}
\section{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+\dots+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.\ \cite{HKMM} to account for patterns inherent in Tables~\ref{icr} and \ref{evens} for the statistic
$$\ic_r(n) = \mbox{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.\ \cite{HKMM} and described in \seqnum{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.\ \cite{KMW} also study $\ic_1(n)$ to $\ic_5(n)$.
This paper is divided into five sections. In Section~\ref{sec:freq}, 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~\ref{sec:totinv}). By considering the size of each inversion in Section~\ref{sec:invsizes}, we sum the size of all inversions across compositions of $n$, and then sum inversions of size $d$ or more in Section~\ref{sec:dormore}. Finally, in Section~\ref{sec:oddtimes}, we return to the idea of parity and study compositions with the first part occurring with odd multiplicity.
\section{Relative frequency of even and odd compositions}\label{sec:freq}
A table of values of $\ic_r(n)$ is provided in Table~\ref{icr}. 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.\ \cite{KMW} analyse table entries column by column to derive
generating function identities and consider asymptotic results.
\begin{table}[ht]
\[
\begin{array}{l|ccccccccccccccc}
n\backslash r &
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &\dots &\Ev & \Od\\ \hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\dots & 1 & 0\\
2 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\dots & 2 & 0\\
3 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\dots & 3 & 1\\
4 & 5 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\dots & 6 & 2\\
5 & 7 & 5 & 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &\dots & 10 & 6\\
6 & 11 & 8 & 7 & 4 & 2 & 0 & 0 & 0 & 0 & 0 &\dots & 20 & 12\\
7 & 15 & 15 & 14 & 10 & 6 & 3 & 1 & 0 & 0 & 0 &\dots & 36 & 28\\
8 & 22 & 23 & 26 & 21 & 17 & 10 & 6 & 2 & 1 & 0 &\dots & 72 & 56\\
9 & 30 & 37 & 44 & 42 & 36 & 27 & 19 & 11 & 6 & 3 &\dots & 136 & 120\\
10 & 42 & 55 & 73 & 74 & 73 & 60 & 50 & 34 & 24 & 13 &\dots & 272 & 240\\
11 & 56 & 83 & 115 & 128 & 133 & 123 & 109 & 87 & 68 & 48 &\dots & 528 & 496\\
12 & 77 & 118 & 177 & 209 & 235 & 230 & 223 & 192 & 166 & 129 &\dots & 1056 & 992
\end{array}
\]
\caption{Compositions with $r$ inversions, $\ic_r(n)$} \label{icr}
\end{table}
Values of $|\Ev(n)|$ (resp., $|\Od(n)|$) can be recovered by summing the entries in row $n$ of Table \ref{icr} for the columns with even (odd) indices. We see the first few values for the compositions in $\Ev(n)$ in Table~\ref{evens}.
\begin{table}[ht]
\[
\begin{array}{c|cc}
n & |\Ev(n)| & |\Ev(n)|/|C(n)|\\
\hline
1 & 1 & \text{1.}\\
2 & 2 & \text{1.}\\
3 & 3 & \text{0.75}\\
4 & 6 & \text{0.75}\\
5 & 10 & \text{0.625}\\
6 & 20 & \text{0.625}\\
7 & 36 & \text{0.5625}\\
8 & 72 & \text{0.5625}\\
9 & 136 & \text{0.53125}\\
10 & 272 & \text{0.53125}\\
11 & 528 & \text{0.515625}\\
12 & 1056 & \text{0.515625}\\
13 & 2080 & \text{0.5078125}\\
14 & 4160 & \text{0.5078125}\\
15 & 8256 & \text{0.50390625}
\end{array}
\]
\caption{Compositions of even parity}\label{evens}
\end{table}
The sequence of values $\Ev(2n-1): 1, 3, 10, 36 \dots$ appears
in the {\em On-Line Encyclopedia of Integer Sequences} (OEIS) as
\seqnum{A007582}. There are several interesting combinatorial contexts
mentioned there, but none explicitly involves compositions. We also
find $\Ev(n)$ at \seqnum{A005418}, $\Ev(2n)$ at \seqnum{A063376},
and corresponding sequences of odd compositions at \seqnum{A032085},
\seqnum{A006516}, and \seqnum{A020522}.
First we account for the entries in Table \ref{evens}.
\begin{theorem} \label{EvOd} Let $n$ be a positive integer. Then
\begin{itemize}
\item[(1)] $|\Ev(2n)| =2|\Ev(2n-1)|$;
\item[(2)] $|\Ev(2n+1)| = 2 |\Ev(2n)| - 2^{n-1}$;
\item[(3)] $|\Od(2n)| =2|\Od(2n-1)|$;
\item[(4)] $|\Od(2n+1)| = 2 |\Od(2n)| + 2^{n-1}$.
\end{itemize}
\end{theorem}
\begin{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:
\begin{enumerate}
\item[(a)] Prepend a 1, so, e.g., $3+3+1 \rightarrow 1+3+3+1$
\item[(b)] Augment the first summand by 1, so, e.g., $3+3+1 \rightarrow 4+3+1$
\end{enumerate}
This is a familiar construction. See, for example,
work by Tripathi \cite{Tri}, 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+\dots+a_k \in C(m)$ such that $(a_1+1)+a_2+\dots+a_k \in 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, \dots, 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+\dots+a_k$. Look for the first pair of summands $(a_2,a_3),(a_4,a_5),\dots$ 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 $\rightarrow$ odd and the odd $\rightarrow$ 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),\dots$ 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+\dots+a_l+a_l+a_1.$$
There are as many ways this can happen as there are compositions $a_1+a_2+\dots+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}$.\end{proof}
We solve the recurrences from Theorem \ref{EvOd}, to obtain
\begin{corollary} Formulas for the parity counting composition functions for $n \ge 1$ are as follows:
\begin{itemize}
\item[(1)] $|\Ev(2n)| =2^{2n-2}+2^{n-1}$;
\item[(2)] $|\Ev(2n-1)| = 2^{2n-3} +2^{n-2}$;
\item[(3)] $|\Od(2n)| =2^{2n-2}-2^{n-1}$;
\item[(4)] $|\Od(2n-1)| = 2^{2n-3}-2^{n-2}$.
\end{itemize}
\end{corollary}
We use the formulas above to observe that, asymptotically,
the number of even and odd compositions match.
\begin{corollary}
$\lim\limits_{n \rightarrow \infty} \dfrac{|\Ev(n)|}{|C(n)|}=\lim\limits_{n \rightarrow \infty} \dfrac{|\Od(n)|}{|C(n)|}=\frac12$.
\end{corollary}
\section{Total number of inversions}\label{sec:totinv}
Let $\ic(n)$ denote the total number of inversions in all compositions of $n$. Then
\[
\ic(n) = \sum_{r=1}^n \ic_r(n)
\]
(see Table~\ref{icr}). The sequence generated by this formula is in the OEIS as \seqnum{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 \cite{HM} or Sedgewick and Flajolet \cite{SF}.
\begin{lemma}\label{ones}
The total number of parts of size one in all compositions of $n$ is
\begin{equation}\label{uofn}
u(n):=\begin{cases}(n+2)2^{n-3}, &\textrm{ for } n \ge 2;\\
1, &\textrm{ for } n=1.
\end{cases}
\end{equation}
\end{lemma}
This appears in the OEIS as \seqnum{A045623}.
\begin{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 \ge 2$) as follows.
\begin{equation}\label{rec}
u(n+1) = \underbrace{u(n) + 2^{n-1}}_{\textrm{append a one}} + \underbrace{u(n)-2^{n-2}}_{\textrm{add one to last part}},
\end{equation}
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~(\ref{rec}) above, we get
\[
u(n+1)=2u(n)+2^{n-2},
\]
and solving it gives the result in Lemma~\ref{ones}.
\end{proof}
\begin{theorem}\label{totalinvs}
The total number of inversions in all compositions of $n$ is
\begin{equation}
\ic(n) = \frac{2^{n-4}}{27}(9n^2-3n-22)-\frac{2}{27}(-1)^n.
\end{equation}
\end{theorem}
Heubach et al.\ \cite{HKMM} derived this expression via generating functions. We are now able to give a more combinatorial proof.
\begin{proof} We use a similar method to that used in Theorem~\ref{EvOd}, 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 $\pi$ be a composition of $n$ and denote a composition which ends in a part of size $a$ as $\pi | a$. We construct $\pi'$ (a composition of $n+1$) from $\pi$ as follows:
\begin{enumerate}
\item[(a)] append a part of size one to the end of $\pi$
\item[(b)] add one to the last part of $\pi$
\end{enumerate}
In the first procedure the number of additional inversions is the total number of parts in $\pi$ minus the total number of parts of size one in $\pi$.
In the second procedure the number of inversions of $\pi | a$ (for a fixed $a$) decreases by the number of parts in $\pi$ of size $a+1$ which is the same as the number of parts of size $a+1$ in $\pi'$ (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 \le 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:
\begin{equation}\label{recic1}
\ic(n+1)=\underbrace{\ic(n)+(n+1) 2^{n-2}-u(n)}_{\textrm{Procedure 1}} + \underbrace{\ic(n)-\sum_{a=1}^{\lfloor \frac n2 \rfloor} u(n-2a)}_{\textrm{Procedure 2}}
\end{equation}
which can be simplified to
\begin{equation}\label{recic2}
\ic(n+1)=2\ic(n)+(n+1) 2^{n-2}-\sum_{a=0}^{\lfloor \frac n2 \rfloor} u(n-2a).
\end{equation}
Because the formula for $u(n)$ in Equation~(\ref{uofn}) only holds for $n \ge 2$, we exclude the upper limit of the sum on $a$ to evaluate:
\begin{align*}
\sum_{a=0}^{\lfloor \frac n2 \rfloor-1} u(n-2a)
&=(n+2)2^{n-3} \sum_{a=0}^{\lfloor \frac n2 \rfloor-1} 2^{-2a}-2^{n-2} \sum_{a=0}^{\lfloor \frac n2 \rfloor-1} a 2^{-2a}\\
&=\frac 19 2^{n - 1 -
2 \lfloor \frac n2 \rfloor} \Big((4^{\lfloor \frac n2 \rfloor}-1) (4 + 3 n) + 6 \Big\lfloor \frac n2 \Big\rfloor \Big)\\
&=\frac {2^n}{18} \Big(4 + 3 n - 4 \cdot 2^{ -
2 \lfloor \frac n2 \rfloor} - 3 n 2^{ -
2 \lfloor \frac n2 \rfloor} + 6 \Big\lfloor \frac n2 \Big\rfloor 2^{ -
2 \lfloor \frac n2 \rfloor}\Big),
\end{align*}
and note that the last term in the sum on $a$ is
\begin{align*}
u\left(n-2 \Big\lfloor \frac n2 \Big\rfloor\right) &= \begin{cases} u(n-2 \frac n2), \textrm{ if $n$ is even};\\ u(n-2 \frac {n-1}2), \textrm{ if $n$ is odd}; \end{cases}\\
&= \begin{cases} u(0), \textrm{ if $n$ is even};\\ u(1,) \textrm{ if $n$ is odd}; \end{cases}\\
&= \begin{cases} 0, \textrm{ if $n$ is even};\\ 1, \textrm{ if $n$ is odd}. \end{cases}
\end{align*}
We make use of the Kronecker delta function to express this, and write
\[
\delta_n := \begin{cases} 0, \textrm{ if $n$ is even};\\ 1, \textrm{ if $n$ is odd}. \end{cases}
\]
Hence the recursion for the function $\ic(n)$ becomes
\begin{align}\label{recic3}
\ic(n+1)=&2\ic(n)+(n+1) 2^{n-2}\notag \\
&-\frac {2^n}{18} \Big(4 + 3 n - 4 \cdot 2^{ -
2 \lfloor \frac n2 \rfloor} - 3 n 2^{ -
2 \lfloor \frac n2 \rfloor} + 6 \Big\lfloor \frac n2 \Big\rfloor 2^{ -
2 \lfloor \frac n2 \rfloor}\Big)-\delta_n
\end{align}
which can be solved (noting that $\ic(2)=\ic(1)=0$) to get
\begin{align*}
\ic(n+1) =& 2^{n-2} \sum_{i=0}^{n-2}(i+3)- \sum_{i=0}^{n-2} \delta_{n-i} 2^i\\
&-\frac {2^n}{18} \sum_{i=2}^{n}\Big(4 + 3 i - 4 \cdot 2^{ -
2 \lfloor \frac i2 \rfloor} - 3 i 2^{ -
2 \lfloor \frac i2 \rfloor} + 6 \Big\lfloor \frac i2 \Big\rfloor 2^{ -
2 \lfloor \frac i2 \rfloor}\Big).
\end{align*}
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:
\begin{align}\label{floor}
\sum_{i=2}^{n}2^{ - 2 \lfloor \frac i2 \rfloor} &= \begin{cases} 2 \sum_{i=1}^{\frac {n-1}2} 2^{-2i}, & \textrm{ for $n$ odd}; \\ 2 \sum_{i=1}^{\frac {n-2}2} 2^{-2i} + 2^{-n}, &\textrm{for $n$ even}; \end{cases}\\
&= \begin{cases} \frac 23 - \frac 4{3 \cdot 2^n}, & \textrm{ for $n$ odd}; \\ \frac 23 - \frac{5}{3 \cdot 2^n}, &\textrm{for $n$ even}; \end{cases}
\end{align}
and similarly:
\begin{equation}\label{ifloor}
\sum_{i=2}^{n} i 2^{ -
2 \lfloor \frac i2 \rfloor} = \begin{cases} \frac 1{9 \cdot 2^n} (-26 + 19 \cdot 2^n - 12 n), & \textrm{for $n$ odd};\\ \frac 1{9 \cdot 2^n} (-28 + 19 \cdot 2^n - 15 n), &\textrm{for $n$ even}; \end{cases}
\end{equation}
and
\begin{equation}\label{floorfloor}
\sum_{i=2}^{n} \Big\lfloor \frac i2 \Big\rfloor 2^{ -
2 \lfloor \frac i2 \rfloor} = \begin{cases} \frac 2{9 2^n} (-5 + 2^{2 + n} - 3 n), & \textrm{for $n$ odd};\\ \frac 1{9 2^{n+1}} (-16 + 2^{4 + n} - 15 n), &\textrm{for $n$ even}. \end{cases}
\end{equation}
Again a parity split is useful for
\begin{align}\label{deltasum}
\sum_{i=0}^{n-2} \delta_{n-i} 2^i &= \begin{cases} \sum_{i=0}^{\frac{n-3}2} 2^{2i}, & \textrm{for $n$ odd}; \\ \sum_{i=0}^{\frac{n-4}2} 2^{2i+1}, & \textrm{for $n$ even}; \end{cases}\\
&= \begin{cases} \frac 16 (2^n-2), & \textrm{for $n$ odd}; \\ \frac 16 (2^n-4), & \textrm{for $n$ even}. \end{cases}
\end{align}
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_{\rm odd}(n)=\frac{1}{216} \left(9\ 2^n n^2+15\
2^n n-16
\left(2^n-1\right)\right)
\]
and for $n$ even
\[
\ic_{\rm even}(n)=\frac{1}{216} \left(9\ 2^n n^2+15\
2^n n-16
\left(2^n+1\right)\right)
\]
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~\ref{totalinvs}) which corresponds to the result obtained by algebraic methods by Heubach et al.\ \cite{HKMM}. \end{proof}
\section{Sum of inversion sizes}\label{sec:invsizes}
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$.
\begin{theorem}\label{sumofdrops}
The sum of the sizes of all inversions across all compositions of $n$ is
\begin{equation}\label{eq:sod}
s(n)=\frac{1}{216}\left(9 n^2 \cdot 2^n-21 n \cdot 2^n+8 \cdot 2^n-8(-1)^n\right).
\end{equation}
\end{theorem}
This corresponds to the sequence \seqnum{A102841} (shifted by three) in the OEIS under another description.
\begin{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 $\pi$ 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:
\begin{equation}\label{eq:rec}
s(n+1)=2s(n)+d(n).
\end{equation}
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,\dots,k$ (excluding the first part) is
\begin{align*}
f(x,u|k)&:=\frac{x^k}{1-(ux+ux^2+\cdots+u x^{k-1}+u x^k +x^{k+1}+x^{k+2}+\cdots)}\\
&=\frac{x^k}{1-\Big(u\frac{x-x^{k+1}}{1-x}+\frac{x^{k+1}}{1-x}\Big)}.
\end{align*}
Since we are interested in the number of parts less than or equal to $k$, we now differentiate with respect to $u$ to get
\begin{align*}
\frac{\partial}{\partial u}f(x,u)\bigg|_{u=1}
&=\frac{x^k \Big(\frac{x-x^{k+1}}{1-x}\Big)}{\bigg(1-\Big(\frac{x-x^{k+1}}{1-x}+\frac{x^{k+1}}{1-x}\Big)\bigg)^2}\\
&=x^{k+1} (1-x^k)\frac{1-x}{(1-2x)^2}.
\end{align*}
Extracting coefficients, we get
\begin{align*}
[x^n]\frac{\partial}{\partial u}f(x,u)\bigg|_{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).
\end{align*}
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\cdot2^n +4(-1)^n)$. Hence we have
\[
d(n) = \frac{n}{6} 2^n - \frac19 2^n + \frac 19 (-1)^n.
\]
This can now be inserted into the recursion given in Equation~\ref{eq:rec}, which yields
\begin{equation}
s(n+1)=2s(n)+\frac{n}{6} 2^n - \frac19 2^n + \frac 19 (-1)^n.
\end{equation}
Solving this recursion (with $s(1)=0$) gives the result of Theorem~\ref{sumofdrops}. \end{proof}
In order to prove Theorem~\ref{sumofdrops}, 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 \seqnum{A045883} under another description. Here we prove a bijection based on this observation.
\begin{lemma}\label{Bijection2}
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$.
\end{lemma}
\begin{proof}
The bijection is as per Figure~\ref{fig:bij2} 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). \end{proof}
\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=0.45]
\fill[gray!60!white](0,0)--(0,7)--(1.5,7)--(1.5,0)(7,0)--(7,6)--(8.5,6)--(8.5,0);
\draw [thick] (0,0) -- (12,0) (0,0)--(0,7)--(1.5,7)--(1.5,0) (7,0)--(7,6)--(8.5,6)--(8.5,0);
\draw [thick] (1.5,7) .. controls (3,12) and (5,2) .. (7,6);
\draw [thick] (8.5,6) .. controls (9,7) and (11,10) .. (12,0);
\draw (4,4) node[below]{$A$};
\draw (7.75,-0.1) node[below]{$s$};
\draw (0.75,0) node[below]{\begin{small}$1$\end{small}};
\draw (9.8,4) node[below]{$B$};
\draw (0.75,4) node[below]{$h$};
\draw (7.75,4) node[below]{$\le h$};
\draw (6,-1) node[below] {Composition of $n$};
\draw[<->](13,3)--(15,3);
\fill[gray!60!white](21.5,0)--(21.5,8)--(23,8)--(23,0)(23,0)--(23,6)--(24.5,6)--(24.5,0);
\draw [thick] (16,0) -- (28,0)(16,0)--(16,7) (21.5,0)--(21.5,8)--(23,8)--(23,0) (23,0)--(23,6)--(24.5,6)--(24.5,0);
\draw [thick] (16,7) .. controls (18,12) and (20,2) .. (21.5,6);
\draw [thick] (24.5,6) .. controls (25,7) and (27,10) .. (28,0);
\draw (18.5,4) node[below]{$A$};
\draw (23.75,-0.1) node[below]{$s$};
\draw (22.25,0) node[below]{\begin{small}$s-1$\end{small}};
\draw (25.8,4) node[below]{$B$};
\draw (23.75,4) node[below]{$\le h$};
\draw (22,-1) node[below] {Composition of $n+1$};
\draw (22.25,5) node[below]{$h$};
\draw (22.25,4) node[below]{$+$};
\draw (22.25,3) node[below]{$1$};
\end{tikzpicture}\caption{Diagram illustrating bijection for Lemma~\ref{Bijection2}.}\label{fig:bij2}
\end{center}
\end{figure}
\section{Inversions of size $d$ or more}\label{sec:dormore}
Here we study the number of inversions of size $d$ or more that occur in compositions of $n$.
\begin{theorem}\label{dormore}
The total number of inversions of size $d$ or more in compositions of $n$ is
\[f(n,d):=\frac{1}{216} \left(2^{n-d} \left(9 d^2-3 d (6 n+5)+3 n (3 n+5)-16\right)+16
(-1)^{n-d}\right).\]
\end{theorem}
\begin{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-\left(\frac{x}{1-x}-x^{k-(d-1)}+u x^{k-(d-1)}\right)}.
\]
Differentiating and setting $u=1$ gives
\[
\frac{\partial}{\partial u}f(x,u|k)\bigg|_{u=1}=\frac{x^{2 k-d+1}}{\left(1-\frac{x}{1-x}\right)^2},
\]
which we sum on $k$ to get
\begin{equation}\label{eq:d-1}
\sum_{k \ge d}\frac{x^{2 k-d+1}}{\left(1-\frac{x}{1-x}\right)^2}=\frac{(1-x) x^{d+1}}{(1+x) (1-2 x)^2}.
\end{equation}
Equation (\ref{eq:d-1}) 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-2 x)^2}$. This is the number of new $d$ inversions created by process (b).
Processes (a) and (b) together result in the recursion
\begin{equation}\label{eq:rec1}
D(n+1)=2D(n)+r(n)
\end{equation}
Multiplying (\ref{eq:rec1}) by $x^{n+1}$ and summing on $n$ yields
\begin{equation*}
\sum_{n\ge1}D(n+1)x^{n+1}=2\sum_{n\ge1}D(n)x^{n+1}+\sum_{n\ge1}r(n)x^{n+1}
\end{equation*}
Now define $T(x):=\sum\limits_{n\ge1}D(n)x^n$.
Therefore $T(x)-D(1)=2xT(x)+x\frac{(1-x) x^{d+1}}{(1+x) (1-2 x)^2}$.
But $D(1)=0$ (compositions of $1$ have no inversions).
Hence $T(x)=\frac{(1-x) x^{d+2}}{(1+x) (1-2 x)^3}$.
Extracting the coefficient of $x^n$ leads to the result stated in Theorem~\ref{dormore}. \end{proof}
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~\ref{dormore}). Consequently, the sequence in the OEIS given by \seqnum{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$.
\begin{lemma}\label{Bijection3}
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$.
\end{lemma}
\begin{proof}
The bijection is shown in Figure~\ref{fig:bij}, where $s$ and $t$ indicate the positions of the shaded parts. \end{proof}
\begin{figure}[ht]
\begin{center}
\begin{tikzpicture}[scale=0.45]
\fill[gray!60!white](3,0)--(3,8)--(4,8)--(4,0)(7,0)--(7,6)--(8,6)--(8,0);
\draw [thick] (0,0) -- (12,0) (3,0)--(3,8)--(4,8) (4,8)--(4,0)(7,0)--(7,6)--(8,6)--(8,0);
\draw [thick,dotted] (4,6) -- (7,6);
\draw [thick] (0,0) .. controls (1,12) and (2,4) .. (3,6);
\draw [thick] (4,8) .. controls (4,12) and (6,10) .. (7,6);
\draw [thick] (8,6) .. controls (9,3) and (10,8) .. (12,0);
\draw (1.5,2) node[below]{$A$};
\draw (5.5,2) node[below]{$B$};
\draw (3.5,0) node[below]{$s$};
\draw (7.5,0) node[below]{$t$};
\draw (9.8,2) node[below]{$C$};
\draw[<->](4.3,8)--(4.3,6);
\draw (4.3,7) node[right]{$d$};
\draw (6,-1) node[below] {Composition of $n$};
\draw[<->](13,3)--(15,3);
\fill[gray!60!white](19,0)--(19,9)--(20,9)--(20,0)(23,0)--(23,6)--(24,6)--(24,0);
\draw [thick] (16,0) -- (28,0) (19,0)--(19,9)--(20,9)(20,9)--(20,0)(23,0)--(23,6)--(24,6)--(24,0);
\draw [thick,dotted] (20,6) -- (23,6);
\draw [thick] (16,0) .. controls (17,12) and (18,4) .. (19,6);
\draw [thick] (20,8) .. controls (20,12) and (22,10) .. (23,6);
\draw [thick] (24,6) .. controls (25,3) and (26,8) .. (28,0);
\draw (17.5,2) node[below]{$A$};
\draw (21.5,2) node[below]{$B$};
\draw (19.5,0) node[below]{$s$};
\draw (23.5,0) node[below]{$t$};
\draw (25.8,2) node[below]{$C$};
\draw[<->](20.3,9)--(20.3,6);
\draw (20.3,7) node[right]{$d+1$};
\draw (22,-1) node[below] {Composition of $n+1$};
\end{tikzpicture}\caption{Illustration of bijection for Lemma~\ref{Bijection3}.}\label{fig:bij}
\end{center}
\end{figure}
\section{Compositions with first part occurring an odd number of times}\label{sec:oddtimes}
The proof of Theorem~\ref{EvOd} 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 \ge 1$ as
$$1,1,4,4,12,18,44,72,158,288,604,1146,\dots \,.$$
This sequence is \seqnum{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 \seqnum{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+\cdots\, .\]
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 \sum_{r\ge0}\left(\frac{x}{1-x}-x^i\right)^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)=\sum_{i \ge 1}\frac{A(i,x)}{1-A^2(i,x)}.\label{arch1}\]
Suppressing the auxiliary function $A$, we have
\[f(x)=\sum_{i=1}^\infty\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\sum_{i=1}^\infty \frac{x^i}{1-\Big(\frac{x}{1-x}+(u-1)x^i\Big)}.\label{knopf1}\]
Then the number of compositions whose first part has odd multiplicity is generated by
\begin{align*}
g(x)&=\frac{1}{2}(g(x,1)-g(x,-1))\\
&=\frac{x}{2(1-2x)}+\sum_{i=1}^\infty\frac{(1-x)x^i}{2(1-2x+2x^i-2x^{i+1})}.\end{align*}
We can verify that $f(x)$ and $g(x)$ represent the same generating function by considering the difference of the infinite series:
\[
\sum _{i=1}^{\infty } \frac{(x-1) x^i \left(x^{i+1}-x^i+2
x-1\right)}{(1-2 x) \left(-2 x^{i+1}+2 x^i-2 x+1\right)}-\sum
_{i=1}^{\infty } \frac{(1-x) x^i}{2 \left(-2 x^{i+1}+2 x^i-2
x+1\right)}.
\]
By combining corresponding summands, we have
\[
\sum_{i=1}^{\infty}\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.
\begin{theorem}\label{asym}
The average proportion $E_n$ of compositions of $n$ in which the initial part has odd multiplicity satisfies
$$
E_n=\frac12+ \frac{1}{(2\log 2) n}+\frac{1}{(2 \log2)n}\delta\left(\log_2n\right)
+o(1/n),
$$
where $\delta(x)$ is a periodic function of period 1 and mean
0 and small amplitude, which is given by the Fourier series
$$
\delta(x)=\sum_{k\ne 0}\Gamma\left(1+\chi_k\right)
e^{2k\pi ix}.
$$
The complex numbers $\chi_k$ are given by $\chi_k=2k\pi i/\log 2$.
\end{theorem}
\begin{proof} We use the second expression
\[g(x)=\frac{x}{2(1-2x)}+\sum_{i=1}^\infty\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)=\frac12+\frac{1}{2^{n-1}}[x^n]\sum_{i=1}^\infty\frac{(1-x)x^i}{2(1-2x+2x^i-2x^{i+1})}.
$$
Let $\rho _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,
\begin{equation}\label{qnk}
q_{n,k}:=[x^n]\frac{(1-x)x^k}{2(1-2x+2x^{k}-2x^{k+1})}= c_k \rho_k^{-n}+O\left(\left(\frac53\right)^n\right)
\end{equation}
with
\[ c_k=\frac{(1-{\rho_k})\rho_k^k}{2\rho_k(2-k\rho_k^{k-1}+2(k+1)\rho_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
$\rho_k$ to be approximated by $\frac12$ as $k\rightarrow \infty$. By ``bootstrapping" we find that
\begin{equation}\label{rho}
\rho_k=\frac12+2^{-k-1}+O(k2^{-2k})
\end{equation}
and hence $c_k = \frac1{2^{k+2}}+O(k 2^{-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 \cite{GP} or Knuth \cite{Knu}.
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}\le 2^{-k}\le \frac{\log n}{n}$. For such $k$ we find
\[\rho_k^{-n}=\left(\frac12\big(1+2^{-k}+O(k2^{-2k})\big)\right)^{-n}=2^n\exp\left(-\frac{n}{2^k}\right)\left(1+O\left(\frac{k n}{2^{2k}}\right)\right)\]
whence
\[q_{n,k}=2^{n-k-2}\exp\left(-\frac{n}{2^k}\right)\left(1+O\left(\frac{k}{2^k}\right)+O\left(\frac{k n}{2^{2k}}\right)\right).
\]
Then using the given upper and lower bounds on $k$,
\begin{equation}\label{main1}
q_{n,k}=2^{n-k-2}\left(\exp\left(-\frac{n}{2^k}\right)+O\left(\frac{{\log^3 n}}{n}\right)\right).
\end{equation}
Turning next to smaller values of $k \ge2$, 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 \to \infty$. Finally we must consider the larger values of $k\le n$
that is, $k$ for which $n^{-3}> 2^{-k}$, or equivalently, $k \ge 3\log_2 n$. In this range we find that
\begin{equation}\label{main2}
q_{n,k}= 2^{n-k-2}\left(\exp\left(-\frac{n}{2^k}\right)+O\left(\frac{{1}}{n^2}\right)\right).
\end{equation}
Then combining the estimates for $q_{n,k}$ over the range $2\le k \le n$ above,
\begin{align*}
E_n-\frac12&= \sum_{k=2}^n\frac{q_{n,k}}{2^{n-1}}\\
&\sim \sum_{k= 2}^n2^{-k-1}\exp\left(-\frac{n}{2^k}\right)\\
&\sim \sum_{k= 0}^{\infty}2^{-k-1}\exp\left(-\frac{n}{2^k}\right),
\end{align*}
as the additional tail sum $\sum\limits_{k>n}2^{-k-1}\exp\left(-\frac{n}{2^k}\right)$ is exponentially small.
It remains to estimate the harmonic sum
\[h(n):=\sum_{k\ge 0}2^{-k-1}\exp\left(-\frac{n}{2^k}\right),\]
as $n \to \infty$. For this we use Mellin transforms and find (see \cite[Appendix $B.7$, Equation $(48)$]{SF} ) that the Mellin transform $h^*(s)$ of $h(x)$ is
\[h^*(s)=\frac12 \Gamma[s]\frac{1}{1-2^{s-1}}\quad \textrm{for} \quad 0