# Descents of $\lambda$-unimodal cyclic permutations

Kassie Archer

Department of Mathematics, Dartmouth College, Hanover, NH 03755, USA

**Abstract.** We prove an identity conjectured by Adin and Roichman involving the descent set of $\lambda$-unimodal cyclic permutations. These permutations appear in the character formulas for certain representations of the symmetric group and these formulas are usually proven algebraically. Here, we give a combinatorial proof for one such formula and discuss the consequences for the distribution of the descent set on cyclic permutations.

**Résumé.** Nous prouvons une identité conjecturée par Adin et Roichman impliquant les ensembles des descentes des permutations cycliques $\lambda$-unimodales. Ces permutations apparaissent dans les formules des caractères pour certaines représentations du groupe symétrique, et ces formules sont généralement prouvées dans une manière algébrique. Ici, nous donnons une preuve combinatoire pour une telle formule et discutons les conséquences pour la distribution de l'ensemble des descentes sur des permutations cycliques.

**Keywords:** cyclic permutation; descent; necklaces; characters of representations of the symmetric group.

## 1 Introduction

Given a composition $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ of $n$, we say a permutation is $\lambda$-unimodal if it is the concatenation of unimodal segments of length $\lambda_i$. These permutations and their descent sets appear in the formulas for certain characters of representations of the symmetric group [3, 6, 8]. These formulas are of the same form found in Theorem 1.1, where the sum occurs over $\lambda$-unimodal permutations with some extra property which varies based on the character. Known formulas for characters include sums over $\lambda$-unimodal permutations which are involutions, are in some given Knuth class, or have a given Coxeter length [3].

We prove a formula of this type originally conjectured by Ron Adin and Yuval Roichman [10]. Consider the one-dimensional representation $\psi$ on $H = \langle (123 \cdots n) \rangle$ obtained by letting $\psi(g^i) = \zeta_n^i$ where $g$ is a generator of $H$ and $\zeta_n$ is an $n$th root of unity. Denote by $\rho$ the representation on $S_n$ induced from the representation on $H \le S_n$ described above and by $\chi$ the character of the representation $\rho$. Let $\chi_\lambda$ be its value on the conjugacy class of type $\lambda$. Denote by $S(\lambda)$ the set of partial sums $\{\lambda_1, \lambda_1 + \lambda_2, \dots, \lambda_1 + \dots + \lambda_k\}$ and by $C(\lambda)$ the set of $\lambda$-unimodal cyclic permutations. Theorem 1.1, which we will prove in Section 5, is the main result of this paper.

**Theorem 1.1** For every composition $\lambda$,

$$ \chi_{\lambda} = \sum_{\pi \in C(\lambda)} (-1)^{|\text{Des}(\pi) \setminus S(\lambda)|}. \qquad (1) $$
Previously, these types of character formulas have been proven algebraically [1, 2, 9]. Here, we prove Theorem 1.1 using combinatorial methods by explicitly computing both sides of Equation 1.

In Section 2, we will see that Theorem 1.1 implies interesting results about the distribution of the descent set on $C_n$. For example, the descent sets of elements of $C_n$ are equi-distributed with the descent sets of the standard Young tableaux which form a basis for the representation described above. Additionally, the number of permutations of $S_{n-1}$ with descent set $D$ is equal to the number of permutations of $C_n$ whose descent set is either $D$ or $D \cup \{n-1\}$. Different proofs of these consequences can alternatively be found in [8] and [5], respectively.

In Sections 3 and 4, we introduce the ideas needed for the proof of Theorem 1.1 and in Section 5, we prove the theorem using a relationship between $\lambda$-unimodal permutations and primitive words developed in [4]. The main idea of the proof is to rewrite the right-hand sum over permutations in Equation 1 as a sum over necklaces and use combinatorial arguments to simplify the sum to show that it equals $\chi_\lambda$, as computed in Proposition 2.1.

## 1.1 Definitions and notation

Let $S_n$ denote the set of permutations on $[n]$. We write permutations in their one-line notation as $\pi = \pi_1\pi_2\cdots\pi_n$. A cyclic permutation is a permutation which is composed of a single $n$-cycle, when written in cycle notation. We denote the set of cyclic permutations of size $n$ by $C_n$. We say a sequence $x_1, x_2, \dots, x_n$ is *unimodal* if there is some $m$, with $1 \le m \le n$, for which

$$x_1 < x_2 < \cdots < x_m > x_{m+1} > \cdots > x_n.$$

That is, the sequence is increasing, then decreasing. For example, the sequence 367841 is unimodal.

A composition of $n$ is a sequence $\lambda = (\lambda_1, \lambda_2, \dots, \lambda_k)$ so that $\lambda_1 + \lambda_2 + \cdots + \lambda_k = n$. For the remainder of the paper, we will assume that $\lambda$ is a composition of $n$ of length $k$. We say a permutation $\pi \in S_n$ is $\lambda$-unimodal if when one breaks $\pi$ into contiguous segments of lengths $\lambda_i$, each segment is unimodal. That is, letting partial sums of $\lambda$ by $s_i(\lambda) = \lambda_1 + \lambda_2 + \cdots + \lambda_i$, the segment $\pi_{s_{i-1}(\lambda)+1} \cdots \pi_{s_i(\lambda)}$ of $\pi$ is unimodal for all $1 \le i \le k$. For example, the permutation 367841295 is (6, 3)-unimodal since 367841 and 295 are unimodal segments of lengths 6 and 3, respectively. We will let $\mathcal{U}(\lambda)$ denote the set of $\lambda$-unimodal permutations and $\mathcal{C}(\lambda)$ denote the set of $\lambda$-unimodal cycles.

# 2 Distribution of the descent set on $C_n$

In this section, we prove some consequences of Theorem 1.1 using representation theory. We first compute that the character of $\rho$ denoted by $\chi$ on each conjugacy class of cycle type $\lambda$ of $S_n$.

**Proposition 2.1** *Recall that $\chi_\lambda$ denotes the value of $\chi$ on conjugacy class $\lambda$. For any conjugacy class $\lambda$,*

$$\chi_{\lambda} = \begin{cases} (k-1)!d^{k-1}\mu(d) & \text{if } \lambda = (d^k) \\ 0 & \text{otherwise.} \end{cases} \qquad (2)$$

The proof of Proposition 2.1 follows directly from the definition of an induced character.

We will show that Theorem 1.1 implies that the descent sets of elements of $C_n$ are equi-distributed with the descent sets of the standard Young tableaux which form a basis to the representation $\rho$. That is to say, for any given $D \subseteq [n-1]$,

$$|\{\pi \in C_n : \mathrm{Des}(\pi) = D\}| = |\{T \in \mathcal{B}_{\rho} : \mathrm{Des}(T) = D\}|$$
where $\mathcal{B}_{\rho}$ is the basis of representation $\rho$ and the descent set of a given standard Young tableau $T$ is defined to be $\text{Des}(T) = \{1 \le i \le n-1 : i+1$ lies strictly south of $i\}$.

To prove this, we must first introduce a few definitions from [3]. We say that a subset $D \subseteq [n-1]$ is $\lambda$-unimodal if $D \setminus S(\lambda)$ is the disjoint union of intervals of the form $[s_{t-1}(\lambda) + \ell_t, s_t(\lambda) - 1]$ where $1 \le \ell_t \le \lambda_t$ for all $1 \le t \le k$. Note that a permutation $\pi \in S_n$ is $\lambda$-unimodal if and only if its descent set $D$ is $\lambda$-unimodal.

Consider a given set of combinatorial objects, $\mathcal{B}$, and descent map $\text{Des} : \mathcal{B} \to \mathcal{P}([n-1])$ which sends each element $b \in \mathcal{B}$ to a subset $\text{Des}(b) \subseteq [n-1]$. If $\rho'$ is some complex representation of $S_n$, then we call $\mathcal{B}$ a fine set for $\rho'$ if the character of $\rho'$ satisfies:

$$ \chi_{\lambda}^{\rho'} = \sum_{b \in \mathcal{B}^{\lambda}} (-1)^{|\text{Des}(b) \setminus S(\lambda)|} $$

where $\mathcal{B}^{\lambda}$ are the elements of $\mathcal{B}$ whose descent set is $\lambda$-unimodal. For example, Theorem 1.1 proves that $C_n$ is a fine set for the representation $\rho$. The following two propositions from [3] will be useful.

**Proposition 2.2** ([3, Cor. 6.7]) If sets $\mathcal{B}_1$ and $\mathcal{B}_2$ are both fine sets for the same representation, then their descent sets are equi-distributed.

**Proposition 2.3** ([3, Thm 2.1]) Any Knuth class $C$ of shape $\nu$ is a fine set for the irreducible representation $S^{\nu}$ of $S_n$.

Here, a Knuth class is a set of permutations which result in the same insertion tableau when performing the Robinson–Schensted–Knuth (RSK) algorithm. For reference, see [13].

Denote by $B_{\rho}$ the set (or possibly, multiset) of standard Young tableaux which form a basis to the representation $\rho$. Recall that any representation of $S_n$ can be written as the direct sum of some irreducible representations $S^{\nu}$ (possibly with multiplicity); that is,

$$ \rho = \bigoplus_{\nu \in V} S^{\nu}. $$

Then the basis of $\rho$ is then defined to be all tableaux $B_{\rho} = \{T \in \text{SYT}(\nu) : \nu \in V\}$ with multiplicities. In the next proposition, we prove that $B_{\rho}$ is a fine set. This also follows immediately from [3, Prop. 6.13].

**Proposition 2.4** $B_{\rho}$ is a fine set.

**Proof:** Suppose $\chi^{\nu}$ is the $S_n$-character of the irreducible representation $S^{\nu}$. By Proposition 2.3, we have

$$ \chi_{\lambda}^{\nu} = \sum_{\pi \in C \cap U(\lambda)} (-1)^{|\text{Des}(\pi) \setminus S(\lambda)|} $$

where $C$ is any Knuth class of shape $\nu$. In performing RSK, the descent set of the permutations is the same as the descent set of the recording tableau $Q$ (see [12]). Therefore, we can rewrite this sum over $\lambda$-unimodal permutations in a given Knuth class as a sum over all tableaux $Q$ of shape $\nu$ whose descent set is $\lambda$-unimodal.

$$ \chi_{\lambda}^{\nu} = \sum_{Q \in \text{SYT}(\nu) \cap \mathcal{T}(\lambda)} (-1)^{|\text{Des}(Q) \setminus S(\lambda)|} $$
where $\mathcal{T}(\lambda)$ is the set of tableaux whose descent set is $\lambda$-unimodal and SYT($\nu$) is the set of standard Young tableaux of shape $\nu$.

Finally, any representation of $S_n$ can be written as the direct sum of some irreducible representations $S^\nu$ and the character of the representation is the sum of the irreducible characters for the representations that appear in this direct sum. Therefore, the proposition follows. $\square$

**Theorem 2.5** The descent sets of elements of $C_n$ are equi-distributed with the descent sets of the standard Young tableaux which form a basis to the representation $\rho$.

**Proof:** By Theorem 1.1, $C_n$ is a fine set for the representation $\rho$. By Proposition 2.4, the set of standard Young tableaux which form a basis of the representation $\rho$ is also a fine set for $\rho$. Therefore, the theorem follows from Proposition 2.2. $\square$

It should be noted that this statement of equi-distribution of descent sets in Theorem 2.5 is a special case of Theroem 2.2 in [8], which itself is a reformulation of Theorem 2.1 in [7].

As another consequence of Theorem 1.1, we recover Theorem 2.8, a result of Elizalde [5] stating that the number of permutations of $S_{n-1}$ with descent set $D$ is equal to the number of permutations of $C_n$ whose descent set is either $D$ or $D \cup [n-1]$. In [5], this is proved directly with a bijection. In the proof of Theorem 2.8, we show that the result also follows from Theorem 1.1 and Propositions 2.6 and 2.7.

**Proposition 2.6** The restriction of $\rho$ to $S_{n-1}$ is isomorphic to the regular representation.

**Proof:** The primitive linear representation $\rho$ of $H$ acts on $\mathbb{C}v$ by $(12...n) \cdot v \mapsto e^{2\pi i/n}v$. Since $H$ is cyclic, this determines the action. The induced representation $\rho'$ on $S_n$ is then an action on $\mathbb{C}\{\sigma_i v\}$ where the $\sigma_i$ are all representatives from the distinct cosets of $H \le S_n$. For a given element $\pi \in S_n$ and coset representative $\sigma_i$, there must be some $\tau \in H$ and $j$ so that $\pi\sigma_i = \sigma_j\tau$. The action of the representation is that $\pi \in S_n$ acts on basis element $\sigma_i v$ by

$$ \pi \cdot \sigma_i v = \sigma_j \rho(\tau) v. $$

We can take the coset representatives $\sigma_i$ to be the elements of $S_n$ which fix $n$. There are exactly $(n-1)!$ such permutations and $\{\sigma_i H\}$ are all distinct cosets, since $\sigma_i^{-1}\sigma_j$ fixes $n$ and therefore can be in $H$ only if it is the identity element. Notice that these coset representatives form a subgroup isomorphic to $S_{n-1}$.

If we take the restriction of $\rho'$ to $S_{n-1}$, we act on $\mathbb{C}\{\sigma_i v\}$ by the elements of $S_{n-1}$, which are exactly the coset representatives. We have that $\sigma_j \cdot \sigma_i v = \sigma_k v$ for some $k$, since $\tau$ is the identity and thus $\rho(\tau) = 1$. If we set $v = 1$, this action is exactly the action by left multiplication on $\mathbb{C}S_{n-1}$, which is the regular representation. $\square$

**Proposition 2.7** $S_n$ is a fine set for the regular representation on $S_n$.

**Proof:** It is well-known (for example, see [11]) that the character of the regular representation $\chi^R$ of $S_n$ takes values $\chi^R(\pi) = n!$ when $\pi$ is the identity and $\chi^R(\pi) = 0$ otherwise. Therefore, from the definition of a fine set, it suffices to show that

$$ \sum_{\pi \in \mathcal{U}(\lambda)} (-1)^{|\mathrm{Des}(\pi) \setminus S(\lambda)|} = \begin{cases} n! & \lambda = (1^n) \\ 0 & \text{otherwise.} \end{cases} \qquad (3) $$
If $\lambda = 1^n$, then every permutation is $\lambda$-unimodal and each one contributes 1 to the sum since $|\text{Des}(\pi) \setminus S(\lambda)| = |\text{Des}(\pi) \setminus [n-1]| = 0$. Therefore, when $\lambda = (1^n)$, the sum is indeed $n!$.

Now, suppose $\lambda \neq (1^n)$. Consider the following map $\varphi : \mathcal{U}(\lambda) \to \mathcal{U}(\lambda)$. Take $i \ge 1$ to be the smallest positive integer such that $\lambda_i > 1$. Then $\pi_{s_i(\lambda)+1} \dots \pi_{s_{i+1}(\lambda)}$ is a unimodal segment of length $\lambda_i > 1$. By switching the positions of the largest and second largest elements of this segment, we obtain a unimodal segment with either one more or one less descent. Let $\varphi(\pi)$ be the permutation you obtain by making this change. Then $\varphi$ is an involution on $\mathcal{U}(\lambda)$ which changes $|\text{Des}(\pi) \setminus S(\lambda)|$ by one. Therefore, there must be a bijection between $\lambda$-unimodal permutations with $|\text{Des}(\pi) \setminus S(\lambda)|$ odd and those with $|\text{Des}(\pi) \setminus S(\lambda)|$ even. It follows that the sum must be 0 in this case. $\square$

**Theorem 2.8** ([5]) The number of permutations in $S_{n-1}$ with descent set $D$ is equal to the number of permutations in $C_n$ whose descent set is either $D$ or $D \cup \{n-1\}$.

**Proof:** By Proposition 2.7, we know that $S_{n-1}$ a fine set for the regular representation of $S_{n-1}$. Denote the restriction of the character $\chi$ to $S_{n-1}$ by $\chi^r$. Consider the injection $\iota : S_{n-1} \to S_n$ sending $\tau \in S_{n-1}$ to $\pi \in S_n$ defined by $\pi(i) = \tau(i)$ for $1 \le i \le n-1$ and $\pi(n) = n$. This allows us to think of $S_{n-1}$ as a subgroup of $S_n$. We have $\chi^r(\tau) = \chi(\tau)$ for $\tau \in S_{n-1} \le S_n$. Recall that by Theorem 1.1,

$$ \chi_{\lambda} = \sum_{\pi \in C(\lambda)} (-1)^{|\text{Des}(\pi) \setminus S(\lambda)|} $$

Suppose $\lambda^r$ is a composition of $n-1$ and $\lambda = (\lambda_1^r, \lambda_2^r, \dots, \lambda_{k-1}^r, 1)$. Additionally, for $\pi \in S_n$, let $\text{Des}^r(\pi)$ denote the $r$-descent set defined to be $\text{Des}(\pi) \setminus \{n-1\}$. Then any element of $C(\lambda)$ is $\lambda^r$-unimodal with respect to $\text{Des}^r$, that is to say, the $r$-descent set of an element of $C(\lambda)$ is $\lambda^r$-unimodal as a set. It follows that

$$ \chi_{\lambda^r} = \sum_{\pi \in C(\lambda)} (-1)^{|\text{Des}^r(\pi) \setminus S(\lambda^r)|} $$

Therefore, it follows that $C_n$ (equipped with the $r$-descent set) is a fine set for the restricted representation. By Proposition 2.2, it follows that for a given $D \subseteq [n-2]$, the number of permutations in $S_{n-1}$ with descent set $D$ is equal to the number of permutations in $C_n$ with $r$-descent set $D$. The theorem follows. $\square$

# 3 Background

In the next two sections, we introduce the necessary background in necklaces that we will need for the proof of Theorem 1.1.

## 3.1 Words and necklaces

A word of length $n$ on $m$ letters is a sequence $s = s_1 s_2 \dots s_n$ where $s_i \in \{0, 1, \dots, m-1\}$. A necklace of length $n$ on $m$ letters is an equivalence class of words $[s]$ so that $t = t_1 t_2 \dots t_n \sim s = s_1 s_2 \dots s_n$ if and only if $t_1 t_2 \dots t_n = s_1 s_{i+1} \dots s_n s_1 \dots s_{i-1}$ for some $1 \le i \le n$, that is, $t$ is some cyclic rotation of $s$. For example, $1101 \sim 1011 \sim 0111 \sim 1110$. Denote by $W_m(n)$ the set of words of length $n$ on $m$ letters and by $N_m(n)$ the set of necklaces of length $n$ on $m$ letters.

We call a word $s$ (or a necklace $[s]$) primitive if there is no strictly smaller word $q$ so that $s = q^r$ for some $r > 1$, where $q^r$ denotes the concatenation of $q$ with itself $r$ times. We denote the number
of primitive necklaces of length $n$ on $m$ letters by $L_m(n)$. We let $a_t(s) = |\{j \in [n] : s_j = t\}|$, that is the number of copies of $t$ in word $s$ and we let $o(s) = \sum_{\text{odd } t} a_t(s)$, that is the number of odd letters in word $s$. We denote by $L(a_1, a_2, \dots, a_m)$ the size of the set of primitive necklaces $[s]$ so that $a_t(s) = a_t$. The enumeration of this set where $\sum_i a_i = n$ is well-known. Here, we use the notation $(a_1, a_2, \dots, a_m) := \gcd(a_1, a_2, \dots, a_m)$ for convenience.

**Lemma 3.1**

$$L(a_1, a_2, \dots, a_m) = \frac{1}{n} \sum_{\ell|(a_1, a_2, \dots, a_m)} \mu(\ell) \frac{(n/\ell)!}{\binom{a_1}{\ell}! \binom{a_2}{\ell}! \dots \binom{a_m}{\ell}!} \quad (4)$$

Define the set $N_\lambda \subseteq N_{2k}(n)$ to be the set of necklaces $[s]$ such that $a_{2t}(s) + a_{2t+1}(s) = \lambda_{t+1}$ for all $0 \le t \le k-1$ and such that $[s]$ is either primitive or $s = q^2$ for some primitive word $q$ for which $o(q)$ is odd. For example, the word $s = 00121 \in N_{(4,1)}$ since $a_0(s) + a_1(s) = 2+2=4$ and $a_2(s) + a_3(s) = 1+0=1$ and $s$ is primitive. For another example, $t = 0213302133$ is in $N_{(4,6)}$ since $a_0(t) + a_1(t) = 2+2=4$ and $a_2(t) + a_3(t) = 2+4=6$ and also $t = (02133)^2$ where $o(02133) = 3$ and $02133$ is primitive.

Let $N_\lambda^{(m)}$ be the set of elements $[s] \in N_\lambda$ where $o(s) = m$. Denote by $\mathcal{L}(\lambda, m)$ the number of primitive necklaces in $N_\lambda^{(m)}$. We have the following lemmas.

**Lemma 3.2** Let $d = \gcd(\lambda_1, \dots, \lambda_k)$. If $d$ is even, let $\lambda/2 = (\lambda_1/2, \lambda_2/2, \dots, \lambda_k/2)$.

$$|N_{\lambda}^{(m)}| = \begin{cases} \mathcal{L}(\lambda, m) + \mathcal{L}(\lambda/2, m/2) & \text{if } d \text{ is even and } m = 2 \mod 4 \\ \mathcal{L}(\lambda, m) & \text{otherwise.} \end{cases}$$

**Proof:** The elements of $N_\lambda^{(m)}$ which are not primitive are exactly those of the form $[s]$ where $s = q^2$ and $q$ is primitive with $o(q) = m/2$ is odd. Therefore, we must have that $n$ is even and $m = 2 \mod 4$. Additionally, if $n$ is even and $m = 2 \mod 4$, given any word $q$ of length $n/2$ with $a_t(q) = \lambda_{t+1}/2$ and $o(q) = m/2$, we will have $q^2 \in N_\lambda^{(m)}$. $\square$

Notice that by definition, we can write $\mathcal{L}(\lambda, m)$ in the following way:

$$\mathcal{L}(\lambda, m) = \sum_{\substack{\sum_t i_t l = m \\ 0 \le i_t \le \lambda_t}} L(\lambda_1 - i_1, i_1, \dots, \lambda_k - i_k, i_k). \quad (5)$$

The next lemma demonstrates a useful symmetry of $\mathcal{L}(\lambda, m)$.

**Lemma 3.3**

$$\mathcal{L}(\lambda, m) = \mathcal{L}(\lambda, n-m).$$

**Proof:** Given a primitive word $s \in N_\lambda$ with $o(s) = m$, we can construct a primitive word $s' \in N_\lambda$ with $o(s) = n-m$ by letting $s'_i = 2t$ if $s_i = 2t+1$ and letting $s'_i = 2t+1$ if $s_i = 2t$ for all $0 \le t \le k-1$. Doing this switches odd letters with even letters and also ensures $\lambda_{t+1} = a_{2t}(s)+a_{2t+1}(s) = a_{2t}(s')+a_{2t+1}(s')$. $\square$
## 3.2 Patterns of necklaces

In order to prove Theorem 1.1, we define a mapping $\Pi_{\lambda}$ from $N_{\lambda}$ to $\lambda$-unimodal cyclic permutations. The mapping we describe here is a special case of the mapping $\Pi_{\sigma}$ defined in [4].

Define a map $\Sigma: W_{2k}(n) \to W_{2k}(n)$ which takes a word $s_1s_2...s_n$ to word $s_2s_3...s_n s_1$. We will define an ordering on words in $W_{2k}(n)$ denoted by $\prec$. Suppose that $s = s_1s_2...s_n$ and $s' = s'_1s'_2...s'_n$ and that for some $1 \le i \le n$, we have $s_1...s_{i-1} = s'_1...s'_{i-1}$ and $s_i \ne s'_i$. Then we say that $s \prec s'$ if either $o(s_1...s_{i-1})$ is even and $s_i < s'_i$ or if $o(s_1...s_{i-1})$ is odd and $s_i > s'_i$.

We are now prepared to define a mapping $\Pi_{\lambda}: N_{\lambda} \to C(\lambda)$ where $C(\lambda)$ are the $\lambda$-unimodal cyclic permutations. Suppose first that $[s] \in N_{\lambda}$ is primitive. Choose a representative $s \in [s]$. Take $\pi = \pi_1\pi_2...\pi_n \in S_n$ to be the permutation, called the *pattern*, which is in the same relative order as the sequence

$$s, \Sigma(s), \Sigma^2(s), \dots, \Sigma^{n-1}(s)$$

with respect to the ordering $\prec$. Then take $\hat{\pi} = (\pi_1\pi_2...\pi_n)$, the cyclic permutation obtained by sending $\pi_1$ to $\pi_2$, $\pi_2$ to $\pi_3$, etc. Then we say that $\Pi_{\lambda}([s]) = \hat{\pi}$. Notice that the choice of representative $s \in [s]$ does not matter.

If $[s] \in N_{\lambda}$ is not primitive, then $s$ is of the form $q^2$ for primitive $q$ where $o(q)$ is odd. Defining the pattern $\pi$ in this case is a little different since for any representative $s \in [s]$, $\Sigma^i(s) = \Sigma^{\frac{n}{2}+i}(s)$ and so it is not immediately obvious how to associate a permutation of length $n$ to it. However, for a given $s \in [s]$ we can “force” the relation $s \prec \Sigma^{\frac{n}{2}}(s)$. After forcing this inequality, for $1 \le i < \frac{n}{2}$ we must similarly force the relations $\Sigma^i(s) \prec \Sigma^{\frac{n}{2}+i}(s)$ whenever $o(s_1...s_i)$ is even and $\Sigma^i(s) \succ \Sigma^{\frac{n}{2}+i}(s)$ whenever $o(s_1...s_i)$ is odd. Since $o(s_1...s_{\frac{n}{2}})$ is odd, this does define a consistent ordering and we can thus define a permutation $\pi = \pi_1\pi_2...\pi_n$ which is in the same relative order as

$$s, \Sigma(s), \Sigma^2(s), \dots, \Sigma^{n-1}(s)$$

with respect to $\prec$. As before, we take $\hat{\pi} = (\pi_1\pi_2...\pi_n)$ and $\Pi_{\lambda}([s]) = \hat{\pi}$. Again, $\hat{\pi}$ does not depend on the choice of representative $s \in [s]$.

Let us see an example. Suppose $\lambda = (3,6)$ and $s = 321132202$. Then $\pi = 953286417$ and $\hat{\pi} = (953286417) = 782134985$. Notice that $\hat{\pi}$ is $(3,6)$-unimodal since 782 and 134985 are both unimodal.

For an example when $[s]$ is not primitive, consider when $\lambda = (4,4)$ and $s = 02210221$. Notice that $s = (0221)^2$ where $0221$ is primitive and $o(0221) = 1$ is odd. Therefore $[s] \in N_{\lambda}$. In this case, $\pi = 17532864$ and $\hat{\pi} = (17532864) = 78213456$. Notice that $\hat{\pi}$ is $(4,4)$-unimodal since 7821 and 3456 are both unimodal segments.

**Remark 3.4** Notice that the way $\prec$ is defined, we must have that if $s \prec s'$ and $s_1 = s'_1$, then $\Sigma(s) \prec \Sigma(s')$ if $s_1$ is even and $\Sigma(s) \succ \Sigma(s')$ if $s_1$ is odd.

## 3.3 Counting Lemmas

Here, we include a few combinatorial lemmas we will need in the proof of Theorem 1.1.

**Lemma 3.5** Suppose $p$ is a $r$-degree polynomial and that $1 \le r < n$. Then

$$\sum_{i=0}^{n} (-1)^i p(i) \binom{n}{i} = 0.$$
**Lemma 3.6** For $d, k \ge 1$,

$$ \sum_{i=1}^{k} (-1)^{i+k} \binom{di}{k} \binom{k}{i} = d^k. $$

**Lemma 3.7** Suppose $\gamma_1 + \gamma_2 + \dots + \gamma_k = r \ge 1$. Then,

$$ \sum_{\substack{0 \le a_t \le \gamma_t \\ a_1 + \dots + a_k = i}} \frac{(r)!}{(\gamma_1 - a_1)!(a_1)! \dots (\gamma_k - a_k)!(a_k)!} = \frac{(r)!}{\gamma_1! \dots \gamma_k!} \binom{r}{i}. $$

# 4 Relationship between necklaces and $\lambda$-unimodal permutations

The following lemma is a special case of Theorem 2.1 in [4]. For that reason, we provide a sketch of the proof without all of the details.

**Lemma 4.1** For any $[s] \in N_\lambda$, we have $\Pi_\lambda([s]) \in C(\lambda)$. Additionally, the map $\Pi_\lambda : N_\lambda \to C(\lambda)$ is surjective.

**Sketch of Proof:** Suppose $[s] \in N_\lambda$, $\pi$ is the pattern of $s' \in [s]$, and $\hat{\pi} = \Pi_\lambda([s])$. For all $0 \le t \le 2k$, define $e_t = |\{j \in [n] : s'_j < t\}|$. We claim that for any $0 \le t < 2k$, if $e_t < \pi_i < \pi_j \le e_{t+1}$, then $\pi_{i+1} < \pi_{j+1}$ if $t$ is even and $\pi_{i+1} > \pi_{j+1}$ if $t$ is odd, where here we let $\pi_{n+1} := \pi_1$. Indeed, since $\pi_i < \pi_j$, it must be true that $\Sigma^{i-1}(s) \prec \Sigma^{j-1}(t)$. Additionally, since $e_t < \pi_i, \pi_j \le e_{t+1}$, we must have $s_i = s_j = t$. By the above remark, it follows that $\Sigma^i(s) \prec \Sigma^j(s)$ (and thus $\pi_{i+1} < \pi_{j+1}$) if $t$ is even and $\Sigma^i(s) \succ \Sigma^j(s)$ (and thus $\pi_{i+1} > \pi_{j+1}$) if $t$ is odd.

From this, it follows that the segment $\hat{\pi}_{e_{t+1}} \dots \hat{\pi}_{e_{t+1}}$ is increasing if $t$ is even and decreasing if $t$ is odd. For if $e_t < a < b \le e_{t+1}$, we only need to show that $\hat{\pi}_a < \hat{\pi}_b$ if $t$ is even and $\hat{\pi}_a > \hat{\pi}_b$ if $t$ is odd. First, notice that $\hat{\pi}_{\pi_i} = \pi_{i+1}$. Take $i$ and $j$ so that $\pi_i = a$ and $\pi_j = b$. Then $e_t < \pi_i < \pi_j \le e_{t+1}$, and thus $\hat{\pi}_a = \pi_{i+1} < \pi_{j+1} = \hat{\pi}_b$ if $t$ is even and $\hat{\pi}_a = \pi_{i+1} > \pi_{j+1} = \hat{\pi}_b$ if $t$ is odd. Since $e_t = \sum_{r<t} a_r(s)$, it follows that $e_{2t+2} - e_{2t} = a_{2t}(s) + a_{2t+1}(s) = \lambda_{t+1}$. Therefore the segment $\hat{\pi}_{e_{2t+1}} \dots \hat{\pi}_{e_{2t+1}} \hat{\pi}_{e_{2t+1}+1} \dots \hat{\pi}_{e_{2t+2}}$ has length $\lambda_{t+1}$ and is unimodal for all $0 \le t < k$. Therefore $\hat{\pi} \in C(\lambda)$.

To see that the map is surjective let $\hat{\pi} \in C(\lambda)$ be arbitrary and let $\pi = \pi_1 \dots \pi_n$ be such that $\hat{\pi} = (\pi_1 \pi_2 \dots \pi_n)$. Since $\hat{\pi} \in C(\lambda)$, there is some sequence $0 = e_0 \le e_1 \le \dots \le e_{2k} = n$ so that (1) the segment $\hat{\pi}_{e_{t+1}} \dots \hat{\pi}_{e_{t+1}}$ is increasing if $t$ is even and decreasing if $t$ is odd, and (2) $e_{2t+2} - e_{2t} = \lambda_{t+1}$ for all $0 \le t \le k-1$. The word $s = s_1 s_2 \dots s_n$ you obtain by setting $s_i = t$ if $e_t < \pi_i \le e_{t+1}$ is a word in $N_\lambda$ so that $\Pi_\lambda([s]) = \hat{\pi}$. Therefore, the map is surjective. $\square$

**Remark 4.2** It is a nontrivial fact that any choice of $0 = e_0 \le e_1 \le \dots \le e_{2k} = n$ will result in a word in $N_\lambda$.

The next lemma describes the relationship between the number of odd letters in an element of $N_\lambda$ and the number of descents of its image under $\Pi_\lambda$. This will prove useful when we rewrite the sum in Theorem 1.1 as a sum over necklaces.

Recall that $N_\lambda^{(m)}$ denotes the set of elements $[s] \in N_\lambda$ where $o(s) = m$. Let $\Pi_\lambda^{(m)}$ be the map $\Pi_\lambda$ restricted to the set $N_\lambda^{(m)}$. Also, let $C_\lambda(m)$ be the set of $\lambda$-unimodal cycles $\tau$ with $|\mathrm{Des}(\tau) \setminus S(\lambda)| = m$, where $S(\lambda)$ is the set of partial sums of $\lambda$ and let $c_\lambda(m) = |C_\lambda(m)|$.
**Lemma 4.3** Suppose $k \ge 1$ and $1 \le m \le n - 1$. Then the map

$$ \Pi_{\lambda}^{(m)} : N_{\lambda}^{(m)} \to \bigcup_{j=0}^{k} C_{\lambda}(m-j) $$

is surjective. Moreover, for $\tau \in C_{\lambda}(m-j)$, the size of the preimage $(\Pi_{\lambda}^{(m)})^{-1}(\tau)$ is $\binom{k}{j}$.

**Sketch of Proof:** For some $\pi = \pi_1\pi_2\dots\pi_n$, we have $\tau = \hat{\pi}$. We know from Lemma 4.1 that for given $\hat{\pi} \in C(\lambda)$, there is a word $s = s_1s_2\dots s_n \in N_{\lambda}$ so that $\Pi([s]) = \hat{\pi}$. We obtain this word by finding a sequence $0 = e_0 \le e_1 \le \dots \le e_{2k} = n$ so that the segment $\hat{\pi}_{e_{t+1}} \dots \hat{\pi}_{e_{t+1}}$ is increasing if $t$ is even and decreasing if $t$ is odd. However, this sequence is not unique. Certainly, we must have that $e_{2t+2} - e_{2t} = \lambda_{t+1}$ for all $0 \le t \le k-1$ and so $e_{2t}$ is fixed for every $0 \le t \le k$. However, for $e_{2t+1}$, we have exactly two choices for all $0 \le t \le k-1$. This is because the unimodal segment of length $\lambda_t \ne 0$ can be broken up in exactly two ways, where the corner could be included in either the increasing segment or the decreasing segment.

Suppose $\tau = \hat{\pi}$ has exactly $m-j$ descents. Then we must have at least $m-j$ odd letters. For example, in a unimodal permutation 24587631, there are 4 descents and the decreasing segment is either length 4 or 5. Choose $j$ of the $k$ corners to include in the decreasing part of each unimodal segment. This will add exactly $j$ odd letters to the minimum number resulting in exactly $m$ odd letters in a given representative $s \in [s]$. Clearly, there are $\binom{k}{j}$ ways to do this. $\square$

**Corollary 4.4** For $k \ge 1$ and $1 \le m \le n - 1$,

$$ |N_{\lambda}^{(m)}| = \sum_{j=0}^{k} \binom{k}{j} c_{\lambda}(m-j). $$

Using the above relationship, we can use generating functions to find an equation for $c_{\lambda}(m)$ in terms of $|N_{\lambda}^{(m)}|$.

**Lemma 4.5** For $k \ge 1$ and $1 \le m \le n - 1$,

$$ c_{\lambda}(m) = \sum_{j=0}^{m} (-1)^{m-j} \binom{m-j+k-1}{m-j} |N_{\lambda}^{(j)}|. \qquad (6) $$

# 5 Proof of main result

Notice that using Equation (2) and the definition of $c_{\lambda}(m)$, we can rewrite the statement of Theorem 1.1 in the following way:

$$ \sum_{m=0}^{n-k} (-1)^m c_{\lambda}(m) = \begin{cases} (k-1)!d^{k-1}\mu(d) & \text{if } \lambda = (d^k), \\ 0 & \text{otherwise.} \end{cases} \qquad (7) $$

We will prove two cases in the next two theorems, when $d = \gcd(\lambda_1, \lambda_2, \dots, \lambda_c)$ is odd and when $d$ is even. Theorems 5.1 and 5.2 will give us a proof of Equation (7) and thus a proof of Theorem 1.1.
**Theorem 5.1** When $d = \gcd(\lambda_1, \dots, \lambda_k)$ is odd,

$$ \sum_{m=0}^{n-k} (-1)^m c_{\lambda}(m) = \begin{cases} (k-1)! d^{k-1} \mu(d) & \text{if } \lambda = (d^k), \\ 0 & \text{otherwise.} \end{cases} \qquad (8) $$

**Proof:** Using Lemma 4.5, we can expand the left hand side of Equation (8) by plugging in the right hand side of Equation (6) for $c_\lambda(m)$. By Lemma 3.2, we know that when $d$ is odd, $|N_\lambda^{(j)}| = \mathcal{L}(\lambda, j)$. We switch the order of summation which allows us to simplify the equation to a single sum. The binomial identity used here to simplify the equation is easily checked.

$$ \sum_{j=0}^{n-k} \sum_{m=j}^{n-k} (-1)^j \binom{m-j+k-1}{m-j} \mathcal{L}(\lambda, j) = \sum_{j=0}^{n-k} (-1)^j \binom{n-j}{k} \mathcal{L}(\lambda, j) $$

Notice that since Lemma 3.3 implies $\mathcal{L}(\lambda, n-j) = \mathcal{L}(\lambda, j)$, then we can perform a change of variables by setting $j := n-j$ to obtain the following formula. We then expand this formula using Equations (4) and (5).

$$ \sum_{j=k}^{n} (-1)^{n-j} \binom{j}{k} \mathcal{L}(\lambda, j) = \sum_{j=1}^{n} (-1)^{n-j} \binom{j}{k} \sum_{0 \le i_t \le \lambda_t, i_1 + \cdots + i_k = j} \frac{1}{n} \sum_{\ell|(d, i_1, i_2, \cdots, i_k)} \mu(\ell) \frac{(n/\ell)!}{(\frac{\lambda_1 - i_1}{\ell})!(\frac{i_1}{\ell})! \cdots (\frac{\lambda_k - i_k}{\ell})!(\frac{i_k}{\ell})!} $$

Notice that for convenience, we write the sum on the right starting at 1. This does not change the formula since $\binom{j}{k} = 0$ whenever $j < k$. Since $\ell | \gcd(d, i_1, i_2, \cdots, i_k)$, certainly $\ell | d$ and thus $\ell$ must always be odd. Also, for any fixed $\ell$ and for any choice of $i_1, \dots, i_k$, we have that $\ell | i_t$ for $1 \le t \le k$ and thus $\ell | j$. We can rewrite the above formula, now moving the sum over $\ell | d$ to the front. We make the following substitutions for the indices in our equation, letting $i, r, a_t$, and $\gamma_t$ be such that $j = \ell i, n = \ell r, i_t = \ell a_t, \lambda_t = \ell \gamma_t$ for all $1 \le t \le k$. After these substitutions, our resulting formula is the following:

$$ \frac{1}{n} \sum_{\ell|d} \mu(\ell) \sum_{i=1}^{r} (-1)^{\ell r - \ell i} \binom{\ell i}{k} \sum_{a_1 + \cdots + a_k = i} \frac{(r)!}{(\gamma_1 - a_1)!(a_1)! \cdots (\gamma_\ell - a_k)!(a_k)!} $$

We simplify this formula by noticing first that the right-most sum is equal to $\frac{(r)!}{\gamma_1! \cdots \gamma_k!} \binom{r}{i}$ by Lemma 3.7. Also, since $\ell$ is odd, we have $(-1)^{\ell r - \ell i} = (-1)^{i+r}$. We therefore obtain:

$$ \frac{1}{n} \sum_{\ell|d} \mu(\ell) \frac{(r)!}{\gamma_1! \cdots \gamma_k!} \sum_{i=1}^{r} (-1)^{i+r} \binom{\ell i}{k} \binom{r}{i}. $$

Since $\binom{\ell i}{k}$ is a degree $k$ polynomial in $i$, the right-most sum is zero when $r > k$ by Lemma 3.5. When $\frac{n}{\ell} = r \le k$, we have $n \le \ell k$, but $\ell | d$ and in turn $d | \lambda_t$ for all $1 \le t \le k$ where $\lambda_1 + \cdots + \lambda_t = n$. Therefore, we must have that $\ell = d = \lambda_t$ for all $1 \le t \le k$. It follows that if $\lambda \ne (d^k)$, then $\sum_{m=0}^{n-k} c_\lambda(m) = 0$.

If $\lambda = (d^k)$, then by the above argument, we must have that $r = k$ and $\ell = d$. Substituting these values into the formula gives us:

$$ \mu(d) \frac{(k)!}{kd} \sum_{i=1}^{k} (-1)^{i+k} \binom{di}{k} \binom{k}{i}. $$
By Lemma 3.6, we know that $\sum_{i=1}^{k} (-1)^{i+k} \binom{di}{k} \binom{k}{i} = d^k$. Equation (8) follows. $\square$

**Theorem 5.2** When $d = \gcd(\lambda_1, \dots, \lambda_k)$ is even,

$$ \sum_{m=0}^{n-k} (-1)^m c_{\lambda}(m) = \begin{cases} (k-1)! d^{k-1} \mu(d) & \text{if } \lambda = (d^k), \\ 0 & \text{otherwise.} \end{cases} \qquad (9) $$

**Sketch of Proof:** Let $\lambda' = \lambda/2$, the composition of $n/2$ of length $k$ where $\lambda'_i = \lambda_i/2$. We use Lemmas 3.2 and 4.5 to expand Equation (9).

$$ \sum_{m=0}^{n-k} \sum_{j=0}^{m} (-1)^j \binom{m-j+k-1}{m-j} \mathcal{L}(\lambda, j) + \sum_{m=0}^{n-k} \sum_{\substack{0 \le i \le m \\ i \equiv 2 \bmod 4}} \binom{m-i+k-1}{m-i} \mathcal{L}(\lambda', \frac{i}{2}). \quad (10) $$

Notice that the left most sum in Equation (10) looks similar to the formula in the proof of Theorem 5.1. Through the same process as before, we find that the left most sum in Equation (10) can be written as:

$$ \frac{1}{n} \sum_{\ell \mid d} \mu(\ell) \frac{(r)!}{\gamma_1! \cdots \gamma_k!} \sum_{i=1}^{r} (-1)^{\ell i} \binom{\ell i}{k} \binom{r}{i}. $$

From this point, the proof is different than the proof of Theorem 5.1, because $\ell$ could be even. We split the sum into the two cases when $\ell$ is either even or odd and apply Lemma 3.5. To make things simplify easily later, we let $n' = n/2$, $d' = d/2$ and $\ell' = \ell/2$. We only need to consider $\ell'$ odd, since if it were even, $\mu(\ell) = 0$. If $\ell'$ is odd, then we have that $\mu(\ell) = \mu(2)\mu(\ell') = -\mu(\ell')$. Then, after simplifying, the first sum in Equation (10) can be written as:

$$ -\frac{1}{n} \sum_{\substack{\ell' \mid d' \\ \ell' \text{ odd}}} \mu(\ell') \frac{r!}{\gamma_1! \cdots \gamma_k!} \sum_{i=1}^{r} \binom{2\ell'i}{k} \binom{r}{i}. \qquad (11) $$

Next, consider the second sum in equation (10). There are two similar cases: when $n'$ is even and when $n'$ is odd. For this sketch of the proof, we will consider the case when $n'$ is even. Using necessary lemmas, we can simplify and obtain the following formula for the right hand sum of Equation (10):

$$ \frac{1}{n'} \sum_{\substack{\ell \mid d' \\ \ell \text{ odd}}} \mu(\ell) \frac{(r)!}{\gamma_1! \cdots \gamma_k!} \sum_{\substack{0 \le i \le r \\ i \text{ odd}}} \binom{2\ell i}{k} \binom{r}{i}. \qquad (12) $$

Finally, we combine the two summations from Equation (10) which we have found to be equal to Equations (11) and (12). After combining like terms, and appealing to Lemma 3.5, we find that if $\lambda \neq (d^k)$, then the sum $\sum_{m=0}^{n-k} c_{\lambda}(m) = 0$ and that if $\lambda = (d^k)$, we obtain:

$$ -\frac{1}{2kd'} \mu(d')k! \cdot \sum_{i=1}^{k} (-1)^i \binom{2d'i}{k} \binom{ke}{i} = \frac{1}{kd} \mu(d)k! \cdot \sum_{i=1}^{k} (-1)^i \binom{di}{k} \binom{ke}{i}. $$
Recall we are dealing with the case when $n'$ is even and thus $d'$ is odd. Therefore, we must have $k$ even. Therefore, by Lemma 3.6, the rightmost sum is $d^k$. Equation (9) follows. □

A future direction of this work would be to extend these ideas to more than just cyclic permutations. The work in Section 4 can be generalized to multisets of necklaces, which could be useful in proving character formulas similar to Theorem 1.1 for other cycle types. These could lead to interesting results about the distribution of the descent set of permutations with a given cycle type.

## Acknowledgements

The author would like to thank Yuval Roichman, Sergi Elizalde, and Zajj Daugherty for helpful discussions.

## References

[1] R. M. Adin, A. Postnikov, and Y. Roichman. Combinatorial Gelfand models. *J. Algebra* 320 (2008) 1311–1325.

[2] R. M. Adin, A. Postnikov, and Y. Roichman. Hecke algebra actions on polynomial rings. *J. Algebra* 233 (2000) 594–613.

[3] R. M. Adin and Y. Roichman. Matrices, characters and descents. arXiv:1301.1675.

[4] K. Archer and S. Elizalde. Cyclic permutations realized by signed shifts. Submitted. arXiv:1304.7790

[5] S. Elizalde. Descent sets of cyclic permutations. *Adv. in Appl. Math.* 47 (2011), 688–709.

[6] S. Elizalde and Y. Roichman. Arc permutations. *J. Algebraic Combin.*, to appear, DOI 10.1007/s10801-013-0449-6.

[7] I. Gessel and C. Reutenauer, Counting Permutations with Given Cycle Structure and Descent Set. *Journal of Combinatorial Theory*. Series A 64, (1993) 189–215.

[8] Y. Roichman. A note on the number of $k$-roots in $S_n$. arXiv:1307.5504.

[9] Y. Roichman. A recursive rule for Kazhdan-Lusztig characters. *Adv. in Math.* 129 (1997) 24–45.

[10] Y. Roichman. Personal Communication.

[11] B. Sagan. “The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions.” 2nd Ed. Springer-Verlag New York Inc. (2010).

[12] M.P. Schützenberger. Quelques remarques sur une Construction de Schensted. *Mathematica Scan-dinavica* 12 (1963): 117–128.

[13] R. Stanley. “Enumerative Combinatorics,” Vol II. Cambridge University Press (1999).