UMYU Scientifica

A periodical of the Faculty of Natural and Applied Sciences, UMYU, Katsina

ISSN: 2955 – 1145 (print); 2955 – 1153 (online)

ORIGINAL RESEARCH ARTICLE

Aunu Polynomials: Excedance Number in Aunu Involutions

Sani Abba^† Aminu Usman K/Bai^††

^{† and ††}Department of Mathematics, Umaru Musa Yar’adua University, Katsina, P.M.B. 2218, Katsina, Nigeria

Corresponding Author: Sani Abba [email protected]

Abstract

An Involution is a Permutation which is equal to its own inverse. An involution is a permutation of a non-empty set \(S\) which does not contain any permutation cycles of length greater than two (i.e., it consists exclusively of fixed points and transpositions). In this research, we obtain a generating function for the Aunu polynomials. The Aunu polynomials enumerate Aunu-permutation/Involutions according to their number of descents or their number of excedances. In this research, we generated Aunu polynomials of orders: \(0,\ 1\ and\ 2\), however, further investigation in the same pattern would lead to the generation of more polynomials of higher orders.

Keywords: Aunu-permutations, Involutions and permutation statistics

1 INTRODUCTION

Permutation patterns have been used in the last two decades to study mathematical structures in Algebraic Combinatorics, see Krattenthaler (2001) and Chow and West (1999). The group-theoretic properties of some special numbers (Aunu Numbers) have also been studied, see. These numbers were also used in an elaborate scheme to determine the order of precedence and the position of each element in a finite set of prime size.

1.1 Aunu Permutations

An Aunu permutation π of order n is a permutation of the set {1, 2, . . . , n} such that its first element \(i \in \lbrack n\rbrack\) is unity \((i = 1)\), where \(\lbrack n\rbrack = \{ 1,\ 2,\ ..\ .\ ,\ n\}\) and the order of [n] equals the length of π is a prime number. Denote by A_n the set of Aunu permutations of order n. For example, for \(\lbrack 2\rbrack = \left\{ 1,2 \right\}\), A₂={12}; for [3]={1,2,3}, A₃={123,132}; for [5]={1,2,3,5},

\[A_{5} = \left\{ \begin{aligned} & \text{12345},\text{12354},\text{12435},\text{12453},\text{12534},\text{12543},\text{13245},\text{13254},\text{13425},\text{13452},\text{13524},\text{13542}, \\ & \text{14235},\text{14253},\text{14325},\text{14352},\text{14523},\text{14532},\text{15234},\text{15243},\text{15324},\text{15342},\text{15423},\text{15432} \end{aligned} \right\}\]

, etc. For \(\sigma = \ \sigma_{1}\sigma_{2}\ \cdot \ \cdot \ \cdot \ \sigma_{n} \in A_{n}\), an occurrence of an ascent is an index iϵ[n-1] such that \(\sigma(i) < \sigma(i + 1)\).

Recently, there has been a large body of literature devoted to Aunu permutations and their generalisations. The reader is referred to Ibrahim (2008), Isa and Ibrahim (2010), Ibrahim (2008), and all the references therein for recent progress in the study of statistics on Aunu permutations.

In this paper, we assume that Aunu permutations are recognised by unity at their initial state. That is, we identify an n-Aunu permutation \(\sigma = \ \sigma_{1}\sigma_{2}\ \cdot \ \cdot \ \cdot \ \sigma_{n} \in A_{n}\) with the word \(\sigma_{1}\sigma_{2}\sigma_{3} \cdot \ \cdot \ \cdot \sigma_{n}\), where σ₁ = 1. Let \(\sigma = \ \sigma_{1}\sigma_{2}\ \cdot \ \cdot \ \cdot \ \sigma_{n} \in A_{n}\). We say that an index \(i \in \lbrack n - 1\rbrack\) is an ascent if \(\sigma(i - 1) < \sigma(i)\); is a descent if \(\sigma(i - 1) > \sigma(i)\); is an excedance if \(\sigma(i) > i\); . Let ap (σ) be the number of the ascent plateaus of σ. For example, for \(\pi = 1427653\), \(\left| des(\pi) \right| = 3\); \(\left| exc(\pi) \right| = 2\).

We define

\(I_{n}(\pi) = \sum_{\pi \in A_{n}}^{}{\lbrack N_{n}(\pi)\rbrack^{|exc(\pi)|}}\).

Table 1 presents the Aunu permutations and involutions for small values of n, illustrating the distribution of descents and excedances.

Table 1: Aunu Permutation/Involutions

In Algebraic Combinatorics, a Permutation is a Mapping from a set, say \(S,\) to itself that is, if \(S\) is a non-empty set, then a mapping \(\pi:S \rightarrow S\) is refers to as a permutation on \(S\) while an Involution is a Permutation that is equal to its inverse. The set of all permutations on the set \(S = \{ 1,2,\ \ldots,n\}\) is denoted by \(S_{n} = \{\pi|\pi:S \rightarrow S\}\). An involution of a set \(S,\) therefore, is a permutation \(\sigma \in S_{n}\) which consists exclusively of fixed points and transpositions. A transposition is a cyclic permutation of length two. Thus Involutions are permutations that are their own inverse-permutation. For example, there are two involution permutations in \(S_{2}\) are the elements \((12)\) and \((21)\), while in \(S_{3}\). There are four involution permutations on \(S = \{ 1,2,3\}\) elements are \(I\), \((23)\), \((12)\) and \((13)\). We denote by \(I_{n}\) and \(I_{n}(\sigma)\). The set of involutions of length n and the set of involutions of length n that avoid the pattern \(\sigma,\) respectively.

The distribution of the permutation statistics fixed point \(fp\) and exedence \(exc\) in permutations avoiding a certain pattern, \(\sigma\) will be one of the main areas of discussion in this paper. In a permutation \(\pi \in S_{n}\) an index \(i\) for which \(\pi(i) < 1,\ \)will be called a deficiency if the element of the permutation is neither a fixed point nor an excedance. thus (i.e.\(def(\pi) = \{ i \in \lbrack n - 1\rbrack:\pi(i) < i\}\)). We denote the number of deficiencies in π by \(def(\pi)\).

An index \(i\) such that \(\pi(i) > 1,\) is called excedance in π. We denote the set of all excedences by \(exc(\pi) = \{ i \in \lbrack n - 1\rbrack:\pi(i) > i\}\) while a fixed point in π is an index \(i\) such that \(\pi(i) > 1,\) (i.e. \(fix(\pi) = \{ i \in \lbrack n - 1\rbrack:\pi(i) = i\}\)) A fixed-point free permutation is called a derangement. A permutation \(\pi \in S_{n}\) is called an involution, if \(\pi\ = \ \pi^{- 1}\). Let \(q\ = \ q_{1}q_{2}\ .\ .\ .\ q_{k}\) and \(p = p_{1}p_{2}.\ .\ .\ p_{n}\) be Aunu-permutations in the symmetric groups \(S_{k}\) and \(S_{n}\)_, respectively, where \(k \leq n\). Let \(|exc(\pi)|,\ |fix\ (\pi)|\) and \(|cyc\ (\pi)|\) denote the number of excedances, fixed points and cycles in \(\pi\), respectively. For example, the Aunu-permutation \(\pi = 1427653\) has the cycle decomposition \((1)(2473)(56)\), so \(|cyc\ (\pi)| = 3\), \(|exc\ (\pi)| = 3\), \(\left| def(\pi) \right| = 3\) and \(|fix\ (\pi)| = 1\). We presumably refer to their corresponding sets if the modulus signs are removed. Thus for \(\pi = 1427653\), we have \(cys(\pi) = \left\{ (1),\ (2473),(56) \right\}\), \(exc(\pi) = \left\{ 2,4,5 \right\}\), \(def(\pi) = \left\{ 3,6,7 \right\}\) and \(fix(\pi) = \left\{ 1 \right\}\), where \(def(\pi)\) refers to the deficiency set in \(\pi\).

We found that the joint distribution of the pair of statistics (\(fix(\pi)\),\(exc(\pi)\)) is the same in 312-avoiding, as in 231-avoiding Aunu-permutation Involutions. This generalizes a recent result of Robertson, Saracino and Zeilberger. The key ideas are to establish ‘Aunarian polynomial’. In particular, this gives a simple bijective proof of the equi-distribution of fixed points in the above two sets of restricted permutations. This introduces a bijection between 312- and 231-avoiding Aunu-permutation Involutions that preserves the number of fixed points and the number of excedances.

Consider, for instance, the two sets of restricted Aunu-permutations Involutions;

\[I_{5}(312) = \{ 12345,12354,12435,12543,13245,13254,14325,15432\}\]

and

\[I_{5}(231) = \{ 12345,12354,12435,12543,13245,13254,14325,15432\}\]

2.0 METHODOLOGY

We denote the permutation \(\pi \in S_{n}\) by the sequence \(\lbrack\pi(1),\pi(2),...,\pi(n)\rbrack\) . That is, the set of bijections on \(\{ 1,2,...,n\}\) is denoted by \(S_{n} = \{\pi|\pi:S \rightarrow S\}\) and set of all permutations of length \(n\) that contains exactly \(r\) occurrence of a pattern \(\sigma\) by \(F_{n}^{r}(\sigma)\) where \(\sigma \in S_{k}\ and\ k \leq n\). We also denote by\(N_{\sigma}(\pi)\) (and \(|N_{\sigma}(\pi)|\)) the set (and respectively number) of occurrences of the pattern \(\sigma\) in the permutation \(\pi\). We denote by \(|F_{n}^{r}(\sigma)|\) the number of permutations in \(S_{n}\)such that \(|N_{\sigma}(\pi)| = r\).

The next step is to consider permutations containing some prescribed number of sequences/sub-permutations that have the same relative order as a given pattern. The tools involved are enumeration techniques. Observe that if π contains 123, then any 123-avoiding permutation avoids π as well, so in what follows we always assume that σ≼π iff\(\sigma^{- 1}\)≼\(\pi^{- 1}\), for instance.

We use one-line notation to express permutations in \(S_{n}\). However, use cycle notation to express permutations when needed. For example, Suppose \(\pi \in S_{n}\). Since πis viewed as a bijection on the set \(\lbrack n\rbrack = \{ 1,\text{ 2},\ .\ .\ .\ ,\ n\}\). This bijection can be represented by listing the elements in the set \(\lbrack n\rbrack = \{ 1,\text{ 2},\ .\ .\ .\ ,\ n\}\)in a row with their images under π listed immediately below.

\[\pi:\begin{pmatrix} 1\text{ }2\ .\ .\ .\text{ }n \\ (1)\pi\text{ }(2)\pi\ ...\ (n)\pi \end{pmatrix}\]

On the other hand, we expressed elements in\(\lbrack n\rbrack = \{ 1,\text{ 2},\ .\ .\ .\ ,\ n\}\) as cycles (in cyclic form), let \(i_{1},i_{2},...,i_{n}\) be distinct elements in the set \(\lbrack n\rbrack = \{ 1,\text{ 2},\ .\ .\ .\ ,\ n\}\).Then \((i_{1}i_{2}...i_{n - 1}i_{n})\) is called a cycle of length nor an n-cycle, and represents the permutation \(\pi \in S_{n}\) that maps \(i_{1} \mapsto i_{2},i_{2} \mapsto i_{3},...,i_{n - 1} \mapsto i_{n},i_{n} \mapsto i_{1}\), and every other element in s to itself. Every permutation in \(S_{n}\)can be expressed as either a single cycle or a product of disjoint cycles. For example, the permutation \(\pi = 345162 \in S_{6}\) can be expressed as the 6-cycle (135624). Next, consider permutation \(\alpha = \text{345612} \in S_{6}\). To express αusing cycle notation, we must use more than one cycle. For example, we can express αas the following “product” of two 3-cycles: (135)(246). Observe thatthese cycles contain no element(s) in common, and so they are said to be disjoint. And because they are disjoint, the order in which they are listed does not matter. The permutation αcan also be expressed as (246)(135).In an expression of a permutation as a product of cycles, the cycles need not be disjoint. For example, the permutation \(\pi = \left( \text{135624} \right)\) defined above can also be expressed as the product (13)(15)(16)(12)(14) of 2-cycles.Because these 2-cycles are not disjoint, the order in which they are listed matters.

Counting occurrences of the patterns \(\mathbf{\sigma \in}\mathbf{S}_{\mathbf{3}}\) in the permutations \(\mathbf{\pi \in}\mathbf{S}_{\mathbf{n}}\).

The counting of occurrences of a pattern σ in a permutation πis the number of distinct subsequences in the permutation πwhich are order isomorphic to the pattern σ. Let \(\pi = a_{1}a_{2}...a_{t}\), \(\tau = b_{1}b_{2}...b_{S}\) be finite sequences of integers; then a subsequence of π of the same length as τ is said to be an occurrence of τ if its entries occur in the same relative order as in τ . More precisely, given indices \(i_{1} < i_{2} < ... < i_{S}\), the subsequence \(a_{i_{1}}a_{i_{2}}...a_{i_{S}}\)of π is an occurrence of τ if and only if for all j, k, we have \(a_{ij} < a_{i_{k}} \Leftrightarrow b_{i} < b_{j}\). Thus, for example, the patterns in \(\sigma \in S_{3}\) occur in the following selected permutations\(\pi \in S_{5}\); for \(\pi = \text{15423}\), there are \(\begin{pmatrix} 5 \\ 3 \end{pmatrix} = 10\) distinct three-length subsequences in π, \(154,152,153,142,143,123,542,543,524,423\).Then

\(|N_{\lbrack 123\rbrack}(\pi)| = 1,|N_{\lbrack 132\rbrack}(\pi)| = 5,|N_{\lbrack 213\rbrack}(\pi)| = |N_{\lbrack 231\rbrack}(\pi)| = 0,|N_{\lbrack 312\rbrack}(\pi)| = |N_{\lbrack 321\rbrack}(\pi)| = 2\); and of course \(\sum_{\sigma \in S_{3}}^{}{|N_{\sigma}(\pi)|} = 10\). For \(\pi = \text{32451}\), 10 three-length subsequences of \(\pi = \text{32451}\) are

\(324,325,321,345,341,351,245,241,251,451\). Then

\(|N_{\lbrack 123\rbrack}(\pi)| = |N_{\lbrack 213\rbrack}(\pi)| = 2,|N_{\lbrack 321\rbrack}(\pi)| = 1,|N_{\lbrack 132\rbrack}(\pi)| = |N_{\lbrack 312\rbrack}(\pi)| = 0,|N_{\lbrack 231\rbrack}(\pi)| = 5\);

For \(\pi = \text{51243}\), 10 three-length subsequences of \(\pi = \text{51243}\) are

\(512,514,513,524,523,543,124,123,143,243\). Then

\(|N_{\lbrack 123\rbrack}(\pi)| = |N_{\lbrack 132\rbrack}(\pi)| = 2,|N_{\lbrack 213\rbrack}(\pi)| = |N_{\lbrack 231\rbrack}(\pi)| = 0|N_{\lbrack 321\rbrack}(\pi)| = 1,|N_{\lbrack 312\rbrack}(\pi)| = 5\);

For \(\pi = \text{14532}\), 10 three-length subsequences of \(\pi = \text{14532}\) are

\(145,143,142,153,152,132,453,452,432,532\). Then

\(|N_{\lbrack 123\rbrack}(\pi)| = 1,|N_{\lbrack 132\rbrack}(\pi)| = 5,|N_{\lbrack 213\rbrack}(\pi)| = |N_{\lbrack 312\rbrack}(\pi)| = 0,|N_{\lbrack 231\rbrack}(\pi)| = |N_{\lbrack 321\rbrack}(\pi)| = 2\).

Note that the number \(|N_{\sigma}(\pi)|\) is independent of π for example,

\[\bullet for\left| N_{\sigma}(15423) \right|when\ \sigma = 213,231,123,312,321,132,we\ have\ 0,0,1,2,2,5;\]

\[\bullet for\left| N_{\sigma}(32451) \right|when\ \sigma = 132,312,321,123,213,231,we\ have\ 0,0,1,2,2,5;\]

\[\bullet for\left| N_{\sigma}(51243) \right|when\ \sigma = 213,231,321,123,132,312,,we\ have\ 0,0,1,2,2,5;\]

\[\bullet for|N_{\sigma}(14532)|when\ \sigma = 213,312,123,231,321,132,we\ have\ 0,0,1,2,2,5.\]

Observe that on one hand, the permutation π the in second, third and fourth rows (32451, 51243 and 14532) are the reversal, complementation and inversion of the permutation in the first raw (15423). On the other hand, the corresponding patterns, specifically those bearing the same values of \(|N_{\sigma}(\pi)|\) are related similar. For example, the patterns with values of \(|N_{\sigma}(\pi)| = 0\)in 2^nd, 3^rd, and 4^th rows (i.e. \(\{ 312,132\},\{ 231,213\},and\{ 213,312\}\)) are reversal, complementation and inversion respectively of the corresponding patterns in the 1^st raw (i.e. \(\{ 213,231\}\)), etc. Similarly, the patterns 321,321 and 123, each bearing the same value \(|N_{\sigma}(\pi)| = 1\), are reversal, complementation and inversion of the corresponding pattern 123 in the 1^st raw; the pairs of patterns, each bearing the value \(|N_{\sigma}(\pi)| = 2\), {213,123}, {132,123}, and {231,321} in the 2^nd, 3^rd, and 4^th rows, relate in the same manner to the pair {312,321} in the 1^st raw; and, lastly, the patterns 231,312 and 132 in the 2^nd, 3^rd, and 4^th rows relate in the same manner to the pattern 132 in the 1^st raw, each bearing \(|N_{\sigma}(\pi)| = 5\). We summarized the above in Table 2 below;

Table 2: Patterns occurrences in some permutations via standard bijections

Table 2, shows that there are easy correspondences which explain why

\(|F_{n}(132)|\ = \ |F_{n}(213)|\ = \ |F_{n}(231)|\ = \ |F_{n}(312)|\),

and why

\(|F_{n}(123)|\ = \ |F_{n}(321)|\).

A tree diagram for Aunu permutations of length 5 containing exactly one Occurrence of 123 pattern is shown in Figure 1.

Figure 1: Tree representation for \(\mathbf{F}_{\mathbf{5}}^{\mathbf{1}}\mathbf{(123)}\)

2.1 The cycle descent statistic on Aunu-permutations

In this section, we study the cycle descent statistic on permutations. Several involutions on Aunu-permutations are constructed.

Denote by \(\left| des(\pi) \right|\) and \(\left| asc(\pi) \right|\) the number of descents and the number of ascents of π, respectively. Although the concepts of excedance and descent are closely related and can be considered as mirror images of each other, the story is quite different when it comes to descent sets versus excedance sets. The descent set of a permutation \(\pi\ = \ \pi(1)\pi(2)\ .\ .\ .\ \pi(n) \in S_{n}\) is the set of indices i for which \(\pi(i) > \pi(i + 1)\), whereas the excedance set is the set of indices i for which \(\pi(i)\ > \ i\).

Thus, we say that \(i \leq n - 1\) is a descent of \(\pi \in S_{n}\) if \(\pi(i) > \pi(i + 1)\) (i.e. \(des(\pi) = \{ i \in \lbrack n - 1\rbrack:\pi(i) > \pi(i + 1)\}\)). Similarly, \(i \leq n - 1\) is an ascent of \(\pi \in S_{n}\) if \(\pi(i) < \pi(i + 1)\) (i.e. \(asc(\pi) = \{ i \in \lbrack n - 1\rbrack:\pi(i) < \pi(i + 1)\}\)). For example, if π = 63528174, then the

\(des(\pi) = \left\{ 1 \rightarrow 2,3 \rightarrow 4,5 \rightarrow 6,7 \rightarrow 8 \right\}\),

therefore \(\left| des(\pi) \right| = 4\);

\(asc(\pi) = \left\{ 2 \rightarrow 3,4 \rightarrow 5,6 \rightarrow 7 \right\}\),

therefore \(\left| asc(\pi) \right| = 3\); \(exc(\pi) = \left\{ 1,2,3,5 \right\}\), therefore \(|exc(\pi)| = 4\); \(def(\pi) = \left\{ 4,6,8 \right\}\), therefore \(|def\ (\pi)| = 3\); while \(fix(\pi) = \{ 7\}\), therefore \(|fix(\pi)| = 1\). A right-to-left minimum of π is an element π _i such that \(\pi_{i} < \pi_{j}\) for all j > i. In other words, a right-to-left minimum of π is a least element of the increasing subsequence of π.

Let \(\left| lis(\pi) \right|\) denote the length of the longest increasing subsequence of π, i.e., the largest m for which there exist indices \(i_{1} < i_{2} < ... < i_{m}\) such that \(\pi_{i_{1}} < \pi_{i_{2}} < ... < \pi_{i_{m}}\). Equivalently, in terms of forbidden patterns, \(\left| lis(\pi) \right|\) is the smallest m such that π avoids 12 . . . (m+1). The length of the longest decreasing subsequence is defined analogously, and it is denoted \(\left| lds(\pi) \right|\).

For example, if π = 17463528, then \(fix(\pi) = \{ 1,8\}\), hence \(|fix(\pi)| = 2\); \(exc(\pi) = \left\{ 2,3,4 \right\}\), hence \(\left| exc(\pi) \right| = 3\); \(des(\pi) = \left\{ 2 \rightarrow 3,4 \rightarrow 5,6 \rightarrow 7 \right\}\), hence \(\left| des(\pi) \right| = 3\); \(lis(\pi) = \left\{ 17,46,35,28 \right\}\), hence \(\left| \ lis(\pi) \right| = 4\); \(lds(\pi) = \left\{ 74,63,52 \right\}\), hence \(\left| lds(\pi) \right| = 3\).

A standard cycle decomposition of \(\pi \in S_{n}\) is defined by requiring that each cycle be written with its smallest element first, and that the cycles be written in increasing order of their smallest elements. A permutation is said to be cyclic if there is only one cycle in its cycle decomposition.

2.1.1. Combinatorial classes and generating functions

Here we direct the reader to Sedgewick and Flajolet (1996) for a detailed account of combinatorial classes and the symbolic method. See also Moustakas (2018). Let \(A\) be a class of unlabelled combinatorial objects and let \(|\alpha|\) be the size of an object \(\alpha \in A\). If \(A_{n}\) denotes the objects in \(A\) of size \(n\) and \(a_{n} = |A_{n}|\), then the ordinary generating function of the class \(A\) is

\(I_{n}(\pi) = \sum_{\pi \in A_{n}}^{}{\lbrack N_{n}(\pi)\rbrack^{|exc(\pi)|}} = \sum_{n \geq 2}^{}{\lbrack N_{n}(\pi)\rbrack^{n|}}\). ….(i)

In our context, the size of an object z (an Aunu permutation) is simply the fixed-pointlength or length of excedance. From now on we will use the acronym GF as a shorthand for the term generating function. See Alon and Friedgut (2000); see also Arratia, (1999); Bagno and Garber (2007); Bona (1999); Brenti (1994) and Brenti (2000); Chen at el (2009); Foata (1970); Klazar (2000); Ksavxelof and Zeng (2003); Mansour and Vainshtein, (2000), (2001); Reifegerste (2003); Zhoa (2013).

There is a direct correspondence between set-theoretic operations (or “constructions") on combinatorial classes and algebraic operations on \(GFs.\ Table\ 2\) summari this correspondence for the operations used in this work. There, “union" means union of disjoint copies, “product" is the usual Cartesian product, and “sequence" forms an ordered sequence in the usual sense. Enumerations according to size and auxiliary parameters.

Throughout this paper, the variable z is reserved for marking the length of an Aunu-permutation and x is used to mark the number of excedances of an Aunu-permutation, unless otherwise stated.

where \(D_{n,i}\) is the set of derangements \(\pi\) of \(\lbrack n\rbrack\) such that \(\pi(n)\ = \ i\).

2.1.2. Aunu polynomials

Throughout this paper, the variable \(x\) is used for marking the number of excedances of an Aunu permutation Involution, unless otherwise stated.

2.1.3. Counting some permutations statistic in Aunu Involutions.

In this sub-section we present a general approach to determine the number of some permutation statistic (see Table 3) in n-permutation Involutions.

Table 3: Distribution of some permutation statistics in few sets (I₂,I₃ and I₅) of Aunu Involutions

The n-th Aunu polynomial, \(I_{n}(x)\ = \ I_{n_{1}}\ + I_{n_{2}}x + \ I_{n_{3}}x^{2} + ・\ ・\ ・ + I_{n_{(n - 1)}}x^{n - 2}\), may be defined as the generating polynomial for the number of fixed-points over the symmetric group \(G_{n}\), i.e.

\(\text{ }I_{n}(x) = \sum_{\pi \in G_{n}}^{}x^{|exc(\pi)|}\text{ }for\text{ }n \geq 2\) … (x)

where \(|exc(\pi)| = |\{ i:\pi(i) > i\}|\) and where \(\pi:i \rightarrow \pi(i),\text{ }(1 \leq i \leq n)\) is identified with the word \(a_{1}a_{2}\ ・\ ・\ ・\ a_{n}\) in the distinct n letters \(a_{1},a_{2}\text{, }・\ ・\ ・,\ a_{n}\) taken out of \(\lbrack n\rbrack = \{ 1,2,...,n\}\).

For the first few values of n we have:

\[I_{n}(x) = \left\{ \begin{aligned} & 1,\text{ }if\ n = 2 \\ & 1 + x,\text{ }if\ n = 3 \\ & 1 + 6x + 3x^{2},\text{ }if\ n = 5 \end{aligned} \right\}\]

Linearity of expectation states that the expected value of a sum of random variables equals the sum of the individual expectations.

3 CONCLUSION

Though we can use excess as a permutation statistic to generate an Aunu polynomial for free, there are several other investigations that could be carried out on other permutation statistics, such as derangements, descents, ascent deficiencies, etc. For instance, further investigation could be carried out to determine whether or not Aunu polynomials have a simple combinatorial interpretation in terms of some other permutation statistic.

REFERENCES

Alon, N., & Friedgut, E. (2000). On the number of permutations avoiding a given pattern. Journal of Combinatorics Theory Ser. A, 89, 133-140. [Crossref]

Arratia, R. (1999). On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern. Electronic Journal of Combinatorics, 6(1), Note N1. [Crossref]

Bagno, E., Butman, A., & Garber, D. (2007). Statistics on the multi-colored permutation groups. Electronic Journal of Combinatorics, 14, #R24. [Crossref]

Bóna, M. (1999). The solution of a conjecture of Stanley and Wilf for all layered patterns. Journal of Combinatorics Theory Ser. A, 85, 96-104. [Crossref]

Brenti, F. (1994). q-Eulerian polynomials arising from Coxeter groups. Electronic Journal of Combinatorics, 15, 417-441. [Crossref]

Brenti, F. (2000). A class of q-symmetric functions arising from plethysm. Journal of Combinatorics Theory Ser. A, 91, 137-170. [Crossref]

Chen, W. Y. C., Tang, R. L., & Zhao, A. F. Y. (2009). Derangement polynomials and excedances of type B. Electronic Journal of Combinatorics, 16(2), #R15. [Crossref]

Chow, T., & West, J. (1999). Permutations with forbidden subsequences and Chebyshev polynomials. Discrete Mathematics, 204, 119-128. [Crossref]

Foata, D., & Schützenberger, M. (1970). Théorie géométrique des polynômes eulériens (Lecture Notes in Mathematics, Vol. 138). Springer-Verlag. [Crossref]

Ibrahim, A. A. (2008). Some transformation schemes involving the special (132)-avoiding permutation patterns and a binary coding: An algorithmic approach. Asian Journal of Algebra, 1(1), 10-14. [Crossref]

Ibrahim, A. A., Sloane, N. J. S., et al. (2006). Integer Sequence A119626 [Online Encyclopedia of Integer Sequences]. [Link]

Isa, G. A., & Ibrahim, A. A. (2010). A new method of constructing a variety of finite group based on some succession scheme.

Klazar, M. (2000). The Füredi-Hajnal conjecture implies the Stanley-Wilf conjecture. In Proceedings Formal power series and algebraic combinatorics 2000 (pp. 250-255). Springer. [Crossref]

Krattenthaler, C. (2001). Permutations with restricted patterns and Dyck paths. Advances in Applied Mathematics, 27, 510-530. [Crossref]

Ksavrelof, G., & Zeng, J. (2003). Two involutions for signed excedance numbers. Sém. Lothar. Combin., 49, Art. B49e.

Mansour, T., & Mansour and Vainshtein, A. (2000). Restricted permutations, continued fractions, and Chebyshev polynomials. Electronic Journal of Combinatorics, 7, #R17. [Crossref]

Mansour, T., & Vainshtein, A. (2001). Restricted 132-avoiding permutations. Advances in Applied Mathematics, 26, 258-269. [Crossref]

Moustakas, V. P. (2018). The Eulerian distribution on the involutions of the hyperoctahedral group is unimodal. Electronic Journal of Combinatorics, 14, #R24.

Reifegerste, A. Reifegerste (2003). On the diagram of 132-avoiding permutations. European Journal of Combinatorics, 24, 759-776. [Crossref]

Sedgewick, R., & Flajolet, P. (1996). An introduction to the analysis of algorithms. Addison-Wesley.

Zhao, A. F. Y. (2013). Excedance numbers for the permutations of type B. Electronic Journal of Combinatorics, 20(2), #P28. [Crossref]