Séminaire Lotharingien de Combinatoire 85 (2021), Article B85d

CYCLIC SHUFFLE COMPATIBILITY

Rachel Domagalski

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA, domagal9@msu.edu

Jinting Liang

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA, liangj26@msu.edu

Quinn Minnich

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA, minnichq@msu.edu

Bruce E. Sagan

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA, bsagan@msu.edu

Jamie Schmidt

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA, schmi710@msu.edu

Alexander Sietsema

Department of Mathematics, Michigan State University, East Lansing, MI 48824-1027, USA, sietsem6@msu.edu

Abstract. Consider a permutation π to be any finite list of distinct positive integers. A statistic is a function St whose domain is all permutations. Let π �σ be the set of shuffles of two disjoint permutations π and σ. We say that St is shuffle compatible if the distribution of St over π � σ depends only on St(π), St(σ), and the lengths of π and σ. This notion is implicit in Stanley’s work on P -partitions and was first explicitly studied by Gessel and Zhuang. One of the places where shuffles are useful is in describing the product in the algebra of quasisymmetric functions. Recently Adin, Gessel, Reiner, and Roichman defined an algebra of cyclic quasisymmetric functions where a cyclic version of shuffling comes into play. The purpose of this paper is to define and study cyclic shuffle compatibility. In particular, we show how one can lift shuffle compatibility results for (linear) permutations to cyclic ones. We then apply this result to cyclic descents and cyclic peaks. We also discuss the problem of finding a cyclic analogue of the major index.

1. Introduction

Let ℕ and ℙ be the nonnegative and positive integers, respectively. If n ∈ ℕ then let [n] = {1, 2, …, n}. Given a finite A ⊆ ℙ then a linear permutation of A is a linear arrangement

2020 Mathematics Subject Classification. Primary 05A05; Secondary 05A19. Key words and phrases. cyclic permutation, descent, peak, shuffle compatible.

π = π_{1}π_{2} … π_{n} of the elements of A. We let

L(A) = {π | π is a linear permutation of A}.

We often drop “linear” if it is understood from context. For example,

L({1, 3, 6}) = {136, 163, 316, 361, 613, 631}.

If π = π_{1}π_{2} … π_{n} then n is called the length of π, written #π = |π| = n. The hash symbol and absolute value sign will also be used for the cardinality of a set. In fact, we will often treat permutations as sets if no problem will result and write things such as x ∈ π in place of the more cumbersome π_{i} = x for some i.

A (linear) permutation statistic is a function St whose domain is all linear permutations. There are four statistics which will concern us here. A permutation π = π_{1}π_{2} … π_{n} has descent set

Des π = {i | π_{i} > π_{i+1}},

descent number

des π = # Des π,

peak set

Pk π = {i | π_{i−1} < π_{i} > π_{i+1}},

and peak number

pk π = # Pk π.

To illustrate, if π = 4218596 then Des π = {1, 2, 4, 6}, des π = 4, Pk π = {4, 6}, and pk π = 2. We will be particularly concerned with a particular type of statistic which is determined by the descent set in the following sense. Statistic St is a descent statistic if Des π = Des σ and #π = #σ implies St π = St σ. Note that Des itself, des, Pk, and pk are all descent statistics. A statistic which is not a descent statistic would be St π = π_{1} for nonempty π and St ∅ = 0. We will often need to evaluate a statistic St on a set of permutations Π. So we define the distribution of St over Π to be

St Π = {{St π | π ∈ Π}}.

Note that this is a set with multiplicity since St may evaluate to the same thing on various members of Π. We will sometimes use exponents to denote multiplicities where, as usual, no exponent means multiplicity 1. For example

des{123, 132, 312, 321} = {{0, 1, 1, 2}} = {{0, 1^{2}, 2}}.

We will also need to combine functions on permutations and statistics. If Π and Π′ are sets of permutations and St is a statistic, then a function f : Π → Π′ is St-preserving if

St f(π) = St π

for all π ∈ Π.

If π ∈ L(A) and σ ∈ L(B) where A ∩ B = ∅ then these permutations have shuffle set

π � σ = {τ ∈ L(A ⊎ B) | π, σ are subwords of τ}

where a subwords of a permutation τ is a subsequence of (not necessarily consecutive) elements of τ. For example,

25 � 73 = {2573, 2753, 2735, 7253, 7235, 7325}.  (1)

Whenever we write the shuffle of two permutations, we will tacitly assume that they are from disjoint sets.

An important use of the shuffle set is in computing the product of two fundamental quasisymmetric functions in the algebra QSym of quasisymmetric functions. More information about QSym can be found in the texts of Luoto, Mykytiuk, and van Willigenburg [LMvW13], Sagan [Sag20], or Stanley [Sta99]. In order to prove that this product formula is well defined, one needs shuffle compatibility. Roughly speaking, a statistic St is shuffle compatible if the distribution of St over π � σ depends only on St π, St σ, and the lengths #π and #σ. To be precise, St is shuffle compatible if for all quadruples π, π′, σ, σ′ with St π = St π′, St σ = St σ′, #π = #π′, and #σ = #σ′ we have

St(π � σ) = St(π′ � σ′).

For example, from equation (1) it is easy to see that

des(25 � 73) = {{1^{3}, 2^{3}}}

The reader can check that this is also the distribution des(12 � 43) which is because des is shuffle compatible. Shuffle compatibility is implicit in Stanley’s theory of P -partitions [Sta72] and he proved a result implying the shuffle compatibility of des. Gessel and Zhuang [GZ18] were the first to define the concept explicitly and prove many shuffle compatibility results, including those for the other three statistics defined previously.

Theorem 1.1. The statistics

Des, des, Pk, pk

are all shuffle compatible. □

Other work on shuffle compatibility has been done by Baker-Jarvis and Sagan [BJS20], by Oğuz [Oğu], and by Grinberg [Gri18].

Recently Adin, Gessel, Reiner, and Roichman [AGRR20] introduced a cyclic version of quasisymmetric functions with a corresponding cyclic shuffle operation. A linear permutation π = π_{1}π_{2} … π_{n} has a corresponding cyclic permutation [π] which is the set of all its rotations, namely

[π] = {π_{1}π_{2} …, π_{n}, π_{2} …, π_{n}π_{1}, …, π_{n}π_{1} … π_{n−1}}.

For example

[3725] = {3725, 7253, 2537, 5372}

so that

[3725] = [7253] = [2537] = [5372].

The reader should bear in mind the difference between the notation [n] for an interval of integers and [π] for a cyclic permutation. We let

C(A) = {[π] | [π] is a cyclic permutation of A}.

To illustrate

C({2, 3, 5, 7}) = {[2357], [2375], [2537], [2735], [2573], [2753]}.

We can lift the linear permutation statistics we have introduced to the cyclic realm as follows. Define the cyclic descent set and cyclic descent number for a linear permutation π = π_{1}π_{2} … π_{n} to be

cDes π = {i ∈ [n] | π_{i} > π_{i+1} where i is taken modulo n}

and cdes π = # cDes π, respectively. Returning to π = 4218596 we have cDes π = {1, 2, 4, 6, 7} and cdes π = 5. Now a cyclic permutation [π] will have cyclic descent set

cDes[π] = {{cDes σ | σ ∈ [π]}}.

Notice that this is a multiset since two different σ can have the same cyclic descent set. Also define the cyclic descent number

cdes[π] = cdes π.

Note that this is well defined since all elements of [π] have the same number of cyclic descents. To illustrate

cDes[3725] = {{cDes 3725, cDes 7253, cDes 2537, cDes 5372}} = {{ {1, 3}^{2}, {2, 4}^{2} }}

and cdes[3725] = 2. An important point later will be that if S is one of the sets in cDes[π] then all of the other member sets can be obtained by adding i to the elements of S modulo n = #π as i runs over [n].

We deal with peaks in a similar manner, defining the cyclic peak set and cyclic peak number in the linear case by

cPk π = {i ∈ [n] | π_{i−1} < π_{i} > π_{i+1} where i is taken modulo n}

and

cpk π = # cpk π,

respectively. For π = 4218593 we have cPk π = {1, 4, 6} and cpk π = 3. The extension to cyclic permutations is as expected

cPk[π] = {{cPk σ | σ ∈ [π]}}

and

cpk[π] = cpk π.

In general, a cyclic permutation statistic is any function cSt whose domain is cyclic permutations. And cSt is a cyclic descent statistic if cDes[π] = cDes[σ] and #π = #σ implies cSt[π] = cSt[σ]. All four of our cyclic statistics are cyclic descent statistics. Functions preserving cyclic permutation statistics are defined in the obvious way.

The definitions for shuffles follow the same pattern already established. Given [π] ∈ C(A) and [σ] ∈ C(B) where A ∩ B = ∅ we define their cyclic shuffle set to be

[π] � [σ] = {[τ] ∈ C(A ⊎ B) | [π], [σ] are circular subwords of [τ]}.

Alternatively, there are rotations π′ and σ′ of π and σ, respectively, which are both linear subwords of τ. To illustrate,

[13] � [24] = {[1324], [1342], [1234], [1432], [1243], [1423]}.  (2)

Call a cyclic permutation statistic cSt cyclic shuffle compatible if for all quadruples [π], [π′], [σ], [σ′] with cSt[π] = cSt[π′], cSt[σ] = cSt[σ′], #π = #π′, and #σ = #σ′ we have

cSt([π] � [σ]) = cSt([π′] � [σ′]).

The aim of the present work is to study this concept. In particular, we will prove the following theorem.

Theorem 1.2. The statistics

cDes, cdes, cPk, cpk

are all cyclic shuffle compatible.

The rest of this paper is structured as follows. Rather than proving each of the cases of Theorem 1.2 in an ad hoc manner, we will develop a method for lifting linear shuffle compatibility results to cyclic ones. This will be done in the next section. Then in Section 3 we will apply our Lifting Lemma to each of the four statistics in turn. Finally, we will end with a section of comments and a future direction for research.

2. The Lifting Lemma

In this section we will provide a general method for proving cyclic shuffle compatibility results as corollaries of linear ones. We will first set some notation. In the notations like C(A) and L(A) we will often drop the parentheses if they would cause double delimiters. For example L[n] is all the linear permutations of [n].

If A ⊂ ℙ and n ∈ ℕ then let

A + n = {a + n | a ∈ A}.

In particular,

[m] + n = {n + 1, n + 2, …, n + m}.

We will also need to add integers to sets modulo some m ∈ ℙ. So if A ⊆ [m] then define

A + n (mod m) = {a + n (mod m) | a ∈ A}

where the representatives are chosen to be in [m]. For example if A = {2, 4, 5} and m = 6 then

A + 3 = {5, 7, 8}

and

A + 3 (mod 6) = {1, 2, 5}.

We will also need the notion of standardization. Suppose A, B ⊂ ℙ with #A = #B = n and π = π_{1}π_{2} … π_{n} ∈ L(A). The standardization of π to B is

std_{B} π = f(π_{1})f(π_{2}) … f(π_{n}) ∈ L(B)

where f : A → B is the unique order-preserving bijection between A and B. To illustrate, if A = {2, 4, 6, 7} and B = {1, 3, 8, 9} then std_{B}(4762) = 3981. If B = [n] then we write just std π for std_{[n]} π and call this the standardization of π. Standardization for cyclic permutations is defined in the analogous manner. For example, std[79254] = [45132].

We first prove a result about cyclic descent statistics which is a cyclic analogue of one in the linear case [BJS20].

Lemma 2.1. Let cSt be a cyclic descent statistic. For any four cyclic permutations [π], [π′], [σ], [σ′] such that

std[π] = std[π′] and std[σ] = std[σ′]

we have

cSt([π] � [σ]) = cSt([π′] � [σ′]).

Proof. Since cSt is a cyclic descent statistic, its values only depend on the relative order of adjacent elements. So it suffices to prove the case when

[π] ⊎ [σ] = [π′] ⊎ [σ′] = [m + n]

where m = #π = #π′ and n = #σ = #σ′. For simplicity, let A = [m] and B = [n] + m.

We claim that it suffices to find, for any π and σ as in the previous paragraph, a cStpreserving bijection

[π] � [σ] → std_{A}[π] � std_{B}[σ].

For from this map and the hypothesis of the lemma we have

cSt([π] � [σ]) = cSt(std_{A}[π] � std_{B}[σ]) = cSt(std_{A}[π′] � std_{B}[σ′]) = cSt([π′] � [σ′]).

We will show the existence of this bijection by induction on the size of the set of what we will call out-of-order pairs

O = {(i, j) ∈ π × σ | i > j}.

If #O = 0 then [π] ∈ C(A) and [σ] ∈ C(B). It follows that [π] = std_{A}[π] and [σ] = st_{B}[σ] so the identity map will do.

For the induction step, let #O > 0. Then there must be a pair (i, i − 1) ∈ O. Let π′′ = (i − 1, i)π and σ′′ = (i − 1, i)σ where (i − 1, i) is the transposition which exchanges i − 1 and i. We will be done if we can construct a cSt preserving bijection

T_{i} : [π] � [σ] → [π′′] � [σ′′].

This is because π′′, σ′′ have fewer out-of-order pairs and so, by induction, there is a cStpreserving bijection [π′′] � [σ′′] → std_{A}[π′′] � std_{B}[σ′′] which, when composed with T_{i}, will finish the construction.

Define T_{i} by

T_{i}[τ] = \begin{cases}[(i − 1, i)τ] & if i − 1, i are not cyclically adjacent in [τ], \\ [τ] & else. \end{cases}

We must first check that T_{i} is well defined in that T_{i}[τ] ∈ [π′′] � [σ′′]. This is true if i − 1 and i are not cyclically adjacent since i − 1 and i have been swapped in all three cyclic permutations involved. If they are adjacent then the relative order of the elements of [τ] corresponding to [π] and [π′′] are the same, and similarly for [σ] and [σ′′]. So leaving [τ] fixed again gives a shuffle in the range.

Finally, we need to verify that T_{i} is cSt preserving. Since cSt is a descent statistic, it suffices to show that T_{i} is cDes preserving. Certainly this is true if [τ] is fixed. And if it is not, then i − 1, i are not cyclically adjacent in [τ]. But switching i − 1 and i could only change a cyclic descent into a cyclic ascent or vice-versa if these two elements were adjacent. So in this case cDes[(i − 1, i)τ] = cDes[τ] and we are done. □

As an example of the map T_{i}, consider the shuffle set in (2). Here we can take i = 3 since 3 ∈ 13 and 2 ∈ 24. For [τ] = [1324] we have 2 and 3 cyclically adjacent so

T_{3}[1324] = [1324] ∈ [12] � [34]

as desired. On the other hand, in [1342] the 2 and 3 are not cyclically adjacent so

T_{3}[1342] = [1243].

Note that [1243] ∈ [12] � [34] and

cDes[1243] = {{ {1, 2}, {2, 3}, {3, 4}, {1, 4} }} = cDes[1342].

We can use the previous lemma to drastically cut down on the number of cases which need to be checked to obtain cyclic shuffle compatibility. In particular, the component permutations in the shuffles to be considered can be on consecutive intervals of integers. And one can keep one component of the shuffle constant while the other varies.

Corollary 2.2. Suppose that cSt is cyclic descent statistic. The following are equivalent. (a) The statistic cSt is cyclic shuffle compatible.

(b) If cSt([π]) = cSt([π′]) where [π], [π′] ∈ C[m] and [σ] ∈ C([n] + m) for some m, n ∈ ℕ

then

cSt([π] � [σ]) = cSt([π′] � [σ]).

(c) If cSt([σ]) = cSt([σ′]) where [σ], [σ′] ∈ C([n] + m) and [π] ∈ C[m] for some m, n ∈ ℕ

then

cSt([π] � [σ]) = cSt([π] � [σ′]).

Proof. We will prove the equivalence of (a) and (b) since the equivalence of (a) and (c) is similar. Clearly (a) implies (b). For the converse, let π, π′, σ, σ′ be any four permutations satisfying the hypothesis of the cyclic shuffle compatible definition and let m = #π = #π′, n = #σ = #σ′. Also let A = [m], B = [n] + m, A′ = [m] + n, and B′ = [n]. Then, using Lemma 2.1 and (b) alternately

cSt([π] � [σ]) = cSt(std_{A}[π] � std_{B}[σ])
= cSt(std_{A}[π′] � std_{B}[σ])
= cSt(std_{A′}[π′] � std_{B′}[σ])
= cSt(std_{A′}[π′] � std_{B′}[σ′])
= cSt([π′] � [σ′])

which is what we wished to prove. □

In order to prove the Lifting Lemma, we will need to define two functions. For i ∈ [n] we construct the splitting map S_{i} : C[n] → L[n] as follows. If [π] ∈ C[n] then let S_{i}[π] be the unique linear permutation in [π] which starts with i. For example,

S_{3}[45132] = 32451.

Also define the maximum removal map M : C[n] → L[n − 1] by first applying S_{n} to [π] and then removing the initial n. To illustrate

M[45132] = 1324.

Note that M is a bijection. We similarly define M : C([n] + m) → L([n − 1] + m) using m + n in place of n, as in

M[67354] = 3546.

Finally, we say that y is between x and z in [π] if this is true of any linear permutation in [π] where x occurs to the left of z. If [π] ∈ C[m], i ∈ [m], and [σ] ∈ C([n] + m) define

[π] �_{i} [σ] = {[τ] ∈ [π] � [σ] | only elements of σ are between m + n and i in [τ]}.

For example,

[12] � [34] = {[1234], [1243], [1324], [1423], [1342], [1432]}

with

[12] �_{1} [34] = {[1234], [1243], [1324]}

and

[12] �_{2} [34] = {[1423], [1342], [1432]}.

Note that [π] � [σ] is the disjoint union of the [π] �_{i} [σ] for i ∈ [m] since we can decompose the full shuffle set by finding the first element i ∈ [m] that one encounters cyclically after m + n.

Lemma 2.3 (Lifting Lemma). Let cSt be a cyclic descent statistic and St be a shuffle compatible linear descent statistic such that the following conditions hold.

(a) For any [τ], [τ′] of the same length

St(M[τ]) = St(M[τ′]) implies cSt[τ] = cSt[τ′].

(b) Given any [π], [π′] ∈ C[m] such that cSt[π] = cSt[π′], there exists a bijection f : [m] → [m] such that for all i and j = f(i)

St(S_{i}[π]) = St(S_{j}[π′]).

Then cSt is cyclic shuffle compatible.

Proof. By Corollary 2.2, it suffices to show that if [π], [π′] are as given in (b) and σ ∈ C([n] + m) then cSt([π] � [σ]) = cSt([π′] � [σ]). The remarks preceding the lemma show that this reduces to proving

cSt([π] �_{i} [σ]) = cSt([π′] �_{j} [σ])  (3)

for all i ∈ [m] and j = f(i).

It follows that St(S_{i}[π]) = St(S_{j}[π′]) by (b). So, since St is shuffle compatible, we have St(S_{i}[π] � σ′) = St(S_{j}[π′] � σ′) where σ′ = M[σ]. Thus there is an St-preserving bijection

θ : S_{i}[π] � σ′ → S_{j}[π′] � σ′.

This gives rise to a map

θ′ : [π] �_{i} [σ] →^{M} S_{i}[π] � σ′ →^{θ} S_{j}[π′] � σ′ →^{M^{−1}} [π′] �_{j} [σ]

Since this is a bijection, to show (3) it suffices to prove that θ′ is cSt-preserving. So take [τ] ∈ [π] �_{i} [σ] and [τ′] = θ′[τ]. Then M[τ′] = θ ∘ M[τ]. Since θ is St preserving, we have St M[τ′] = St M[τ]. But then hypothesis (a) implies that cSt[τ] = cSt[τ′] which is what we wished to prove. □

3. Applications

The hypotheses in the Lifting Lemma may seem strange at first glance. But they can be quite easy to verify, making it a useful tool. We will see four instances of this by proving Theorem 1.2 using its aid.

Theorem 3.1. The statistic cDes is cyclic shuffle compatible.

Proof. We will verify the hypotheses of Lemma 2.3 using St = Des. For (a), suppose that #τ = #τ′ = n and

Des(M[τ]) = Des(M[τ′]).  (4)

Let us assume that τ, τ′ were chosen from their cyclic equivalence class so that τ_{1} = max τ and similarly for τ′. Then M[τ] = τ_{2}τ_{3} … τ_{n}. And by the choice of τ_{1} we see that

Des τ = {1} ⊎ (Des M[τ] + 1).  (5)

Since the same statement holds with τ′ in place of τ and (4) holds, we have Des τ = Des τ′. But Des τ is one set in the multiset cDes[τ], and the others are gotten by adding each i ∈ [n] to all elements of Des τ modulo n. The same being true of cDes[τ′] shows that cDes[τ] = cDes[τ′] as desired.

For (b), we are given [π], [π′] ∈ C[m] with cDes[π] = cDes[π′] and must construct the necessary bijection. From this assumption, we can choose π and π′ such that

cDes π = cDes π′ = A.  (6)

for some set A. Define f : [m] → [m] by f(π_{k}) = π′_{k} for all k ∈ [m]. Let i = π_{k} and j = π′_{k}. To show that Des(S_{i}[π]) = Des(S_{j}[π′]) there are two cases depending on whether k − 1 ∈ A or not, where k − 1 is taken modulo m.

If k − 1 ∉ A then π_{k}, π′_{k} are not the second elements in cyclic descents of their respective permutations. From this and equation (6) it follows that

Des(S_{i}[π]) = A − k + 1 (mod m) = Des(S_{j}[π′]).

If k − 1 ∈ A then the same equalities hold with A replaced by A′ which is A with k − 1 removed. The completes the proof of (b) and of the theorem. □

Theorem 3.2. The statistic cdes is cyclic shuffle compatible.

Proof. We proceed as in the previous proof with St = des. For (a) we assume des(M[τ]) = des(M[τ′]). But from equation (5) we see that des τ = des(M[τ]) − 1 and the same is true for τ′. Combining this with our initial assumption gives des τ = des τ′. But τ, τ′ begin with their largest element so that

cdes[τ] = des τ = des τ′ = cdes[τ′]

which is what we wished to show.

To prove (b), we are given cdes[π] = cdes[π′]. As in the preceding paragraph, choose π, π′ to begin with their largest elements so that cdes[π] = des π and similarly for π′. Since des π = des π′ there is a bijection θ : Des π → Des π′. Extend this map to θ : [m] → [m] by using any bijection between the complements of Des π and Des π′. The proof that θ has the desired property is now similar to that for Des and so is left to the reader. □

Theorem 3.3. The statistic cPk is cyclic shuffle compatible.

Proof. This proof parallels the one for cDes, so we will only mention the highlights. For (a) one sees that Pk τ = Pk M[τ] + 1 since τ_{1} = max τ is not a peak in τ and is removed in M[τ]. But this still implies that Pk τ = Pk τ′ and the rest of this part of the demonstration goes through.

For (b), the map θ is constructed in exactly the same way using A = cPk π = cPk π′. The only difference with the remaining part of the proof is that there are two subcases when k − 1 ∉ A depending on whether k − 2 ∈ A or not. If k − 2 ∈ A then one loses the peak which was at π_{k−2} in S_{i}[π]. On the other hand, the peak set stays the same modulo rotation if k − 2 ∉ A. But since the analogous statements hold for π′, the manipulations in these subcases are as before. □

The proof of the next result is based on the proof of Theorem 3.3 in much the same way that the demonstrations of Theorems 3.1 and 3.2 are related. So the details are left to the reader.

Theorem 3.4. The statistic cpk is cyclic shuffle compatible. □

Lest it appear that cyclic shuffle compatibility follows exactly the same lines as the linear case, let us point out a place where they differ. Define a factor of π to be a subsequence of consecutive elements. A birun of π is a maximal monotone factor. Let bru π be the number of biruns of π. For example, bru 125346 = 3 because of the biruns 125, 53, and 346. It is easy to see [GZ18] that the birun statistic is not linearly shuffle compatible. A cyclic birun of [π] is defined in the obvious manner and denoted cbru[π]. Returning to our example, cbru[125346] = 4 because of the biruns above and 61.

Theorem 3.5. The statistic cbru is cyclic shuffle compatible.

Proof. Clearly cyclic biruns always begin at a cyclic peak and end at a cyclic valley, or vice-versa. So cbru[π] = 2 cpk[π] and the result follows from Theorem 3.4. □

4. Remarks and an open question

4.1. Cyclic pattern avoidance and statistics. We say that [σ] ∈ C[n] contains the pattern [π] ∈ C[m] if there is some subsequence [σ′] of [σ] such that std[σ′] = [π]. Otherwise [σ] avoids [π]. For any set [Π] of cyclic permutations we let

Av_{n}[Π] = {[σ] ∈ C[n] | [σ] avoids [π] for all [π] ∈ [Π]}.

Callan calculated # Av_{n}[Π] when [Π] consists of a single element of C[4]. Gray, Lanning, and Wang then contributed work on cyclic packing of patterns [GLW18] and patterns in colored cyclic permutations [GLW19]. Most recently, the authors of this article determined # Av_{n}[Π] for all [Π] ⊆ C[4]. They also calculated the generating function

D_{n}([Π]; q) = ∑_{[σ]∈Av_{n}[Π]} q^{cdes[σ]}.

for the same sets of patterns.

4.2. Cyclic maj? One famous linear statistic which we have not discussed so far is the major index of π which is

maj π = ∑_{i∈Des π} i.

Stanley’s theory of P -partitions [Sta72] shows that if #π = m and #σ = n then

∑_{τ∈π�σ} q^{maj τ} = q^{maj π+maj σ}\left[{m + n \atop m}\right]_{q}

where the last factor is a q binomial coefficient. Note that this is a q-analogue of the fact that #(π � σ) = \binom{m+n}{m}.

It is easy to see that

#([π] � [σ]) = (m + n − 1)\binom{m + n − 2}{m − 1}.  (7)

Indeed, write each [τ] in the shuffle so that it starts with π_{1}. Then there are m + n − 1 more slots to be filled and m − 1 of them must be for the elements π_{2}π_{3} … π_{m} in that order. The remaining slots can be filled with any of the n rotations of σ for a total of n\binom{m+n−1}{m−1} choices. This is equivalent to the formula above. In [AGRR20] the following question was raised.

Question 4.1. Is there a cyclic analogue of maj which has nice properties such as giving a q-analogue of equation (7)?

More generally, one could try to find shuffle compatible cyclic analogues of other linear statistics.

References

[AGRR20] Ron M. Adin, Ira M. Gessel, Victor Reiner, and Yuval Roichman. Cyclic quasi-symmetric functions. Israel J. Math., 243(1):437–500, 2021.

[BJS20] Duff Baker-Jarvis and Bruce E. Sagan. Bijective proofs of shuffle compatibility results. Adv. Appl. Math., 113:101973, 29, 2020.

[Cal] David Callan. Pattern avoidance in circular permutations. See preprint at arXiv:0210014. [DLM^{+}] Rachel Domagalski, Jinting Liang, Quinn Minnich, Bruce Sagan, Jamie Schmidt, and Alexander

Sietsema. Cyclic pattern containment and avoidance. See preprint at arXiv:2106.02534.

[GLW18] Daniel Gray, Charles Lanning, and Hua Wang. Pattern containment in circular permutations. Integers, 18B:Paper No. A4, 13, 2018.

[GLW19] Daniel Gray, Charles Lanning, and Hua Wang. Patterns in colored circular permutations. Involve, 12(1):157–169, 2019.

[Gri18] Darij Grinberg. Shuffle-compatible permutation statistics II: the exterior peak set. Electron. J. Combin., 25(4):Paper No. 4.17, 61, 2018.

[GZ18] Ira M. Gessel and Yan Zhuang. Shuffle-compatible permutation statistics. Adv. Math., 332:85– 141, 2018.

[LMvW13] Kurt Luoto, Stefan Mykytiuk, and Stephanie van Willigenburg. An introduction to quasisymmetric Schur functions, Hopf algebras, quasisymmetric functions, and Young composition tableaux. SpringerBriefs in Mathematics. Springer, New York, 2013.

[Oğu] Ezgi Kantarcı Oğuz. A counter example to the shuffle compatibility conjecture. Preprint

          arXiv:1807.01398.

[Sag20] Bruce E. Sagan. Combinatorics: The art of counting, volume 210 of Graduate Studies in Mathematics. American Mathematical Society, Providence, R.I., 2020.

[Sta72] Richard P. Stanley. Ordered structures and partitions. Memoirs of the American Mathematical Society, No. 119. American Mathematical Society, Providence, R.I., 1972.

[Sta99] Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.