Hopping from Chebyshev polynomials to permutation statistics
Jordan O. Tirrell Yan Zhuang


Simulating the Klein tunneling of pseudospin-one Maxwell particles with trapped ions
    Shi-Liang Zhu
    December 30, 2023
====================================================================================















We prove various formulas which express exponential generating functions
counting permutations by the peak number, valley number, double ascent
number, and double descent number statistics in terms of the exponential
generating function for Chebyshev polynomials, as well as cyclic analogues
of these formulas for derangements. We give several applications of
these results, including formulas for the (-1)-evaluation of some
of these distributions. Our proofs are combinatorial and 
involve the use of monomino-domino tilings, the modified
Foata–Strehl action (a.k.a. valley-hopping), and a cyclic analogue of this action due to Sun and Wang.




[2]



§ INTRODUCTION


Let π=π_1π_2⋯π_n be a permutation (written in
one-line notation) in 𝔖_n, the set of permutations
of [n]={1,2,…,n}. We say that π_i (where i∈[n-1])
is a descent if π_i>π_i+1, and that π_i
(where 2≤ i≤ n-1) is a peak of π if π_i-1<π_i>π_i+1.
Define (π) to be the number of descents of π and (π)
to be the number of peaks of π. The descent number  and
peak number  are classical permutation statistics whose study
dates back to MacMahon <cit.> and to David and Barton <cit.>,
respectively.

The nth Eulerian polynomial[We note that many works instead define the nth Eulerian polynomial to be
	∑_π∈𝔖_nt^(π)+1.]

    A_n(t)∑_π∈𝔖_nt^(π)

encodes the distribution of the descent number  over 𝔖_n, and the nth peak polynomial  

    P_n^(t)∑_π∈𝔖_nt^(π)

is the analogous polynomial for the peak number . 

It is well-known <cit.> that the
(-1)-evaluation of the Eulerian distribution is given by the formula

    A_n(-1)=
    (-1)^(n-1)/2E_n,    n is odd,
    
    0,    n is even,

where E_n is the nth Euler number defined by 

    ∑_n=0^∞E_nx^n/n!=(x)+tan(x).

(The Euler numbers E_n for odd n are called tangent
numbers, and those for even n are called secant numbers.)
No combinatorial formula for P_n^(-1) is known, although
this sequence does appear on the OEIS <cit.>. The first
several terms of this sequence are given in the following table:



n     1     2     3     4     5     6     7     8     9     10P_n^(-1)     1     2     2     -8     -56     -112     848     9088     25216     -310528


We note that the apparent 6-periodicity of the sequence of signs breaks at n=42. Very recently, Troyka <cit.> argued that there is no k for which the sequence of signs of the P_n^(-1) is k-periodic, which suggests that there is unlikely to be a nice combinatorial interpretation for the P_n^(-1).

The exponential generating functions for A_n(t) and P_n^(t)
have the following well-known expressions:[These exponential generating functions are usually given a constant
term of 1 in the literature, but it is more convenient to define these
without the constant term in this work.]

    A(t;x)∑_n=1^∞A_n(t)x^n/n!=e^(1-t)x-1/1-te^(1-t)x;


    P^(t;x)∑_n=1^∞P_n^(t)x^n/n!=1/√(1-t)(x√(1-t))-1.

The work in this paper was originally inspired by the curious observation
that A(-1;x) and P^(-1;x) can be expressed as the logarithmic
derivative of the exponential generating function of some non-negative
integer sequence. For the Eulerian polynomials, this sequence {f_n}_n≥0
is simply f_n(n+1)2, i.e., the sequence
1,0,1,0,…, whose exponential generating function is given by 

    F(x)1+x^2/2!+x^4/4!+⋯=cosh(x).

For the peak polynomials, this sequence is the sequence of Pell numbers,
which has been widely studied in combinatorics and number theory.
The Pell numbers {g_n}_n≥0 are defined by the recursive
formula g_n 2g_n-1+g_n-2 for n≥2 with initial values
g_0=1 and g_1=0. The first several terms of
this sequence are below:



n     0     1     2     3     4     5     6     7     8     9     10     11     12g_n     1     0     1     2     5     12     29     70     169     408     985     2378     5741



Note that the indexing here is slightly different from the
usual indexing of the Pell numbers (see OEIS <cit.>).
The exponential generating function of {g_n}_n≥0 is given
by 


    G(x)∑_n=0^∞g_nx^n/n!=1/2e^x(2cosh(x√(2))-√(2)sinh(x√(2))).


 The exponential generating functions for the Eulerian
and peak polynomials evaluated at t=-1 can be expressed as the
logarithmic derivative of F(x) and G(x), respectively. That
is:


  (a) A(-1;x)=d/dxF(x)/F(x)

  (b) P^(-1;x)=d/dxG(x)/G(x)



While Theorem <ref> can be proven directly by algebraically
manipulating the generating function formulas for A(t;x), P^(t;x),
F(x), and G(x), one of our goals in this paper is to present
a combinatorially-flavored proof. In Section 2, we define several
other relevant permutation statistics and introduce a key ingredient
of our proof: the modified Foata–Strehl group action (a.k.a. valley-hopping).
In Section 3, we define a two-parameter variant of the Chebyshev polynomials
of the second kind which specialize to both the numbers f_n and
the Pell numbers g_n.
Like the ordinary Chebyshev polynomials of the second kind, our bivariate Chebyshev polynomials have as a combinatorial model monomino-domino tilings of a rectangle, but with slightly different weights. We present a formula (Theorem <ref>)
involving these Chebyshev polynomials for the joint distribution of two statistics: the peak number, and the total number of double
ascents and double descents. We give a combinatorial proof of Theorem
<ref> which involves tilings and valley-hopping, and a special case of this result
implies Theorem <ref> (b). We transform Theorem 3 into similar
results for other permutation statistics, which we then use to prove
Theorem <ref> (a) and to prove that the (-1)-evaluation
of double descent distributions yields the tangent numbers. 

In Section 4, we turn our attention to counting derangements by cyclic
analogues of the permutation statistics studied in Sections 2–3.
Using a variant of valley-hopping due to Sun and Wang <cit.>
for derangements, we prove a cyclic analogue of Theorem <ref>
and use it to derive formulas relating exponential generating
functions counting derangements by cyclic statistics with the exponential generating function for our Chebyshev polynomials. We use this to prove a result
similar to Theorem <ref> for the excedance and cyclic peak
distributions over derangements, and to prove that the (-1)-evaluation
of cyclic double descent distributions over derangements yields
the secant numbers.



§ PERMUTATION STATISTICS AND VALLEY-HOPPING


Given a permutation π=π_1π_2⋯π_n in 𝔖_n,
we say that π_i (where i∈[n]) is:


  * a valley if π_i-1>π_i<π_i+1;

  * a double ascent if π_i-1<π_i<π_i+1;

  * a double descent if π_i-1>π_i>π_i+1;

where we are using the convention π_0=π_n+1=∞.[We note that many works on permutation enumeration do not use these conventions, and simply restrict the possible positions of valleys, double ascents, and double descents to the interval from 2 to n-1. What we call “valleys” are sometimes called “left-right valleys” or “exterior valleys”, what we call “double ascents” are sometimes called “right double ascents”, and what we call “double descents” are sometimes called “left double descents”. (See, e.g., <cit.>.)] Thus,
every letter of a permutation is either a peak, valley, double ascent,
or double descent. Define (π), (π), and (π)
to be the number of valleys, double ascents, and double descents of
π, respectively. We also define (π)(π)+(π)
to be the total number of double ascents and double descents of π.

For a list of statistics _1,_2,…,_m
and corresponding variables t_1,t_2,…,t_m, we define
the polynomials {P_n^(_1,_2,…_m)(t_1,t_2,…,t_m)}_n≥0
by 

    P_n^(_1,_2,…_m)(t_1,t_2,…,t_m)∑_π∈𝔖_nt_1^_1(π)t_2^_2(π)⋯ t_m^_m(π).

and we let 

    P^(_1,_2,…_m)(t_1,t_2,…,t_m;x)∑_n=1^∞P_n^(_1,_2,…_m)(t_1,t_2,…,t_m)x^n/n!

be their exponential generating function.[In the case where we have a single statistic , we write these
simply as P_n^(t) and P^(t;x).] For example, we have 

    P_n^(,)(s,t)=∑_π∈𝔖_ns^(π)t^(π)

and 

    P^(,)(s,t;x)=∑_n=1^∞P_n^(,)(s,t)x^n/n!;

we will consider these on the way to proving Theorem <ref>.
Our proof will make use of a bijection based on a group action on
𝔖_n induced by involutions which toggle between double
ascents and double descents; we will spend the remainder of this section
defining this action and the associated bijection.

For π∈𝔖_n, fix k∈[n]. We may write π=w_1w_2kw_4w_5
where w_2 is the maximal consecutive subword immediately to the
left of k whose letters are all smaller than k, and w_4
is the maximal consecutive subword immediately to the right of k
whose letters are all smaller than k. For example, if π=467125839
and k=5, then π is the concatenation of w_1=467, w_2=12,
k=5, the empty word w_4, and w_5=839.

Define φ_k𝔖_n→𝔖_n
by 

    φ_k(π)=
    w_1w_4kw_2w_5,    k
    π,    k

Equivalently, φ_k(π)=w_1w_4kw_2w_5 if exactly
one of w_2 and w_4 is nonempty, and φ_k(π)=π
otherwise. For any subset S⊆[n], we define φ_S𝔖_n→𝔖_n
by φ_S=∏_k∈ Sφ_k. It is easy to see that
φ_S is an involution, and that for all S,T⊆[n],
the involutions φ_S and φ_T commute with each
other. Hence the involutions {φ_S}_S⊆[n] define
a ℤ_2^n-action on 𝔖_n which is often
called the modified Foata–Strehl action or valley-hopping.
This action is based on a classical group action of Foata and Strehl
<cit.>, was introduced by Shapiro, Woan, and Getu <cit.>, and was later rediscovered by Brändén <cit.>.

Let 𝔖_n denote the set of permutations of
[n] with no double ascents and where each double descent is assigned
one of two colors: red or blue.[To be more precise, Davidson College red or Mount Holyoke College blue.] Then valley-hopping induces a map
Φ from 𝔖_n to 𝔖_n defined
in the following way. Given a permutation π in 𝔖_n,
let R(π) be the set of red double descents in π and let
π̅ be the corresponding permutation of π in 𝔖_n,
that is, the permutation obtained by forgetting the colors on the
double descents. Then let Φ(π)=φ_R(π)(π̅).
For example, if π = 726539841,
then Φ(π)=265379418. (See Figure 1.)






 The map Φ𝔖_n→𝔖_n
is a (,)-preserving bijection.



The inverse Φ^-1 of the map Φ can be described in the
following way. Let (π) be the set of double ascents of π
and (π) the set of double descents of π. If S⊆(π)
and if π has no double ascents, then let π^S be the permutation
in 𝔖_n obtained by coloring the double descents
in S blue and all other double descents red. Given a permutation
π in 𝔖_n, let Φ^-1(π)=(φ_(π)(π))^(π).
Then Φ is a bijection between 𝔖_n and
𝔖_n. The claim that Φ preserves the  and
 statistics follows from the easy fact that valley-hopping
preserves these statistics as well.




§ HOPPING FROM CHEBYSHEV POLYNOMIALS TO PERMUTATION
STATISTICS


The Chebyshev polynomials of the second kind {U_n(t)}_n≥0 are defined by the recurrence U_n(t) 2tU_n-1(t)-U_n-2(t) for n≥ 2 with initial values U_0(t)=1 and U_1(t)=2t. These polynomials are an important sequence of orthogonal polynomials arising in many branches of mathematics; see <cit.> for several notable references.

It will be more convenient for us to use a two-parameter variant {U_n(s,t)}_n≥0 of the Chebyshev polynomials of the second kind. We define U_n(s,t) by the recurrence

    U_n(s,t)=2tU_n-1(s,t)-sU_n-2(s,t)

for n≥2 with initial values U_0(s,t)=1 and U_1(s,t)=2t. The first several of these bivariate Chebyshev polynomials are given in the following table.



	
		n     U_n(s,t)0     11     2t2     4t^2-s3     8t^3-4st
	       
	
		n     U_n(s,t)4     16t^4-12st^2+s^25     32t^5-32st^3+6s^2t6     64t^6-80st^4+24s^2t^2-s^37     128t^7-192st^5+80s^2t^3-8s^3t




Note that these polynomials are related to the usual Chebyshev polynomials of the second kind by the formulas U_n(t)=U_n(1,t) and U_n(s,t)=U_n(s^-1/2t)s^n/2. The numbers f_n=(n+1)2 and the Pell numbers g_n are specializations of the U_n(s,t), as f_n=U_n-2(-1,0) and g_n=U_n-2(-1,1) for all n≥2. From the recurrence (<ref>), it is not hard to see that the ordinary generating function for our U_n(s,t) is given by the formula 

    ∑_n=0^∞U_n(s,t)x^n=1/1-2tx+sx^2,

and that U_n(s,t) counts tilings of a 1× n rectangle with two types of monominoes, each weighted t, and one type of domino, each weighted -s. (The ordinary Chebyshev polynomials of the second kind count the same tilings but with dominoes weighted -1; see <cit.> for an accessible reference.)

An expression for the exponential generating function of the U_n(t) is known (see <cit.>) and together with the formula U_n(s,t)=U_n(s^-1/2t)s^n/2, we obtain 

    ∑_n=0^∞ U_n(s,t)x^n+1/(n+1)!=e^xtsinh(x√(t^2-s))/√(t^2-s).

We will find it more convenient to work with the exponential generating function

    V(s,t;x)∑_n=0^∞U_n(s,t)x^n+2/(n+2)!=x^2/2!+2tx^3/3!+(4t^2-s)x^4/4!+⋯.

Note that

    F(x)=∑_n=0^∞f_nx^n/n!=1+V(-1,0;x)
      and  
    G(x)=∑_n=0^∞g_nx^n/n!=1+V(-1,1;x).

It follows from (<ref>) that V(s,t;x) has the closed-form expression

    V(s,t;x)=1/s(1-cosh(x√(t^2-s))e^tx+te^txsinh(x√(t^2-s))/√(t^2-s)).




 §.§ A Chebyshev formula for the bidistribution (pk, dbl)


We now present our main theorem from this section.

 P^(,)(s,t;x)=∂/∂ xV(s,t;x)/1-sV(s,t;x)


Setting s=-1 and t=1 in Theorem <ref> yields Theorem
<ref> (b). Observe that the numerator in Theorem <ref> appears in Equation (<ref>), and using Equation (<ref>) for the denominator we can obtain the expression 

    P^(,)(s,t;x)=1/√(t^2-s)(x√(t^2-s))-t.


From the combinatorial interpretation of multiplication of exponential
generating functions (see, e.g., <cit.>),
it suffices to show that 

    P_n^(,)(s,t)     =∑_k=0^⌊ (n-1)/2⌋s^k∑_BU_|B_0|-1(s,t)U_|B_1|-2(s,t)⋯ U_|B_k|-2(s,t)

where the second sum is over all ordered set partitions B of [n]
into blocks B_0,B_1,…,B_k such that every block other than B_0 has size at least 2. Thus, the right-hand side
of Equation (<ref>) counts these set partitions together
with:


  * a tiling of an 1×(|B_0|-1) rectangle
with two types of monominoes (colored red and blue), each weighted
t, and one type of domino, each weighted -s;

  * for each 1≤ i≤ k, a tiling of an 1×(|B_i|-2)
rectangle with the same types of shapes and weights as above;

and each block (other than B_0) is given an additional weight
of s. We place an ∞ in the first block, write out each
block in decreasing order, and separate adjacent blocks with a bar,
as in

    ∞>π_1>π_2>⋯>π_|B_0||π_|B_0|+1>⋯>π_|B_0|+|B_1||⋯|π_n-|B_k|+1>⋯>π_n.

Here, we consider the tiling on each block as being a tiling on all
but the first and last elements of the block. Now we define a sign-reversing
involution on these objects in the following way: Find the first pair
of elements (π_i,π_i+1) where there is a domino, or where
π_i and π_i+1 are in separate blocks and π_i>π_i+1.
If (π_i,π_i+1) is covered by a domino, then we remove the
domino and insert a new bar in between π_i and π_i+1,
thus splitting their block into two blocks. If π_i and π_i+1
are in separate blocks and π_i>π_i+1, then we merge the
two blocks and cover (π_i,π_i+1) with a domino. (See Figure
2.) This involution swaps a domino (weighted -s) with an additional
block (weighted s), and after cancellation we are left with those
objects with no dominoes and such that π_i<π_i+1 whenever
π_i and π_i+1 are in separate blocks.



If we treat any one of these remaining objects π=π_1π_2⋯π_n
as a permutation, we see that π has no double ascents and has
each double descent colored either red or blue (depending on the color
of the corresponding monomino). Hence, π belongs to 𝔖_n
and contributes a weight of s^(π)t^(π) to the right-hand
side of Equation (<ref>). The result then follows from applying
the (,)-preserving bijection Φ.




 §.§ A Chebyshev formula for the quadruple distribution (pk,val,dasc,ddes)


We shall now derive from Theorem <ref> an analogous result
for the joint distribution of the four statistics , ,
, and .

 P^(,,,)(s,t,u,v;x)=t∂/∂ xV(st,(u+v)/2;x)/1-stV(st,(u+v)/2;x)


First, observe that (π)=(π)+1 for all permutations π,
and that the reversal r(π)π_nπ_n-1⋯π_1
of a permutation is a (,)-preserving involution on 𝔖_n
that switches double ascents with double descents. Thus, we have

    P_n^(,,,)(s,t,u,v)=tP_n^(,)(st,1/2(u+v))

for all n≥1, which proves the result in light of Theorem <ref>.

Theorem <ref> and the formula (<ref>) for
V(s,t;x) can be used together to derive the closed-form formula

    P^(,,,)(s,t,u,v;x)=2t/α(1/2α x)-u-v

where α=√((u+v)^2-4st). This is equivalent to a classical formula of Carlitz and Scoville <cit.>; see also <cit.>.

The following corollary states several specializations of Theorem <ref>.

  


  (a) A(t;x)=∂/∂ xV(t,(1+t)/2;x)/1-tV(t,(1+t)/2;x)

  (b) P^(t;x)=∂/∂ xV(t,1;x)/1-tV(t,1;x)

  (c) P^(t;x)=∂/∂ xV(1,(1+t)/2;x)/1-V(1,(1+t)/2;x)


Further specializing Corollary <ref> (a)
at t=-1 implies Theorem <ref> (a).

Next we show that the (-1)-evaluation of the double descent distribution
over 𝔖_2n+1 gives the tangent number E_2n+1.

 For all n≥1, we have

    P_n^(-1)=
    E_n,    n is odd,
    
    0,    n is even.

Thus P^(-1;x)=tan(x).


Comparing Theorem <ref> with Corollary <ref> (c), we have P^(-1;x)=P^(,)(1,0;x),
which implies P_n^(-1)=P_n^(,)(1,0) for all
n≥1. Observe that P_n^(,)(1,0) is the number of
permutations in 𝔖_n with no double ascents or double
descents. It is easy to see that there are no such permutations for
even n, and the only such permutations for odd n are alternating
permutations: permutations π=π_1π_2⋯π_n satisfying
π_1<π_2>π_3<π_4>⋯<π_n. It is well known
that there are E_n alternating permutations in 𝔖_n,
and the proof follows.

Similar reasoning can be used to prove the formula (<ref>)
for Eulerian polynomials evaluated at t=-1.



§ COUNTING DERANGEMENTS BY CYCLIC STATISTICS


Recall that a derangement is a permutation with no fixed
points, i.e., a permutation for which π_i≠ i for all i.
Let 𝔇_n be the set of derangements in 𝔖_n.
Our goal in this section is to provide an analogous treatment of the
material from the previous section but for counting derangements with
respect to several “cyclic statistics” that we will define shortly.

When writing permutations in cycle notation, we adopt the convention
of writing each cycle with its largest letter in the first position,
and writing the cycles from left-to-right in increasing order of their
largest letters. (This convention is sometimes called canonical
cycle representation.) For example, the permutation π=649237185
in one-line notation is written as π=(42)(716)(8)(953) in cycle
notation.

Given π=π_1π_2⋯π_n, we say that π_i is:


  * a cyclic peak if i<π_i>π_π_i;

  * a cyclic valley if i>π_i<π_π_i;

  * a cyclic double ascent if i<π_i<π_π_i;

  * a cyclic double descent if i>π_i>π_π_i.

Every letter of a derangement is either a cyclic peak, cyclic valley,
cyclic double ascent, or cyclic double descent. Define (π),
(π), (π), and (π) to be the number
of cyclic peaks, cyclic valleys, cyclic double ascents, and cyclic
double descents of π, respectively. 

These “cyclic statistics” were studied earlier by, e.g., Zeng <cit.>, Shin and
Zeng <cit.>, and Sun and Wang <cit.>.[Chow et al. <cit.> also derived various formulas for counting
permutations by cyclic peaks and cyclic valleys, but their definitions
for these statistics differ from ours in that they do not allow the
first or last letter of a cycle to be a cyclic peak or cyclic valley.] These statistics are also closely related to a classical permutation
statistic, the excedance number. We say that i∈[n] is an excedance
of π if i<π_i and let (π) denote the number of
excedances of π. Then i is an excedance of π if and only
if i is a cyclic valley or cyclic double ascent of π, and
it is well-known that the excedance number  and the descent
number  are equidistributed over 𝔖_n.

Define the map o𝔖_n→𝔖_n,
where the input is a permutation in canonical cycle representation
and the output is a permutation in one-line notation, by erasing the
parentheses. Continuing the example with π=(42)(716)(8)(953),
we have o(π)=427168953. The map o is often called Foata's transformation fondamentale and first appeared in <cit.> (see also <cit.>). It is easy to see that the transformation fondamentale is a
bijection; we can recover the cycles of π by noting the left-to-right
maxima of o(π): given a permutation σ=σ_1 σ_2 ⋯σ_n, we say that σ_i is a left-to-right maximum of σ if σ_j<σ_i
for all 1≤ j<i.  

Our work in this section will rely on a cyclic variant of
valley-hopping introduced in <cit.>. Define θ_k𝔇_n→𝔇_n
by θ_k(π)=o^-1(φ_k(o(π))), where the 0th
letter of o(π) is treated as 0 rather than ∞. Similarly,
for a subset S⊆[n], define θ_S𝔇_n→𝔇_n
by θ_S=∏_k∈ Sθ_k. Then the cyclic
modified Foata–Strehl action (or cyclic valley-hopping)
is the ℤ_2^n-action defined by the involutions θ_S.
It is easy to see that cyclic valley-hopping toggles between cyclic
double ascents and cyclic double descents, but does not change cyclic
peaks or cyclic valleys.

Let 𝔇_n denote the set of derangements of
[n] with no cyclic double ascents and where each cyclic double
descent is assigned one of two colors: red or blue. Then cyclic valley-hopping
induces a map Φ from 𝔇_n
to 𝔇_n defined in the analogous way as the map Φ
from Section 2, but with R(π) being the set of red cyclic double
descents. It then follows from the same reasoning as in the proof
of Lemma <ref> that Φ is a (,)-preserving
bijection, where (π)(π)+(π) is
the total number of cyclic double ascents and cyclic double descents
of π.



 §.§ A cyclic analogue of Theorem 3 for derangements


For permutation statistics _1,_2,…,_m and variables
t_1,t_2,…,t_m, we define the polynomials {D_n^(_1,_2,…_m)(t_1,t_2,…,t_m)}_n≥0
by 

    D_n^(_1,_2,…_m)(t_1,t_2,…,t_m)∑_π∈𝔇_nt_1^_1(π)t_2^_2(π)⋯ t_m^_m(π).

and we let

    D^(_1,_2,…_m)(t_1,t_2,…,t_m;x)1+∑_n=1^∞D_n^(_1,_2,…_m)(t_1,t_2,…,t_m)x^n/n!

be their exponential generating function.[As before, if we have a single statistic , we write these simply
as D_n^(t) and D^(t;x).] 
These encode the distributions of permutation statistics over derangements.

We now present a cyclic analogue of Theorem <ref> for derangements.

 D^(,)(s,t;x)=1/1-sV(s,t;x)



It suffices to show that 

    D_n^(,)(s,t)     =∑_k=0^⌊ n/2⌋s^k∑_BU_|B_1|-2(s,t)⋯ U_|B_k|-2(s,t)

where the second sum is over all ordered set partitions B of [n]
into parts B_1,…,B_k. We interpret the right-hand side
of (<ref>) as in the proof of Theorem <ref> (without the initial block B_0 with an ∞) and
apply the same sign-reversing involution; the objects that remain
after cancellation are of the form 

    c_1>c_2>⋯>c_|B_0|| c_|B_0|+1>c_|B_0|+2>⋯>c_|B_0|+|B_1||⋯| c_n-|B_k|+1>⋯>c_n

with no dominoes and such that c_i<c_i+1 whenever c_i
and c_i+1 are in separate blocks.

Now, rather than treating these remaining objects as permutations
in one-line notation, we want to treat them as permutations in cycle
notation with blocks corresponding to cycles. In doing so, we merge
two adjacent blocks whenever the first element of the second block
in the pair is not larger than all elements from all preceding blocks,
i.e., whenever the element is not a left-to-right maximum of the underlying
permutation written in one-line notation; this guarantees that the
resulting permutations are correctly written in canonical cycle representation and is clearly reversible. 

Moreover, these permutations are derangements because each block has
size at least 2, and they have no cyclic double ascents and have each
cyclic double descent colored either red or blue (depending on the
color of the corresponding monomino). In other words, these permutations
π are precisely the elements of 𝔇_n and
each contributes a weight of s^(π)t^(π) to the
right-hand side of Equation (<ref>). The result then follows
from applying the (,)-preserving bijection Φ.


We extend Theorem <ref> to an analogous result
for the joint distribution of the statistics , , , and  over 𝔇_n.


 D^(,,,)(s,t,u,v;x)=1/1-stV(st,(u+v)/2;x)


First, observe that (π)=(π) for all derangements π.
The cyclic valley-hopping map θ_S, where S is the set
containing all cyclic double ascents and cyclic double descents of
π, is a (,)-preserving involution on 𝔇_n
that switches cyclic double ascents with cyclic double descents. Thus,
we have

    D_n^(,,,)(s,t,u,v)=D_n^(,)(st,1/2(u+v))

for all n≥1, which along with Theorem <ref> proves
the result.


We can use Theorem <ref> and Equation (<ref>) to derive the formula 

    D^(,,,)(s,t,u,v;x)=α e^-1/2(u+v)x/αcosh(1/2α x)-(u+v)sinh(1/2α x)

where α=√((u+v)^2-4st).
Furthermore, given any permutation π, let (π) denote the number of cycles of π and let (π) be the number of fixed points of π. Standard applications of the exponential formula (see <cit.>) yield the identities

    D^(,,,,)(s,t,u,v,w;x)=
    D^(,,,)(s,t,u,v;x)^w

and

    1+P^(,,,,,)(s,t,u,v,w,y;x)=
    e^wyxD^(,,,,)(s,t,u,v,w;x).

Then, combining Equations (<ref>), (<ref>), and (<ref>) yields the following exponential generating function formula for the sextuple distribution (,,,,,) over all permutations:

    1+P^(,,,,,)(s,t,u,v,w,y;x) =(α e^(y-1/2(u+v))x/αcosh(1/2α x)-(u+v)sinh(1/2α x))^w.

An equivalent form of this formula was proven earlier by Zeng <cit.>.



 §.§ Counting derangements by excedances


In the remainder of this section, we examine specializations of Theorem <ref> that give rise to formulas
for individual cyclic statistics, beginning with the excedance number.

The excedance polynomials D_n(t) D_n^(t) have been well-studied; for example, it is known that they have exponential generating function 

    D(t;x)     D^(t;x)=(1-t)e^-x/e^-(1-t)x-t

<cit.> and are γ-positive <cit.>. From Theorem <ref> we obtain the following.

D(t;x)=1/1-tV(t,(1+t)/2;x)


It follows from Corollary <ref> that the exponential generating
function for the excedance polynomials D(t;x) evaluated at t=-1
is the reciprocal of the exponential generating function F(x)=cosh(x)
for the sequence 1,0,1,0,….

D(-1;x)=F(x)^-1


This identity can be used to rederive the classical result due to
Roselle <cit.> that 

    D_n(-1)=
    (-1)^n/2E_n,    n is even,
    
    0,    n is odd.


We note that, from Equation (<ref>), one can show that

    U_n(t,(1+t)/2)=1+t+⋯+t^n

for n≥1. Then, using Equation (<ref>), Corollary <ref> can be obtained as a specialization of a formula of Shareshian and Wachs <cit.> involving Eulerian quasisymmetric functions.



 §.§ Counting derangements by cyclic peaks


Next, we examine the distribution of the cyclic peak number over derangements.


 D^(t;x)=1/1-tV(t,1;x)


By specializing (<ref>) appropriately, we derive the formula

    D^(t;x)=√(1-t)e^-x/√(1-t)cosh(x√(1-t))-sinh(x√(1-t)).

The first several polynomials D_n^(t) are given in the following table.



	
		n     D_n^(t)1     02     t3     2t4     4t+5t^2
	       
	
		n     D_n^(t)5     8t+36t^26     16t+188t^2+61t^37     32t+864t^2+958t^38     64t+3728t^2+9656t^3+1385t^4




Note that the coefficient of t in D_n^(t) seems to be
2^n-2 for all n≥2; this is easy to explain combinatorially.

For all n≥2, the number of derangements in 𝔇_n
with exactly one cyclic peak is 2^n-2.



It is easy to see that every derangement π of [n] with exactly
one cyclic peak has exactly one cycle and can be written in the form

    (c_1c_2⋯ c_kc_k+1⋯ c_n)

where c_1=n is the only cyclic peak of π, the sequence c_2⋯ c_k
is decreasing (with c_k=1), and the sequence c_k+1⋯ c_n
is increasing. Thus, for every letter i between 2 and n-1,
either i belongs to the decreasing sequence or the increasing sequence,
and these n-2 choices completely determine the derangement π.

It follows from Corollary <ref> that the exponential generating
function for the numbers D_n^(-1) is the reciprocal of the exponential generating function G(x) for
the Pell numbers.

D^(-1;x)=G(x)^-1


We do not have a combinatorial interpretation for
the numbers D_n^(-1) themselves. The first several of these
numbers appear in the following table.



n     1     2     3     4     5     6     7     8     9     10D_n^(-1)     0     -1     -2     1     28     111     -126     -4067     -26280     53663





 §.§ Counting derangements by cyclic double descents


Lastly, we study the distribution of the cyclic double descent number
over derangements.


 D^(t;x)=1/1-V(1,(1+t)/2;x)


The exponential generating function formula

    D^(t;x)=β e^-1/2(1+t)x/βcosh(1/2β x)-(1+t)sinh(1/2β x),

where β=√((t+3)(t-1)), can be obtained by specializing
(<ref>). The first several of the polynomials D_n^(t) appear in the following table.



	
		n     D_n^(t)1     02     13     1+t4     6+2t+t^2
	      
	
		n     D_n^(t)5     19+21t+3t^2+t^36     109+98t+53t^2+4t^3+t^47     588+808t+334t^2+118t^3+5t^4+t^58     4033+5766t+3827t^2+952t^3+248t^4+6t^5+t^6




An increasing run of a permutation π is a maximal increasing
consecutive subsequence of π (in one-line notation). For example,
the increasing runs of π=467192685 are 467, 19, 268,
and 5. We call increasing runs of length 1 short runs. The
sequence of constant coefficients of D_n^(t) matches
the OEIS sequence <cit.> for the number of permutations
of [n] with no short runs; this can be verified by comparing the
evaluation D^(0;x) with the exponential generating function
of this OEIS entry, but we give a bijective proof below. 

For the purpose of this proof, let us temporarily modify our convention for cycle notation so that we write each cycle with its smallest letter in the first position, and write the cycles from left-to-right in decreasing order of their smallest letters. For example, whereas we previously wrote π=649237185 as π=(42)(716)(8)(953) in canonical cycle representation, now we write π as π=(8)(395)(24)(167). Let o'𝔖_n→𝔖_n be the map defined by taking a permutation in cycle notation under this new convention and erasing the parentheses, yielding a permutation in one-line notation. This is a bijection; we can recover the cycles of π by noting the left-to-right minima of o(π): given a permutation σ=σ_1 σ_2 ⋯σ_n, we say that σ_i is a left-to-right minimum of σ if σ_j>σ_i
for all 1≤ j<i.


An letter i∈[n] is a fixed point or cyclic double descent of π∈𝔖_n
if and only if i is a short run of o^'(π). 

In particular, this proposition implies that the number of derangements
of [n] with no cyclic double descents is equal to the number of
permutations of [n] with no short runs.

Fix a permutation π∈𝔖_n and a letter i∈ [n]. Let us write o^'(π)=σ_1σ_2⋯σ_n
in one-line notation, and take σ_j=i. By taking as convention
σ_0=∞ and σ_n+1=0, it is easy to see that
σ_j=i is a short run of o^'(π) if and only if
σ_j-1>σ_j>σ_j+1.

We divide into cases. First, suppose that i∈[n] is a fixed point
of π. Then σ_j and σ_j+1
are both left-to-right minima, so σ_j-1>σ_j>σ_j+1.
Now suppose that i∈[n] is a cyclic double descent of π.
Note that the first letter of a cycle (under our current convention)
cannot be a cyclic double descent. If i is neither the first nor
last letter of its cycle in π, then σ_j-1>σ_j>σ_j+1.
Otherwise, if i is the last letter of its cycle in π, then
σ_j-1>σ_j and σ_j+1 is a left-to-right
minimum; thus σ_j-1>σ_j>σ_j+1.
In each case, it follows that σ_j=i is a short run of o^'(π).
Hence, every fixed point and cyclic double descent of π is
a short run of o^'(π); the reverse direction is similar.


Finally, we give a cyclic analogue of Theorem <ref>
for derangements.

	 For all n≥1, we have
	
    D_n^(-1)=
    	E_n,    n is even,
    
    	0,    n is odd.

	Thus D^(-1;x)=(x).


In other words, the (-1)-evaluation of the cyclic double descent
distribution over 𝔇_2n gives the secant number E_2n.

By comparing Theorem <ref> with Corollary <ref>, 
we have D_n^(-1)=D_n^(,)(1,0) for
	all n≥1. Observe that D_n^(,)(1,0) is the number
	of derangements of [n] with no cyclic double ascents or cyclic
	double descents. Because the number of cyclic peaks of any permutation
	is equal to its number of cyclic valleys, it is evident that there
	are no such permutations for odd n, and it is easy to see that
	the map o defined earlier is a bijection between such permutations
	for an even n and reverse-alternating permutations of
	[n]: permutations π=π_1π_2⋯π_n satisfying
	π_1>π_2<π_3>π_4<⋯>π_n. Since there are
	E_n reverse-alternating permutations in 𝔖_n,
	the proof follows.





 §.§ Acknowledgements


We thank an anonymous referee for providing thoughtful comments which improved the presentation of this paper and for pointing us to several key references from the literature on Chebyshev polynomials. We also thank Mohamed Omar and Justin Troyka for helpful discussions relating to this project.






plain


