# On the $r$-derangements of type B

István Mezo  School of Mathematics and Statistics, Nanjing University of
Information Science and Technology, Nanjing, 210044, P. R. China
istvanmezo81@gmailcom ,  Victor H. Moll  Department of Mathematics, Tulane
University, New Orleans, LA 70118<EMAIL_ADDRESS>,  José L. Ramírez
Departamento de Matemáticas, Universidad Nacional de Colombia, Bogotá,
Colombia<EMAIL_ADDRESS>and  Diego Villamizar  Department of
Mathematics, Tulane University, New Orleans, LA 70118<EMAIL_ADDRESS>
###### Abstract.

Extensions of a set partition obtained by imposing bounds on the size of the
parts and the coloring of some of the elements are examined. Combinatorial
properties and the generating functions of some counting sequences associated
with these partitions are established. Connections with Riordan arrays are
presented.

###### Key words and phrases:

signed permutations, $r$-derangements, Riordan arrays, generating functions

###### 1991 Mathematics Subject Classification:

Primary 11B83, Secondary 11B73, 0515

##  1\. Introduction

Consider two sets of $n$ symbols $[n]=\\{1,\,2,\ldots,n\\}$ and
$[\overline{n}]=\\{\overline{1},\,\overline{2},\ldots,\overline{n}\\}$, with
$i\neq\overline{j}$, for any $i,\,j$. Define $X_{n}=[n]\cup[\overline{n}]$.
The symbol $\overline{j}$ is called the colored version of the symbol $j$.
Naturally there are $(2n)!$ permutations of $X_{n}$. Some of these
permutations respect the sign, that is, satisfy
$\sigma(\overline{j})=\overline{\sigma(j)}$. These are called signed
permutations or permutations of type $B$. General information about them and
their relations to Coxeter groups appears in Section $8.1$ of [5].

The number of signed permutations on $[n]$ is $2^{n}n!$, since each one of
them is formed by a permutation of $[n]$ and a choice of sign. An example is

(1.1)
$\pi=\begin{pmatrix}1&2&3&4&\overline{1}&\overline{2}&\overline{3}&\overline{4}\\\
\overline{2}&1&3&\overline{4}&2&\overline{1}&\overline{3}&4\end{pmatrix}.$

Observe that the complete permutation is determined by the values of
$\pi(1),\,\pi(2),\,\pi(3),\,\pi(4)$ and these must be a permutation of $[4]$
with some choices of overlines. The remaining images are determined from the
sign rule. In order to simplify notation, only the first half of the bottom
row in (1.1) is retained and $\pi$ is now written simply (in the so-called
line notation) as

(1.2) $\pi=\overline{2}\,1\,3\,\overline{4}.$

As in the classical case, it is possible to express a signed permutation as a
product of disjoint cycles [6]. The notation for the cycles is explained with
the example. $\pi=\overline{4}6\overline{3}51\overline{2}\,\overline{9}87$. In
order to compute the cycle of $\pi$ containing $1$, start by ignoring the
coloring to produce the cycle $1\rightarrow 4\rightarrow 5$. Now insert the
color back as they appear in the one-line notation for $\pi$. This produces
the cycle $(1\overline{4}5)$. Continuing this process gives the final
expression for $\pi$ as
$(1\overline{4}5)(\overline{2}6)(\overline{3})(7\overline{9})(8)$. A second
example illustrates a point that could lead to confusion. The permutations
considered here have no fixed points, for instance

(1.3) $\pi=\begin{pmatrix}1&2&3&\overline{1}&\overline{2}&\overline{3}\\\
2&1&\overline{3}&\overline{2}&\overline{1}&3\end{pmatrix}.$

The short hand notation for $\pi$ is $1\,2\,\overline{3}$ and its cycle
decomposition, as explained above, is written as $(12)(\overline{3})$. The
interpretation of the last term, $(\overline{3})$, is not that $\overline{3}$
is a fixed point of $\pi$, but that $\pi(3)=\overline{3}$ and (necessarily)
$\pi(\overline{3})=3$.

The goal of the present work is to study a variety of functions for signed
permutations in terms of their cycle structure.

Recall that ${n\brack k}$, the (unsigned) Stirling number of the first kind,
counts the number of permutations of $n$ elements with $k$ disjoint cycles.
The recurrence for ${n\brack k}$ is

(1.4) $\begin{bmatrix}n\\\ k\end{bmatrix}=\begin{bmatrix}n-1\\\
k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\\ k\end{bmatrix},\quad\text{ for
}n>k>1,$

with the initial/boundary conditions $\begin{bmatrix}n\\\ n\end{bmatrix}=1$
and $\begin{bmatrix}n\\\ 1\end{bmatrix}=(n-1)!$ for $n>0$ and naturally
$\begin{bmatrix}n\\\ k\end{bmatrix}=0$ for $n<k$. Other functions include some
restrictions on the length of the cycles. For example, if the cycles are
restricted to have length at least $2$, one obtains the derangement numbers
$d_{n}$, given by

(1.5) $d_{n}=n!\sum_{j=0}^{n}\frac{(-1)^{j}}{j!}.$

They satisfy the recurrence $d_{n}=nd_{n-1}+(-1)^{n}$, with $d_{0}=1$. It
follows from (1.5) that

(1.6) $\lim\limits_{n\rightarrow\infty}\frac{d_{n}}{n!}=\frac{1}{e}.$

Broder [7] introduced the notion of $r$-permutations. For $r\in\mathbb{N}$ an
$r$-permutation of $n+r$ is a permutation where the first $r$ elements, called
special, are in distinct cycles. The number of $r$-permutations of $[n+r]$
into $k+r$ cycles are counted by the $r$-Stirling numbers of the first kind,
denoted by $\begin{bmatrix}n\\\ k\end{bmatrix}_{r}$. An $r$-derangement on
$[n+r]$ is an $r$-permutation without fixed points. Information about these
concepts appears in [18, 22]. These concepts are now extended to signed
permutations.

######  Definition 1.1.

A derangement of type $B$ on $[n]$ is a signed permutation $\sigma$ such that
$\sigma(i)\neq i$ for every $i\in[n]$. The set of all such permutations is
denoted by $\mathcal{D}_{n}^{B}$ and its cardinality by $d_{n}^{B}$.

Chow [9] (see also Assaf [1]) proved that

(1.7) $d_{n}^{B}=n!\sum_{k=0}^{n}\frac{(-1)^{k}2^{n-k}}{k!},$

and the analog of (1.6) is

(1.8)
$\lim\limits_{n\rightarrow\infty}\frac{d_{n}^{B}}{n!\,2^{n}}=\frac{1}{\sqrt{e}}.$

This sequence appears as $A000354$ in OEIS and its first few values (starting
at $n=0$) are

(1.9) $1,\,1,\,5,\,29,\,233,\,2329,\,27949,\,391285,\,\cdots.$

Formula (1.7) is equivalent to

(1.10) $\sum_{n=0}^{\infty}d_{n}^{B}\frac{x^{n}}{n!}=\frac{e^{-x}}{1-2x}.$

The main object of the present work is introduced next.

######  Definition 1.2.

Let $n,\,r\in\mathbb{N}$. A type B $\,\,r$-derangement on the set $[n+r]$ is a
signed permutation on $[n+r]$, without fixed points and with $r$ elements
(called special) restricted to be in distinct cycles. The set of all
$r$-derangements of type $B$ on $[n+r]$ is denoted by $\mathcal{D}_{n,r}^{B}$.
Its cardinality is denoted by $d_{n,r}^{B}$. The case $r=0$ recovers
$d_{n}^{B}$ in Definition 1.1.

The number of elements of $\mathcal{D}_{n,r}^{B}$ with $k+r$ cycles is called
the $r$-Stirling number of type $B$ and is denoted by
$\displaystyle\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq 2,r}^{B}$. Counting
over all possible cycles gives the relation

(1.11) $d_{n,r}^{B}=\sum_{k=0}^{n}\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq
2,r}^{B}.$

######  Example 1.3.

The permutation $\sigma=(1\overline{7}4)(\overline{2})(3\overline{6}5)$ is a
type B$\,r$-derangement for $0\leq r\leq 3$ on the set $[7]$.

######  Note 1.1.

The case $r=0$ has been discussed in [17]. The recurrence

(1.12) $\begin{bmatrix}n+1\\\ k\end{bmatrix}_{\geq
2,0}^{B}=2n\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq
2,0}^{B}+2n\begin{bmatrix}n-1\\\ k-1\end{bmatrix}_{\geq
2,0}^{B}+\begin{bmatrix}n\\\ k-1\end{bmatrix}_{\geq 2,0}^{B},$

with the initial conditions

(1.13) $\begin{bmatrix}n\\\ 0\end{bmatrix}_{\geq
2,0}^{B}=\delta_{n,0}\,\,\text{for}\,\,n>0\,\,\text{ and }\begin{bmatrix}n\\\
k\end{bmatrix}_{\geq 2,0}^{B}=0\text{ for }n,\,k<0,$

is established there.

##  2\. A recurrence for the $r$-Stirling numbers of type $B$

This section presents a recurrence for the $r$-Stirling numbers of type $B$.
The initial condition involve the Lah numbers $L(n,k)$, defined as the number
of ways a set of $n$ elements can be partitioned into $k$ nonempty linearly
ordered subsets [20].

######  Theorem 2.1.

For $n\geq 0$ and $k,\,r\geq 1$ the recursion

$\displaystyle\begin{bmatrix}n+1\\\ k\end{bmatrix}_{\geq 2,r}^{B}$
$\displaystyle=$ $\displaystyle\begin{bmatrix}n\\\ k-1\end{bmatrix}_{\geq
2,r}^{B}+2n!\sum_{j=1}^{n}\frac{2^{j}}{(n-j)!}\begin{bmatrix}n-j\\\
k-1\end{bmatrix}_{\geq 2,r}^{B}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad+4rn!\sum_{j=0}^{n}\frac{(j+1)2^{j}}{(n-j)!}\begin{bmatrix}n-j\\\
k\end{bmatrix}_{\geq 2,r-1}^{B}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}n\\\ k-1\end{bmatrix}_{\geq
2,r}^{B}+4r\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq 2,r-1}^{B}$
$\displaystyle\quad\quad\quad\quad+4n!\sum_{j=1}^{n}\frac{2^{j-1}}{(n-j)!}\left(\begin{bmatrix}n-j\\\
k-1\end{bmatrix}_{\geq 2,r}^{B}+2r(j+1)\begin{bmatrix}n-j\\\
k\end{bmatrix}_{\geq 2,r-1}^{B}\right),$

holds. The initial conditions are given by

$\begin{bmatrix}n\\\ 0\end{bmatrix}_{\geq
2,r}^{B}=2^{n}n!\sum_{j=0}^{r}\binom{r}{j}\binom{n-1}{r-j-1}2^{r-j}\quad\text{
and }\quad\begin{bmatrix}0\\\ 0\end{bmatrix}_{\geq 2,r}^{B}=1.$

###### Proof.

The initial condition is established first. Recall that
$\displaystyle\begin{bmatrix}n\\\ 0\end{bmatrix}_{\geq 2,r}^{B}$ counts the
number of signed permutations of $[n+r]$, with $r$ cycles, without fixed
points and $r$ special elements restricted to be in distinct cycles. Therefore
each cycle contains a single special point and, since there are no fixed
points, the special points appearing in a cycle of length $1$ must be colored.
The next step is to place the $n$ non-special points in the $r$ cycles. Let
$j$ be the number of cycles that receive no new points ($0\leq j\leq r$). Then

(2.1) $\begin{bmatrix}n\\\ 0\end{bmatrix}_{\geq
2,r}^{B}=\sum_{j=0}^{r}\binom{r}{j}\cdot 2^{n+r-j}(r-j)!\,L(n,r-j).$

The binomial coefficient $\binom{r}{j}$ takes into account the choices of
cycles without new points, the factor $(r-j)!$ takes care of the ordering of
the cycles with new points, the Lah number counts the ways to partition the
$n$ non-special points in order to place them in the $r-j$ cycles and finally
the power of $2$ describes whether to color the remaining elements or not. The
form of the initial condition stated above is obtained by using the expression

(2.2)
$L(n,k)=\binom{n}{k}\binom{n-1}{k-1}(n-k)!=\frac{n!}{k!}\binom{n-1}{k-1},$

appearing in [20].

To prove the general case of the recurrence, recall that there are $r+k$
cycles of size at least $2,\,\,r$ containing the special points and $k$
containing no special points. Now consider cases for the image of non-special
element $n+1$ under $\pi$.

Option 1. The element $\overline{n+1}$ is fixed by $\pi$. Recall the warning:
this means that $\pi(n+1)=\overline{n+1}$ and $\pi(\overline{n+1})=n+1$.
Removing the cycle $\\{n+1,\,\overline{n+1}\\}$ leaves $\begin{bmatrix}n\\\
k-1\end{bmatrix}_{\geq 2,r}^{B}$ choices. This gives the first term in the
recurrence.

Option 2. Assume $n+1$ is the image under a signed permutation of an uncolored
symbols. There are two cases to consider:

Case 1: $n+1$ belongs to one the first $r$ cycles. Then the cycle
$\mathfrak{b}$ containing $n+1$ has, in addition to $n+1$, one special element
and $j$ additional ones $(0\leq j\leq n$) from $\\{1,\,2,\,\ldots,n\\}$, for a
total of $j+2$ elements. Since $n+1$ is not colored, there are $2^{j+1}$ ways
to color or not the other elements in $\mathfrak{b}$. The $j+2$ elements of
the cycle $\mathfrak{b}$ can now be permuted cyclically in $(j+1)!$ ways. The
count is now

(2.3) $r\sum_{j=0}^{n}\binom{n}{j}(j+1)!2^{j+1}\begin{bmatrix}n-j\\\
k\end{bmatrix}_{\geq 2,r-1}^{B}.$

In this count, the number of special cycles has been reduced by $1$, since
$n+1$ occupies one of them.

Case 2. If $n+1$ does not belong to one of the special cycles, then the number
in Case 1 becomes

(2.4) $\sum_{j=1}^{n}\binom{n}{j}j!2^{j}\begin{bmatrix}n-j\\\
k-1\end{bmatrix}_{\geq 2,r}^{B}.$

The index $j$ counts the number of additional elements in the cycle containing
$n+1$ and the remaining terms are interpreted as before.

Option 3. Assume $\overline{n+1}$ belongs to one of the cycles. Then the count
is similar as in Option 2. The numbers of cases where $\overline{n+1}$ is in
one of $r$ special cycles is

(2.5) $2r\sum_{j=0}^{n}\binom{n}{j}(j+1)!2^{j}\begin{bmatrix}n-j\\\
k\end{bmatrix}_{\geq 2,r-1}^{B}.$

Otherwise, $\overline{n+1}$ is in a cycle without special points and this
contributes

(2.6) $\sum_{j=0}^{n}\binom{n}{j}j!2^{j}\begin{bmatrix}n-j\\\
k-1\end{bmatrix}_{\geq 2,r}^{B}$

to the count. This completes the proof. ∎

######  Note 2.1.

The recurrence is now used to generate the values of $\begin{bmatrix}n\\\
k\end{bmatrix}_{\geq 2,r}^{B}.$ The matrix below gives the values for $r=3$ in
the range $0\leq n,\,k\leq 6$:

(2.7) $\left[\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq
2,3}^{B}\right]=\left(\begin{array}[]{ccccccc}1&0&0&0&0&0&0\\\
12&1&0&0&0&0&0\\\ 144&28&1&0&0&0&0\\\ 1824&592&48&1&0&0&0\\\
25344&11232&1552&72&1&0&0\\\ 391680&213888&41824&3280&100&1&0\\\
6727680&4267008&1061248&119520&6080&132&1\\\ \end{array}\right).$

######  Note 2.2.

The special value $d_{r,0}=1$ comes directly from the definition. The
recurrence in Theorem 2.1 is now used to check that $d_{1,r}^{B}=1+4r$.
Indeed,

(2.8) $d_{r,1}^{B}=\begin{bmatrix}1\\\ 0\end{bmatrix}_{\geq
2,r}^{B}+\begin{bmatrix}1\\\ 1\end{bmatrix}_{\geq 2,r}^{B},$

and the initial condition in Theorem 2.1 shows that

(2.9) $\begin{bmatrix}1\\\ 0\end{bmatrix}_{\geq 2,r}^{B}=2^{1}\cdot
1!\times\sum_{j=0}^{r-1}\binom{r}{j}\binom{0}{r-j-1}2^{r-j}=4r,$

and the second term in the recurrence yields

(2.10) $\begin{bmatrix}1\\\ 1\end{bmatrix}_{\geq 2,r}^{B}=\begin{bmatrix}0\\\
0\end{bmatrix}_{\geq 2,r}^{B}+4r\begin{bmatrix}0\\\ 1\end{bmatrix}_{\geq
2,r}^{B}+\text{an empty sum}=1,$

for a total of $d_{1,r}^{B}=1+4r$.

##  3\. An approach from the theory of Riordan arrays

This section considers the matrix $\mathcal{C}_{\geq 2,r}:=\left({n\brack
k}_{\geq 2,r}^{B}\right)_{n,k\geq 0}$ as a Riordan array. Enumerative
arguments for some combinatorial identities are presented. The unsigned
entries of the matrix ${\mathcal{C}}^{-1}_{\geq 2,r}$ are discussed first.

Recall that an infinite lower triangular matrix
$L=\left[l_{n,k}\right]_{n,k\geq 0}$ is called an _exponential Riordan array_
[3] if its $k^{th}$-column has generating function of the form
$g(z)\left(f(z)\right)^{k}/k!,k=0,1,2,\ldots g(z)$, where $g(z)$ and $f(z)$
are formal power series with $g(0)\neq 0,\,f(0)=0$ and $f^{\prime}(0)\neq 0$.
The matrix corresponding to the pair $f(z),g(z)$ is denoted by $(g(z),f(z))$.

Multiplying $(g,f)$ by a column vector $(c_{0},c_{1},\dots)^{t}$ with
exponential generating function $h(z)$, results in a column vector with
exponential generating function $g\cdot h\circ f$. This property is known as
the fundamental theorem of exponential Riordan arrays or summation property
[12]. The product of two exponential Riordan arrays $(g(z),f(z))$ and
$(h(z),\ell(z))$ is defined by:

$(g(z),f(z))*(h(z),\ell(z))=\left(g(z)h\left(f(z)\right),\ell\left(f(z)\right)\right).$

The set of all exponential Riordan matrices is a group under this operation
[3], [21]. The identity is $I=(1,z)$ and

(3.1)
$(g(z),f(z))^{-1}=\left(\frac{1}{\left(g\circ\overline{f}\right)(z)},\overline{f}(z)\right),$

here $\overline{f}(z)$ denotes the compositional inverse of $f(z)$; that is,
$(\overline{f}\circ f)(z)=z$.

Deutsch et al. [12] gave an algorithm to calculate the entry $l_{n,k}$ of an
exponential Riordan array. They proved that every element $l_{n+1,k}$ of an
exponential Riordan array can be expressed as a linear combination of the
elements in the preceding row. In particular, for
$L=\left[l_{n,k}\right]_{n,k\geq 0}=(g(z),f(z))$ there are sequences $(a_{n})$
and $(z_{n})$ such that

(3.2) $\displaystyle l_{n+1,0}$ $\displaystyle=\sum_{i\geq 0}i!a_{i}l_{n,i},$
(3.3) $\displaystyle l_{n+1,k}$
$\displaystyle=a_{0}l_{n,k-1}+\frac{1}{k!}\sum_{i\geq
k}i!(z_{i-k}+ka_{i-k+1})l_{n,i},$

where

$A(t)=a_{0}+a_{1}t+a_{2}t^{2}+\cdots,\quad
Z(t)=z_{0}+z_{1}t+z_{2}t^{2}+\cdots$

satisfy the functional relations

(3.4) $\displaystyle A(t)=f^{\prime}(\bar{f}(t)),\quad
Z(t)=\frac{g^{\prime}(\bar{f}(t))}{g(\bar{f}(t))}.$

Conversely, (3.4) implies (3.2) and (3.3).

The next results states that the matrix defined by $\mathcal{C}_{\geq
2,r}:=\left({n\brack k}_{\geq 2,r}^{B}\right)_{n,k\geq 0}$ is an exponential
Riordan array.

######  Theorem 3.1.

The matrix $\mathcal{C}_{\geq 2,r}$ is the exponential Riordan array given by

$\left(\left(\frac{1+2z}{1-2z}\right)^{r},-\ln(1-2z)-z\right).$

###### Proof.

Let $C_{k}(x):=\sum_{n\geq 0}{n+k\brack k}_{\geq 2,r}^{B}\frac{x^{n}}{n!}$ be
the generating function of the columns of the matrix $\mathcal{C}_{\geq 2,r}$.
The initial values in Theorem 2.1 shows that the generating function of the
first column is given by

$\displaystyle C_{0}(x)$ $\displaystyle=\sum_{n\geq
0}2^{n}n!\sum_{j=0}^{r}\binom{r}{j}\binom{n-1}{r-j-1}2^{r-j}\frac{x^{n}}{n!}=\sum_{j=0}^{r}\binom{r}{j}2^{r-j}\sum_{n\geq
0}\binom{n-1}{r-j-1}(2x)^{n}.$

The identity

$\frac{1}{(1-x)^{t}}=\sum_{n\geq 0}\binom{t+n-1}{t-1}x^{n},$

gives

$\left(\frac{2x}{1-2x}\right)^{r-j}=\sum_{n\geq 0}\binom{n-1}{r-j-1}x^{n},$

Therefore

$\displaystyle
C_{0}(x)=\sum_{j=0}^{r}\binom{r}{j}2^{r-j}\left(\frac{2x}{1-2x}\right)^{r-j}=\left(1+\frac{4x}{1-2x}\right)^{r}=\left(\frac{1+2x}{1-2x}\right)^{r}.$

The generating function for the column $C_{1}(x)$ is presented next. The
relation

(3.5) $\displaystyle{n\brack 1}_{\geq
2,r}^{B}=\sum_{k=2}^{n}\binom{n}{k}(k-1)!2^{k}{n-k\brack 0}_{\geq
2,r}^{B}+n{n-1\brack 0}_{\geq 2,r}^{B}.$

follows from the following combinatorial argument. Assume a non-special cycle
has $k$ elements ($2\leq k\leq n$). These can be chosen and colored in
$\binom{n}{k}(k-1)!$ ways. The coloring of these these elements produce
$2^{k}$ options. The remaining elements can be organized in ${n-k\brack
0}_{\geq 2,r}^{B}$ ways. Summing over $k$ gives the first expression in (3.5).
On the other hand, in the case where a non-special block has only one element
gives $n{n-1\brack 0}_{\geq 2,r}^{B}$ options. Therefore

$C_{1}(x)=C_{0}(x)\sum_{n\geq
2}\frac{(2x)^{n}}{n}+xC_{0}(x)=C_{0}(x)(-x-\log(1-2x)).$

Similarly

(3.6) $\displaystyle C_{k}(x)=C_{0}(x)\frac{(-x-\log(1-2x))^{k}}{k!},$

since $C_{0}(x)$ takes into account the $r$ special cycles and
$(-x-\log(1-2x))^{k}/k!$ are sequences of unordered $k$ cycles. The result now
follows from (3.6) and the definition of a Riordan array. ∎

##  4\. Counting distances on graphs

Given a graph $G$ the sequence $S_{G}(n)$ is defined as the number of vertices
which have a distance $n$ from a given vertex in $G$. This sequence was
discussed in [2] and [10]. The example $S_{\mathbb{Z}^{2}}(3)=12$ is pictured
in Figure 1.

Figure 1. Points at a distance 2 from a fixed point.

In the case of the $r$-dimension lattice $\mathbb{Z}^{r}$, it follows that

$\sum_{n\geq 0}S_{\mathbb{Z}^{r}}(n)x^{n}=\left(\frac{1+x}{1-x}\right)^{r}.$

The first column in the Riordan array given in Theorem 3.1 gives the next
statement. A combinatorial proof is presented.

######  Theorem 4.1.

For $r,n\in\mathbb{N}$

(4.1) ${n\brack 0}_{\geq 2,r}^{B}=2^{n}n!S_{\mathbb{Z}^{r}}(n).$

###### Proof.

A permutation $\sigma$ with no non-special elements is written as
$\sigma=c_{1}c_{2}\cdots c_{r},$ where $c_{i}$ are the special cycles
containing one of the $[r]$ elements. Define
$x_{\sigma}=(x_{1},\dots,x_{r})\in\mathbb{Z}^{r}$ by

$x_{i}=\begin{cases}0,&\text{ if }\sigma_{i}=\bar{i};\\\
-(ord(c_{i})-1),&\text{ if }\bar{i}\in c_{i};\\\
ord(c_{i})-1,&\text{otherwise.}\end{cases}$

where $ord(c_{i})$ is the length of the cycle $c_{i}$. It is clear that
$\sum_{i=1}^{r}|x_{i}|=n$, so $x_{\sigma}$ is at distance $n$ from the origin.
This construction does not take into account the sign in the $[n]$ elements.
This can be done in $2^{n}$ ways. Finally, the $n!$ term count the ordering of
position in the cycles. The proposition follows. ∎

Lengyel [15] presented the interesting expression:

$\frac{1+x}{1-x}=\sum_{n=1}^{\infty}x^{\lfloor\frac{n}{\phi}\rfloor}+\sum_{n=1}^{\infty}x^{\lfloor
n\phi^{2}\rfloor},\quad\text{for}\,|x|<1.$

Here $\phi$ is the golden ratio.

The next statement characterizes the two diagonals below the main one.

######  Theorem 4.2.

For $n\geq 0$, the identities

$\displaystyle{n+1\brack n}^{B}_{\geq 2,r}$ $\displaystyle=2(n+1)(n+2r),$
$\displaystyle{n+2\brack n}^{B}_{\geq 2,r}$
$\displaystyle=\frac{4}{3}\binom{n+2}{2}(3n^{2}+n+12nr+12r^{2}),$

hold.

###### Proof.

There are two cases to consider, either

  * •

There is an element that belongs to one of the $r$ special cycles. This
happens in $(n+1)r2^{2}$ ways; or,

  * •

Two elements form a non special cycle. This can be done in
$2^{2}\binom{n+1}{2}$ ways.

The first identity follows from here. The proof of the second identity is
similar. ∎

###  4.1. Combinatorial interpretation of the inverse matrix

The matrix ${\mathcal{C}}_{\geq 2,r}$ is a Riordan array and since the set of
all Riordan matrices is a group, its inverse exists. This subsection presents
a combinatorial interpretation of the unsigned inverse matrix of
${\mathcal{C}}_{\geq 2,r}$ in terms of plane increasing trees. The particular
case $r=0$ was presented in [17]. The notation ${\mathcal{T}}_{\geq
2,r}:=\left[T_{\geq 2,r}(n,k)\right]_{n,k\geq 0}$ is used for the inverse of
${\mathcal{C}}_{\geq 2,r}$. Then (3.1) shows that ${\mathcal{T}}_{\geq 2,r}$
is the exponential Riordan array given by

${\mathcal{T}}_{\geq
2,r}=\left(\left(-1+\frac{1}{1+W\left(-\frac{1}{2}e^{-\frac{1}{2}-z}\right)}\right)^{r},\frac{1}{2}+W\left(-\frac{1}{2}e^{-\frac{1}{2}-z}\right)\right),$

with $W(z)$ is the Lambert $W$ function. This is defined by

(4.2) $W(x)e^{W(x)}=x,$

for all real (or complex) $x$. More information on this function appears in
[11].

Let ${\mathcal{\overline{T}}}_{\geq 2,r}:=\left[\overline{T}_{\geq
2,r}(n,k)\right]_{n,k\geq 0}$ be the unsigned matrix of ${\mathcal{T}}_{\geq
2,r}$, that is

$\displaystyle{\mathcal{\overline{T}}}_{\geq 2,r}:=$
$\displaystyle\left[\overline{T}_{\geq 2,r}(n,k)\right]_{n,k\geq
0}=\left[(-1)^{n+k}T_{\geq 2,r}(n,k)\right]_{n,k\geq 0}$ $\displaystyle=$
$\displaystyle\left(\left(-1+\frac{1}{1+W\left(-\frac{1}{2}e^{-\frac{1}{2}+z}\right)}\right)^{r},-\frac{1}{2}-W\left(-\frac{1}{2}e^{-\frac{1}{2}+z}\right)\right).$

The first few rows of the matrix ${\mathcal{\overline{T}}}_{\geq
2,3}=\left[\overline{T}_{\geq 2,3}(n,k)\right]_{n,k\geq 0}$ are

$\left(\begin{array}[]{cccccccc}1&0&0&0&0&0&0\\\ 12&1&0&0&0&0&0\\\
192&28&1&0&0&0&0\\\ 3936&752&48&1&0&0&0\\\ 99456&22304&1904&72&1&0&0\\\
3001344&748672&76320&3920&100&1&0\\\
105544704&28412416&3265792&203040&7120&132&1\\\ \end{array}\right).$

Now let $\overline{T}_{k}(z)$ be the generating function of the $k^{th}$
column of ${\mathcal{\overline{T}}}_{\geq 2,r}$. Then

$\overline{T}_{0}(z)=\left(-1+\frac{1}{1+W\left(-\frac{1}{2}e^{-\frac{1}{2}+z}\right)}\right)^{r}=\left(F^{\prime}(z)\right)^{r},$

where

(4.3) $F(z):=-\tfrac{1}{2}-W\left(-\tfrac{1}{2}e^{-\frac{1}{2}+z}\right).$

The generating function $F(z)$ counts the total number of labeled rooted trees
of subsets of an $n$-set [16]. In the sequence A005172 of OEIS, Peter Bala
states that $F(z)$ satisfies the functional equation

(4.4) $x=\int_{0}^{F(x)}\frac{1}{\Phi(t)}dt,$

where $\Phi(t)=(1+2t)/(1-2t)$. Then [4, Theorem 1] provides an alternative
combinatorial interpretation for this sequence. It turns out that this
sequence also counts the plane increasing trees on $n$ vertices, such that
each vertex of out-degree $k\geq 1$ is colored with one of $2^{k+1}$ colors.
Therefore $F^{\prime}(z)$, the derivative of $F(z)$, counts plane increasing
trees on $n+1$ vertices.

The power series expansion of $F^{\prime}(z)$ starts as

$F^{\prime}(z)=1+4\frac{z}{1!}+32\frac{z^{2}}{2!}+416\frac{z^{3}}{3!}+7552\frac{z^{4}}{4!}+176128\frac{z^{5}}{5!}+\cdots$

Figure 2 shows the corresponding trees with $3$ vertices. The parenthesis
denotes the possible colorings for a vertex.

Figure 2. Colored plane increasing trees on $3$ vertices.

The identity

(4.5)
$\overline{T}_{k}(z)=\left(F^{\prime}(z)\right)^{r}\frac{1}{k!}\left(F(z)\right)^{k},$

leads to the next result.

######  Theorem 4.3.

The sequence $\overline{T}_{\geq 2,r}(n,k)$ counts the number of $r$-ordered
and $k$-unordered elements in a $r+k$-forest of increasing trees on $n$
vertices, such that each vertex of out-degree $k\geq 1$ is colored with one of
$2^{k+1}$ colors and the $r$ ordered connected components are rooted.

The next recurrence now follows from (3.2) and (3.3).

######  Theorem 4.4.

The sequence $\overline{T}_{\geq 2,r}(n,k)$ for $n\geq k\geq 0$ is determined
by the recurrence

$\overline{T}_{\geq 2,r}(n+1,k)=\overline{T}_{\geq
2,r}(n,k-1)+\frac{1}{k!}\sum_{i=k}^{n}i!2^{i-k+2}((i-k+1)r+k)\overline{T}_{\geq
2,r}(n,i),$

and the initial conditions $\overline{T}_{\geq 2,r}(n,0)=\delta_{n,0}$ for
$n\geq 0$, and $\overline{T}_{\geq 2,r}(n,k)=0$ for $n,k<0$.

##  5\. Properties of the numbers $d_{r,n}^{B}$

This section discusses the expression

(5.1) $d_{r,n}^{B}=\sum_{k=0}^{n}\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq
2,r}^{B},$

for the total number of $r$-derangements of type $B$ on $[n+r]$. This is the
row sum of the matrix in (2.7). The case $r=0$ appears in (1.7).

######  Theorem 5.1.

The recurrence

(5.2) $d_{r,n}^{B}=d_{r-1,n}^{B}+2nd_{r,n-1}^{B}+2nd_{r-1,n-1}^{B},$

holds. It is supplemented by the initial conditions $d_{r,0}^{B}=1$ and
$\displaystyle d_{0,n}^{B}=n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}2^{n-k}.$

###### Proof.

Consider a permutation $\pi$ in $\mathcal{D}_{n,r}^{B}$. There are $r$ special
elements and assume that $1$ is the first of them. The recurrence is obtained
by distinguishing cases according to the type of cycle $\mathfrak{c}$
containing $1$. The initial conditions appeared in Note 1.1.

Case 1. Assume $\mathfrak{c}$ is of length $1$. Then the cycle must be
$(\overline{1})$, since there are no fixed points in $\pi$. The rest of the
permutation is in $\mathcal{D}^{B}_{n,r-1}$, counting for the term
$d_{n,r-1}^{B}$.

Case 2. If $\mathfrak{c}$ is of length $2$, then $\mathfrak{c}$ is of the form
$(1\,x)$ with $x$ non-special. Then $1$ and $x$ can be colored or not, for a
total of $n$ choices. The rest of the permutation is in
$\mathcal{D}^{B}_{n-1,r-1}$, for a total of $4nd_{n-1,r-1}^{B}$ choices.

Case 3. Finally consider the case when the cycle $\mathfrak{c}$ has at least
$3$ elements. To produce such a permutation, choose $k$ to be non-special and
drop it from the list of non-special elements. Then form an arbitrary
$B$-$r$-derangement on $n-1+r$ elements in $d_{n-1,r}^{B}$ ways. After that,
insert $k$ to the right of $1$ and optionally color it. This accounts for
$2nd_{n-1,r}^{B}$ choices. In this process, there are certain permutations
that have been counted twice. Namely, those for which $1$ is in a cycle of
length $1$ for a permutation in $\mathcal{D}_{n-1,r}^{B}$. Inserting $k$ then
produces a cycle of length $2$, already counted in Case 2. Therefore these
must be excluded. Thus, the total count is
$2n\left(d_{n-1,r}^{B}-d_{n-1,r-1}^{B}\right)$.

The proof is complete. ∎

######  Corollary 5.1.

For fixed $n\in\mathbb{N}$, the function $d_{n,r}^{B}$ is a polynomial in $r$
of degree $n$.

###### Proof.

This follows from $d_{r,0}=1$ and (5.2), written in the form

(5.3) $d_{r,n}^{B}-d_{r-1,n}^{B}=2n(d_{r,n-1}^{B}+d_{r-1,n-1}^{B}).$

∎

######  Example 5.2.

The value $d_{r,1}^{B}=1+4r$ and the difference equation (5.3) give

(5.4) $d_{r,2}^{B}-d_{r-1,2}^{B}=4(1+4r+1+4(r-1))=32r-8.$

Therefore $d_{r,2}^{B}$ is a quadratic polynomial in $r$. The ansatz
$d_{r,2}^{B}=a_{0}r^{2}+a_{1}r+a_{2}$ in (5.4) gives $a_{2}=16$ and $a_{1}=8$.
The remaining coefficient comes from (1.7); so that

(5.5) $d_{r,2}^{B}=16r^{2}+8r+5.$

Similarly,

$\displaystyle d_{r,3}^{B}$ $\displaystyle=$ $\displaystyle
64r^{3}+48r^{2}+92r+29,$ $\displaystyle d_{r,4}^{B}$ $\displaystyle=$
$\displaystyle 256r^{4}+256r^{3}+992r^{2}+592r+233,$ $\displaystyle
d_{r,5}^{B}$ $\displaystyle=$ $\displaystyle
1024r^{5}+1280r^{4}+8320r^{3}+7200r^{2}+7796r+2329,$ $\displaystyle
d_{r,6}^{B}$ $\displaystyle=$ $\displaystyle
4096r^{6}+6144r^{5}+60160r^{4}+67840r^{3}+141424r^{2}+83672r+27949.$

An explicit formula for $d_{r,n}^{B}$ is presented next.

######  Theorem 5.3.

For all $n,\,r\geq 0$,

(5.7)
$d_{r,n}^{B}=2^{n}\sum_{i=0}^{r}\binom{r}{i}n^{\underline{i}}2^{i}\sum_{k=0}^{n-i}\binom{n-i}{k}(-1)^{k}(i+1)^{\overline{n-i-k}}2^{-k}.$

Here $n^{\underline{i}}=n(n-1)\cdots(n-i+1)$ and
$n^{\overline{j}}=n(n+1)\cdots(n+j-1)$.

###### Proof.

We consider cases with $r-i$ special elements ($0\leq i\leq r$) are in cycles
of length one (and therefore necessarily barred). The other $i$ special
elements are in cycles of length greater than one. Choose first these special
elements (in $\binom{r}{i}$ ways), and then place the $i$ non-special elements
into their cycles. This gives $n(n-1)\cdots(n-i+1)=n^{\underline{i}}$ choices.
Then mark both the $i$ special elements and the non-special ones with a bar,
for a total of $2^{i}\cdot 2^{i}$ options. The other $n-i$ non-special
elements are placed into the $i$ special cycles or outside them. This yields
$(i+1)^{\overline{n-i}}$ options. There are $2^{n-i}$ ways to mark these
elements or not. Up to now, the count is

(5.8) $\binom{r}{i}n^{\underline{i}}2^{2i}(i+1)^{\overline{n-i}}2^{n-i}.$

Observe that in the non-special part of the permutation, the placement above
might have introduced some fixed points and these must be removed. Among the
above permutations, the number of those type B derangements which have exactly
$k$ fixed points among the $n-i$ elements is

$\binom{n-i}{k}n^{\underline{i}}2^{2i}(i+1)^{\overline{n-i-k}}2^{n-i-k}.$

The inclusion-exclusion principle now completes the proof. ∎

###  5.1. The generating function and asymptotics of $d_{r,n}^{B}$

Theorem 5.3 is now used to produce the exponential generating function of
$\\{d_{r,n}^{B}\\}$.

######  Theorem 5.4.

The formula

(5.9)
$\sum_{n=0}^{\infty}d_{r,n}^{B}\frac{x^{n}}{n!}=\frac{e^{-x}}{1-2x}\left(\frac{1+2x}{1-2x}\right)^{r},$

holds.

###### Proof.

Start with

$\sum_{n=0}^{\infty}\frac{d_{r,n}^{B}}{2^{n}}\frac{x^{n}}{n!}=\sum_{i=0}^{r}\binom{r}{i}2^{i}\sum_{k=0}^{\infty}\left(-\frac{1}{2}\right)^{k}\sum_{n=i+k}^{\infty}\binom{n-i}{k}n^{\underline{i}}(i+1)^{\overline{n-i-k}}\frac{x^{n}}{n!}.$

The innermost sum is

$\sum_{n=i+k}^{\infty}\binom{n-i}{k}n^{\underline{i}}(i+1)^{\overline{n-i-k}}\frac{x^{n}}{n!}=\frac{x^{i}}{(1-x)^{i+1}}\frac{x^{k}}{k!}.$

Multiplying the right hand side by $\left(-\frac{1}{2}\right)^{k}$ and summing
over $k$ produces $e^{-x/2}$. Thus

$\sum_{n=0}^{\infty}\frac{d_{r,n}^{B}}{2^{n}}\frac{x^{n}}{n!}=\sum_{i=0}^{r}\binom{r}{i}2^{i}\frac{e^{-x/2}x^{i}}{(1-x)^{i+1}}=\frac{e^{-x/2}}{1-x}\left(\frac{1+x}{1-x}\right)^{r}.$

Substituting $2x$ in place of $x$ produces the result. ∎

The asymptotics of the type B $r$-derangements, when $r$ is fixed and $n$
tends to infinity, are presented next. Standard methods of the analysis of the
principal part of the generating function are used. Details appeared in [23,
Theorem 5.2.1].

######  Corollary 5.5.

For any fixed $r\geq 0$ and large $n$

$\frac{d_{r,n}^{B}}{n!}\sim\frac{(-2)^{n}}{\sqrt{e}}\sum_{i=0}^{r}\binom{r}{i}2^{i}\left[\binom{-i-1}{n}-\frac{2i-1}{2}\binom{-i}{n}\right].$

##  6\. A generalization of the $r$-Stirling numbers

Let $\sigma=c_{1}c_{2}\cdots c_{s}$ be the usual cycle representation of a
permutation into $s$ disjoint cycles. The orders of the cycles are denoted by
$ord(c_{j}),\,1\leq j\leq s$. For example,
$\overline{4}\,3\,\overline{2}\,\overline{7}\,5\,\overline{8}\,1\,9\,6$ is
written as $(1\overline{4}\,\overline{7})(\overline{2}3)(5)(6\overline{8}9)$.
Then
$\,\,\,ord(c_{1})=3,\,\,\,ord(c_{2})=2,\,\,\,\,ord(c_{3})=1,\,\,\,ord(c_{4})=3$.
The derangements of type $B$ can be characterized by

${\mathcal{D}}_{n}^{B}=\\{\sigma=c_{1}\cdots c_{s}:\text{for all $i\in[s]$
either $ord(c_{i})\geq 2$ or
$c_{i}\subseteq[\bar{n}]=\\{\bar{1},\bar{2},\dots,\bar{n}\\}$}\\}.$

This leads to the following

######  Definition 6.1.

Let $\sigma=c_{1}\cdots c_{s}$ be a permutation of type $B$ of length $n$ with
$s$ cycles. The permutation $\sigma$ is a _$m$ -restricted permutation of type
$B$_ if for all $1\leq i\leq s$ either the order of each cycle satisfies
$ord(c_{i})\leq m$ or each item in $c_{i}$ is signed, that is
$c_{i}\subseteq[\bar{n}]$. The permutation $\sigma$ is an _$m$ -associated
permutation of type $B$_ if for all $1\leq i\leq s$ either the order of each
cycle satisfies that $ord(c_{i})\geq m$ or $c_{i}\subseteq[\bar{n}]$.

Denote by $\mathcal{A}_{n,\leq m}^{B}(\mathcal{A}_{n,\geq m}^{B})$ the set of
all $m$-restricted (associated) permutations of type $B$ in
${\mathcal{D}}_{n}^{B}$. The _$m$ -restricted (associated) factorial numbers
of type $B$_, $A^{B}_{n,\leq m}$ is the corresponding cardinalities. Note that
${\mathcal{D}}^{B}_{n}=\mathcal{A}^{B}_{n,\geq 2}$. The _associated
(restricted) Stirling numbers of the first kind of type $B$_, ${n\brack
k}_{\geq m}^{B}({n\brack k}_{\leq m}^{B}$ , is the number of permutations of
$A_{n,\geq(\leq)m}^{B}$ with $k$ cycles. The basic relations

$\displaystyle A^{B}_{n,\geq m}:=\sum_{k=0}^{n}{n\brack k}_{\geq
m}^{B},\quad\quad A^{B}_{n,\leq m}:=\sum_{k=0}^{n}{n\brack k}_{\leq m}^{B},$

hold.

The _restricted Stirling numbers of the first kind (of type $A$)_ ${n\brack
k}_{\leq m}$ enumerate the number of permutations on $n$ elements with $k$
cycles with the restriction that none of the cycles contain more than $m$
items. Similarly, the _associated Stirling numbers of the first kind_
${n\brack k}_{\geq m}$ equals the number that each cycle contains at most $m$
items. Komatsu et al. [14] presented a variety of combinatorial properties for
these sequences. Recently, Moll et al. [19] obtained new combinatorial and
arithmetical properties for them.

The restricted and associated Stirling numbers of the first kind satisfy the
recurrence relations

(6.1) $\displaystyle{n\brack k}_{\leq m}$
$\displaystyle=\sum_{i=0}^{m-1}\frac{(n-1)!}{(n-1-i)!}{n-i-1\brack k-1}_{\leq
m},$ (6.2) $\displaystyle{n\brack k}_{\geq m}$
$\displaystyle=\sum_{i=m-1}^{n-1}\frac{(n-1)!}{(n-1-i)!}{n-i-1\brack
k-1}_{\geq m}.$

with initial values

$\displaystyle{0\brack 0}_{\leq m}=1\quad\text{and}\quad{n\brack 0}_{\leq
m}={0\brack n}_{\leq m}=0,$ $\displaystyle{0\brack 0}_{\geq
m}=1\quad\text{and}\quad{n\brack 0}_{\geq m}={0\brack n}_{\geq m}=0,$

for $n>0$. Introduce now the incomplete factorial numbers $A_{i,\leq m}$ and
$A_{i,\geq m}$, as the total number of incomplete permutations, that is

$\displaystyle A_{n,\leq m}:=\sum_{k=0}^{n}{n\brack k}_{\leq m}\quad A_{n,\geq
m}:=\sum_{k=0}^{n}{n\brack k}_{\geq m}.$

######  Theorem 6.2.

For $n\geq 0$, the identities

$\displaystyle A_{n,\leq m}^{B}$
$\displaystyle=\sum_{i=0}^{n}\binom{n}{i}2^{i}A_{i,\leq m}A_{n-i,\geq m+1},$
$\displaystyle A_{n,\geq m}^{B}$
$\displaystyle=\sum_{i=0}^{n}\binom{n}{i}2^{i}A_{i,\geq m}A_{n-i,\leq m-1},$

hold.

###### Proof.

Let $\sigma\in\mathcal{A}^{B}_{n,\geq k}$ and consider
$A_{1}=\\{s\in[n]:\text{there is}\,\,i\in[k]\text{ such that
}\sigma^{i}_{s}=s\\},$ and $A_{2}=A_{1}^{c}$. It is clear that
$A_{2}\subseteq[n]$ and so there is no coloring on them. Consider now the the
function

$\varphi:\mathcal{A}^{B}_{n,\leq
k}\longrightarrow\bigcup_{i=0}^{n}\binom{[n]}{n-i}\times[2]^{[i]}\times\mathcal{A}_{i,\leq
k}\times\mathcal{A}_{n-1,\geq k+1},$

given by
$\varphi(\sigma)=(A_{2},f,\left.\sigma\right|_{A_{1}},\left.\sigma\right|_{A_{2}}),$
where $f(x)=\chi_{[\bar{n}]}(x).$ It is easy to check that this is a
bijection, completing the proof. ∎

###  6.1. The $r$-version

This subsection consider the analog of the results presented above for the
case of $r$-permutations.

######  Definition 6.3.

Let $n,\,r\in\mathbb{N}$ and $m\geq 1$. A type B $\,\,m$-associated
$r$-permutation on the set $[n+r]$ is a signed permutation on $[n+r]$, with
the restriction that the order of each cycle is at least $m$, and the first
$r$ elements (called special) are restricted to be in distinct cycles. The set
of all $m$-associated $r$-permutation of type $B$ on $[n+r]$ is denoted by
$\mathcal{A}_{n,\geq m,r}^{B}$ and its cardinality by $A_{n,\geq m,r}^{B}$.

The number of elements of $\mathcal{A}_{n,\geq m,r}^{B}$ with $k+r$ cycles is
called the $m$-associated $r$-Stirling number of type $B$ and is denoted by
$\displaystyle\begin{bmatrix}n\\\ k\end{bmatrix}_{\geq m,r}^{B}$. Counting
over all possible cycles gives the relation

(6.3) $A_{n,\geq m,r}^{B}=\sum_{k=0}^{n}\begin{bmatrix}n\\\
k\end{bmatrix}_{\geq m,r}^{B}.$

In the cases $m=0,\,1$, there are no restrictions on the sign, so one can
color any element in $2^{n+r}$ ways and then choose the blocks as the normal
$r-$Stirling numbers of the first kind. It follows that

${n\brack 0}_{\geq m,r}^{B}=2^{n+r}{n\brack
0}_{r}=2^{n+r}n!\binom{n+r-1}{r-1}.$

The case $m=2$ was described in Theorem 2.1. The next result gives a general
recurrence relation. This can be used to analyze the situation for $m>2$.

The symbol $Par_{\leq c}(a,b)$ denotes the number of composition of $a$ into
$b$ positive parts, each part of size at most $c$, then

$Par_{\leq c}(a,b)=\begin{cases}0,&c\leq 0\text{ and }(a\neq 0\text{ or }b\neq
0);\\\
\displaystyle\sum_{i=0}^{b}(-1)^{i}\binom{b}{i}\binom{a-ci-1}{b-1},&\text{otherwise}.\end{cases}$

Introduce the function

(6.4) $\tau_{m,n}(j)=\begin{cases}2^{j+1}&\quad\text{if}\,\,\,m-1\leq j\leq
n\\\ 1&\quad\text{otherwise}.\end{cases}$

######  Theorem 6.4.

For $n\geq 0$, $k,r\geq 1$ and $m>2$, the recursion

${n+1\brack k}_{\geq
m,r}^{B}=\sum_{j=0}^{n}j!\tau_{m,n}(j)\binom{n}{j}{n-j\brack k-1}_{\geq
m,r}^{B}+r\sum_{j=0}^{n}(j+1)!\tau_{m,n+1}(j+1)\binom{n}{j}{n-j\brack
k}^{B}_{\geq m,r-1},$

holds. The initial conditions are given by

$\displaystyle{n\brack 0}_{\geq m,r}^{B}$
$\displaystyle=n!\sum_{p=0}^{r}\sum_{j=0}^{p}\binom{r}{p}\binom{p}{j}\sum_{k=0}^{n}2^{n+p-k-j}Par_{\leq
m-2}(k,j)Par_{\geq m-1}(n-k,p-j).$

###### Proof.

The initial conditions are discussed first. For $m>2$, choose $r-p$ elements
from the $r$ special elements and assign them to its own bar. This can be done
in $\binom{r}{p}$ ways. From the remaining $p$ special elements, choose $j$ of
them which will contain cycles of size less than $m$ so the have to have all
sign. This cane done in $\binom{p}{j}$ ways. Then choose $k$ elements out of
$n$ to put in these $j$ cycles in $\binom{n}{k}Par_{\leq m-2}(k,j)k!$ ways.
The remaining $n-k$ elements will be in the $p-j$ cycles with length greater
or equal to $m$, in $Par_{\geq m-1}(n-k,p-j)$ ways. Note that

$Par_{\geq c}(a,b)=Par_{\geq 1}(a-(c-1)b,b)=\binom{a-(c-1)b-1}{b-1}.$

The inclusion-exclusion principle gives the expression for $Par_{\leq
c}(a,b)$. Adding over all possibilities for $p,j,k$ gives the result.

The recursion is discussed next. The discussion is divided into cases:

  1. (1)

Either $n+1$ is in a cycle without special elements and of length $<m$. This
can be done by selecting the $j$ elements which are in these cycles and taking
care of the cyclic order, to produce

$\binom{n}{j}j!{n-j\brack k-1}^{B}_{\geq m,r}.$

  2. (2)

$n+1$ is in a cycle without special elements of length $\geq m$. As before,
select the $j$ elements and choose their signs in $2^{j+1}$ ways.

  3. (3)

$n+1$ is in a cycle with a special element and of length $<m$. Select $j$
elements and take care of the cyclic order to obtain

$r\binom{n}{j}(j+1)!{n-j\brack k}_{\geq m,r-1}.$

  4. (4)

$n+1$ is in a cycle with a special element and of length $\geq m.$ Select $j$
elements as before and now colored them in $2^{j+2}$ ways.

Summing over these options gives the result. ∎

###  6.2. General case of Howard’s identity of type $B$

Howard [13] established several combinatorial identities involving binomial
coefficients and Stirling number of both kinds. Caicedo et al. [8] gave
combinatorial proofs and generalization for some of them. For example, the
identity

${n\brack n-k}=\sum_{\ell=0}^{k}\binom{n}{2k-\ell}{2k-\ell\brack k-\ell}_{\geq
2}$

is such an example. The next statement provides a $B$-analogue.

######  Theorem 6.5.

The identity

$\displaystyle{n\brack k}^{B}_{\geq m,r}$
$\displaystyle=\sum_{p=0}^{r}\sum_{l=0}^{k}\binom{n}{ml}\binom{r}{p}\binom{n-ml}{(m-1)p}\frac{(2^{m}-1)^{l+p}(ml)!((m-1)p)!}{m^{l}l!}{n-ml-(m-1)p\brack
k-l}^{B}_{\geq m+1,r-p}$
$\displaystyle=n!\sum_{p=0}^{r}\sum_{l=0}^{k}\binom{r}{p}\frac{(2^{m}-1)^{l+p}}{m^{l}l!(n-m(l+p)+p)!}{n-m(l+p)+p\brack
k-l}^{B}_{\geq m+1,r-p}$

holds.

###### Proof.

Consider a type B $r$-permutation $\sigma\in\mathcal{A}^{B}_{n,\geq m,r}$ with
$k+r$ cycles and let $l$ be the number of cycles $\mathfrak{b}$ of size $m$
such that $\mathfrak{b}\cap([r]\cup[\bar{r}])=\emptyset$ and
$|\mathfrak{b}\cap[\overline{n+r}]|<m.$ Let $p$ be the number of cycles with
the above property with $\mathfrak{b}\cap([r]\cup[\bar{r}])\neq\emptyset$. The
number of permutations with this two statistics are counted by the expression
on the left-hand side. Adding for all cases of $p$ and $l,$ yields the result.
∎

The special case $r=0$ is stated next.

######  Corollary 6.6.

The identity

${n\brack k}_{\geq
m}^{B}=\sum_{l=0}^{k}\binom{n}{ml}\frac{(ml)!}{m^{l}l!}(2^{m}-1)^{l}{n-ml\brack
k-l}^{B}_{\geq m+1}$

holds.

The case $m=1$ is similar.

######  Corollary 6.7.

For $n,k\geq 0$, the identity

$\displaystyle{n\brack k}^{B}_{r}$
$\displaystyle=\sum_{p=0}^{r}\sum_{\ell=0}^{k}\binom{r}{p}\binom{n}{\ell}{n-\ell\brack
k-\ell}_{\geq 2,r-p},$

holds. Moreover, if $r=0$ one obtains

${n\brack k}^{B}=\sum_{\ell=0}^{k}\binom{n}{\ell}{n-\ell\brack
k-\ell}^{B}_{\geq 2}.$

###  6.3. The Riordan matrices

It turns out that the sequence ${n\brack k}_{\geq m,r}^{B}$ can be encoded by
a Riordan matrix.

######  Theorem 6.8.

The matrix $\mathcal{C}_{\geq m,r}:=\left({n\brack k}_{\geq
m,r}^{B}\right)_{n,k\geq 0}$ is an exponential Riordan array given by

$\mathcal{C}_{\geq
m,r}=\left(\left(\frac{1-x^{m-1}}{1-x}-\frac{2^{m}x^{m-1}}{1-2x}\right)^{r},-\ln(1-2x)-\sum_{\ell=1}^{m-1}\frac{2^{k}-1}{k}x^{k}\right).$

Theorem 4.2 can be generalized as follows. The proof is left to the reader.

######  Theorem 6.9.

If $m>0,$ the two diagonals below the main diagonal are

$\displaystyle{n+1\brack n}^{B}_{\geq m,r}$
$\displaystyle=2^{(n+r+1)\delta_{m,1}+2\delta_{m,2}-1}(n+1)(n+2r),$
$\displaystyle{n+2\brack n}^{B}_{\geq m,r}$
$\displaystyle=\frac{2^{(n+r+2)\delta_{m,1}}}{12}\binom{n+2}{2}\left(3\cdot
2^{4\delta_{m,2}}(4r(r+n-1)+n(n-1))+2^{3(\delta_{m,2}+\delta_{m,3})+3}(n+3r)\right)$

where $\delta_{a,b}$ is the Kronecker delta function.

Acknowledgements.

The first author thanks for hospitality the Department of Mathematics of
Universidad Nacional de Colombia, Bogotá, Colombia, where the presented work
was initiated. The third author thanks the Department of Mathematics of the
Tulane University, New Orleans. The last author is a graduate student at
Tulane University. The research of the third author was partially supported by
the Universidad Nacional de Colombia, Project No. 46240.

## References

  * [1] S. H. Assaf.  Cyclic derangements.  Electron. J. Combin., 17:$\\#$ R163, 2010.
  * [2] M. Baake and U. Grimm.  Coordination sequences for root lattices and related graphs.  Z. Krist., 212:253–256, 1997.
  * [3] P. Barry.  On a family of generalized Pascal triangles defined by exponential Riordan arrays.  J. Integer Seq., article 10:07.3.5, 2007.
  * [4] F. Bergeron, P. Flajolet, and B. Salvy.  Varieties of increasing trees.  Lecture Notes in Computer Science, 581:24–48, 1992.
  * [5] A. Björner and F. Brenti.  Combinatorics of Coxeter groups, volume 231 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 2005.
  * [6] F. Brenti.  $q$-Eulerian polynomials arising from Coxeter groups.  Europ. J. Combinatorics, 15:417–441, 1994.
  * [7] A. Z. Broder.  The $r$-Stirling numbers.  Disc. Math., 49:241–259, 1984.
  * [8] J. Caicedo, V. Moll, J. L. Ramírez, and D. Villamizar.  Extensions of set partitions and permutations.  Electron. J. Comb., 26:1–45, 2019.
  * [9] C. O. Chow.  On derangement polynomials of type B.  Sém. Lothar. Combin., 55:Article B55b, 2006.
  * [10] J. Conway and N. J. A. Sloane.  Low dimensional lattices, VII. coordination sequences.  Proc. R. Soc. London, Ser. A, 453:2369–2389, 1997.
  * [11] R. M. Corless, G. W. Gonnet, D. H. Hare, D. J. Jeffrey, and D. E. Knuth.  On the Lambert W-function.  Adv. Comp. Math., 5:329–359, 1996.
  * [12] E. Deutsch, L. Ferrari, and S. Rinaldi.  Production matrices and Riordan arrays.  Ann. Comb., 13:65–85, 2009.
  * [13] F. T. Howard.  A theorem relating potential and Bell polynomials.  Discrete Math., 39:129–143, 1982.
  * [14] T. Komatsu, K. Liptai, and I. Mező.  Incomplete poly-Bernoulli numbers associated with incomplete Stirling numbers.  Publ. Math. Debrecen, 88:357–368, 2016.
  * [15] T. Lengyel.  Identities for the generating function of the multiset $\left\lfloor n\phi^{m}\right\rfloor$ for $m=-1,\,1,\,2.$.  Fib. Quart., 44:274–276, 2006.
  * [16] F. R. McMorris and N. W. Zaslavsky.  The number of cladistic characters.  Math. Biosciences, 54:3–10, 1981.
  * [17] I. Mező and J. L. Ramirez.  A combinatorial approach to derangement matrix of type B.  Linear Algebra and its Applications, 582:156–180, 2019.
  * [18] I. Mező, J. L. Ramirez, and C. Wang.  On generalized derangements and some orthogonal polynomials.  Integers, 19, 2019.
  * [19] V. H. Moll, J. L. Ramírez, and D. Villamizar.  Combinatorial and arithmetical properties of the restricted and associated Bell and factorial numbers.  Journal of Combinatorics, 9:693–720, 2018.
  * [20] J. Riordan.  An introduction to Combinatorial Analysis.  Dover Publications, New York, 2002.
  * [21] L. W. Shapiro, S. Getu, W. J. Woan, and L. C. Woodson.  The Riordan group.  Discrete Appl. Math., 34:229–239, 1991.
  * [22] C. Wang, P. Miska, and I. Mező.  The $r$-derangement numbers.  Disc. Math., 340:1681–1692, 2017.
  * [23] H. S. Wilf.  generatingfunctionology.  Academic Press, 1st edition, 1990.


the main text and enters a second oscillatory phase producing the clock
signal. The first oscillatory stage does not produce any detectable signal,
since the the inflaton and the clock field are not directly coupled. On the
other hand, since $\sigma$ is not at rest, the clock field contributes to the
total potential energy and slightly enhances the Hubble parameter while it is
frozen and we observe an enhancement of power spectrum at large scales, before
the dip. Although such large scales are the ones mostly affected by cosmic
variance, for $C\gtrsim 0.7$ the enhancement becomes significant and the
predictions at those scales are different from those obtained by setting $C=0$
as we did in the main text.

##  Appendix B Addition of small scale ACT data

In this Appendix, we complement our data set with measurements of small scale
anisotropies. As a representative example, we consider data from the ACT
collaboration ACT:2020gnv . Since small scale data cannot set any meaningful
constraints on the dip feature signal, we limit the analysis to the restricted
model of Section II.6.

We consider TT, TE and EE anisotropies power spectra from the ACT DR4 dataset.
The likelihood delivered by the ACT
collaboration151515https://lambda.gsfc.nasa.gov/product/act/act_dr4_likelihood_cmb_info.cfm
ACT:2020frw  only depends on one nuisance parameter, i.e. the overall
polarization efficiency $y_{p}$, while all the other contributions from
foregrounds are already marginalized over. Unlike the data used in the main
text, which were unbinned, ACT data are thus binned in bandpowers whose
covariance includes the noise and foregrounds effects. The multiple range
covered by DR4 is $600\leq\ell\leq 4125$ in TT and $350\leq\ell\leq 4125$ in
TE and EE. Note that the lack of information at large angular leads to bad
constraints on the optical depth $\tau_{\rm reio}$. A simple way to fix it,
used in ACT:2020frw , is to include a Gaussian prior on it. However, we decide
not to use it and to first simply explore ACT-only constraints.

As ACT is highly complementary to Planck, which has a better sensitivity to
anisotropies at larger scales, we also explore constraints on our feature
models from their combination. In order not to double count information from
the two datasets, we restrict the range of ACT data following the procedure
outlined in Ref. ACT:2020frw , i.e. we cut the TT likelihood at $\ell_{\rm
min}=1800$ and use only higher multipoles. We only present results obtained
for the combination of ACT and EG20, since running the P18 likelihood is
computationally much more expensive. At low-$\ell$, we use both lowT and
lowE161616Note that lowE data are usually trade for a prior on $\tau_{\rm
reio}$ when combining ACT and Planck. However, we use lowE to be consistent
with the results in the main text..

To further speed up the computation we set the flag $\tt{lsample\\_boost}=50$
in CosmoMC which allows for a faster computation of the CMB power spectra. We
have checked that this produces differences in the $\chi^{2}$ of the order
$\Delta\chi^{2}\sim 0.01$, which does not affect our analysis.

Figure 22:  Triangle plot for the restricted model for Atacama Cosmology
Telescope (ACT, pink), Clean CamSpec v12.5HMcln (EG20, light blue) and their
combination (olive). In the inset, we also show the best-fit for the combined
dataset and compare it to the one for EG20.

Our results are presented in Fig. 22. ACT data cannot place any sensible
constrain on our model if they are not supplemented by other data at large
scales. In particular, it is interesting to notice that the parameter
governing the spectral index, i.e. $C_{\Theta}$, is only bounded from above.
It is well known that ACT data constrains the PPS to be scale invariant
ACT:2020gnv . However, adopting the prior in Table 1, our model does not admit
this possibility by construction since $n_{s}\simeq 1-2C_{\Theta}$ with
$C_{\Theta}>0$. This leads to an evidence of $\ln B=+4.5$ in favor of the CPSC
model over the featureless one (the one with $\Delta P_{\rm clock}/P=0$)
because oscillatory features can improve the fit compared to the a red-tilted
featureless spectrum, which is not preferred by ACT data.

Constraints change when EG20 is added to ACT. As can be seen, now the overall
PPS amplitude can be constrained owing to the inclusion of lowE data.
Furthermore, constraints on $C_{\Theta}$ are very similar to those from EG20,
though slightly shifted towards a less red tilt. However, as also mentioned in
the main text, the addition of ACT does not significantly change constraints
of the feature parameters, as can be seen from their posterior distributions.
The reasons are the following. First, the bestfit feature signals that provide
a better fit to Planck data significantly deviate from scale invariance at
$\ell\lesssim 1500$. Although from $900\lesssim\ell\lesssim 1500$ the error
bars on the EE power spectra are smaller than Planck ones, the ones on TT (and
thus TE) are worse. Planck’s TT and TE currently have the most constraining
power on our model. Secondly, as mentioned above, ACT data are binned, making
it hard to use them to sizeably improve constraints on highly oscillatory
feature signals. As a result, the Bayes factor is a bit worse than the one for
EG20 only, but still inconclusive, i.e. $\ln B=-1.80\pm 0.38$.

To see this point more clearly, let us discuss the bestfit candidate of the
combined dataset. As shown by the inset in Fig. 22, the feature signal is the
same as the restricted LFC presented in Table 5. The total $\Delta\chi^{2}$ to
data does not change much and is broken down into individual $\chi^{2}$’s as
follows

$\Delta\chi^{2}_{\rm TOT}$ | $\Delta\chi^{2}_{\mathrm{prior}}$ | $\Delta\chi^{2}_{\mathrm{high-\ell}}$ | $\Delta\chi^{2}_{\mathrm{low-T}}$ | $\Delta\chi^{2}_{\mathrm{low-E}}$ | $\Delta\chi^{2}_{\rm ACT}$
---|---|---|---|---|---
14.0 | 0.63 | 12.84 | 0.70 | -0.04 | -0.23

The fit to ACT data is essentially as good as the baseline bestfit model, as
the amplitude of the oscillations is very small at the multipoles tested by
ACT. The slightly less red tilt degrades a bit the fit to high-$\ell$ and lowE
Planck data, but the effect is compensated by the fit to lowT which is
slightly improved.

##  Appendix C Comparison of different parameterizations

Figure 23:  Same as Fig. 4 but with a different choice of priors and parameterization described in App. C. Dataset | P18 (Plik bin1) | EG20 (CamSpec v12.5HMcln)
---|---|---
$\ln B$ | $-0.69\pm 0.38$ | $-1.47\pm 0.36$
Table 8: Same as Table 2 but with a different choice of priors and parameterization described in App. C. Dataset | P18 (Plik bin1) | EG20 (CamSpec v12.5HMcln)
---|---|---
$\ln B$ | $-0.38\pm 0.38$ | $-0.42\pm 0.35$
Table 9: Same as Table 4 but with a different choice of priors and
parameterization described in App. C. Figure 24:  Same as Fig. 9 but with a
different choice of priors and parameterization described in App. C.

Figure 25:  Same as Fig. 10 but with a different choice of priors and
parameterization described in App. C.

In order to test the robustness of our results, in this Appendix we test our
model using a different parameterization. We trade the parameters $(\Delta
P_{\rm dip}/P,\,\Delta P_{\rm clock}/P)$ for $(C_{\sigma},\,\xi\sigma_{f})$
respectively and assume a linear prior on $m_{\sigma}/H$ instead of a
logarithmic one. Indeed, since the prior range for $m_{\sigma}/H$ is quite
large and we have already observed that several frequencies are allowed by
data, it is possible, at least in principle, that prominent peak around
$m_{\sigma}/H\sim 18$, which is one of the main results of this paper, is an
artifact of the particular choice of the prior on the frequency parameter
$m_{\sigma}/H$. It is therefore important to test the robustness of our
results against a different choice of priors and parameterization. We adopt
the following priors on these parameters: $C_{\sigma}\times
10^{7}\in[0.09,\,1]$, $\xi\sigma_{f}\in[0.0,\,0.15]$ and
$m_{\sigma}/H\in[1,\,75]$.

We show the results obtained using this parameterization in Fig. 23. The Bayes
factors are given in Table 8. Note that, since the parameterization as well as
the prior volume have changed, the Bayes factor is also expected to change.
Nevertheless, within the errors, the Bayes factors for each data set are
consistent with those quoted in Table 8 and the model selection is
inconclusive.

What is crucial to observe is that both posteriors again show a peak around
$m_{\sigma}/H\sim 18$, which confirms LFCII as our best-fit candidate, no
matter what prior is adopted in the analysis. This is also corroborated by the
sample plots in Fig. 23, that visually show that the better likelihood samples
concentrate around $m_{\sigma}/H\sim 18$ for both datasets. Since the linear
prior gives more weight to large values of $m_{\sigma}/H$ we see that high
frequencies are now better explored by the nested sampling, causing the sample
plots to be more populated in the high frequency region. Overall, the
constraints are consistent with our findings in the main text, confirming the
robustness of our analysis.

For completeness, we also quote the constraints on the restricted CPSC model
and on the SiRe model in Fig. 24 and 25 as well as quote the evidence for the
restricted model using this parameterization in Table 9. Also in this case,
the results are consistent with the main text.

## References

  * (1) X. Chen, Adv. Astron. 2010, 638979 (2010) doi:10.1155/2010/638979 [arXiv:1002.1416 [astro-ph.CO]].
  * (2) J. Chluba, J. Hamann and S. P. Patil, Int. J. Mod. Phys. D 24, no.10, 1530023 (2015) doi:10.1142/S0218271815300232 [arXiv:1505.01834 [astro-ph.CO]].
  * (3) A. Slosar, K. N. Abazajian, M. Abidi, P. Adshead, Z. Ahmed, D. Alonso, M. A. Amin, B. Ansarinejad, R. Armstrong and C. Baccigalupi, et al. Bull. Am. Astron. Soc. 51, no.3, 98 (2019) [arXiv:1903.09883 [astro-ph.CO]].
  * (4) Y. Akrami et al. [Planck], Astron. Astrophys. 641, A10 (2020) doi:10.1051/0004-6361/201833887 [arXiv:1807.06211 [astro-ph.CO]].
  * (5) H. V. Peiris et al. [WMAP], Astrophys. J. Suppl. 148, 213-231 (2003) doi:10.1086/377228 [arXiv:astro-ph/0302225 [astro-ph]].
  * (6) D. K. Hazra, A. Shafieloo and T. Souradeep, JCAP 11, 011 (2014) doi:10.1088/1475-7516/2014/11/011 [arXiv:1406.4827 [astro-ph.CO]].
  * (7) M. Braglia, X. Chen and D. K. Hazra, [arXiv:2106.07546 [astro-ph.CO]].
  * (8) X. Chen and M. H. Namjoo, Phys. Lett. B 739, 285-292 (2014) doi:10.1016/j.physletb.2014.11.002 [arXiv:1404.1536 [astro-ph.CO]].
  * (9) X. Chen, M. H. Namjoo and Y. Wang, JCAP 02, 027 (2015) doi:10.1088/1475-7516/2015/02/027 [arXiv:1411.2349 [astro-ph.CO]].
  * (10) X. Chen, JCAP 01, 038 (2012) doi:10.1088/1475-7516/2012/01/038 [arXiv:1104.1323 [hep-th]].
  * (11) X. Chen, Phys. Lett. B 706, 111-115 (2011) doi:10.1016/j.physletb.2011.11.009 [arXiv:1106.1635 [astro-ph.CO]].
  * (12) X. Chen and C. Ringeval, JCAP 08, 014 (2012) doi:10.1088/1475-7516/2012/08/014 [arXiv:1205.6085 [astro-ph.CO]].
  * (13) X. Gao, D. Langlois and S. Mizuno, JCAP 10, 023 (2013) doi:10.1088/1475-7516/2013/10/023 [arXiv:1306.5680 [hep-th]].
  * (14) T. Noumi and M. Yamaguchi, JCAP 12, 038 (2013) doi:10.1088/1475-7516/2013/12/038 [arXiv:1307.7110 [hep-th]].
  * (15) X. Chen and Y. Wang, Phys. Rev. D 81, 063511 (2010) doi:10.1103/PhysRevD.81.063511 [arXiv:0909.0496 [astro-ph.CO]].
  * (16) X. Chen and Y. Wang, JCAP 04, 027 (2010) doi:10.1088/1475-7516/2010/04/027 [arXiv:0911.3380 [hep-th]].
  * (17) R. Saito, M. Nakashima, Y. i. Takamizu and J. Yokoyama, JCAP 11, 036 (2012) doi:10.1088/1475-7516/2012/11/036 [arXiv:1206.2164 [astro-ph.CO]].
  * (18) R. Saito and Y. i. Takamizu, JCAP 06, 031 (2013) doi:10.1088/1475-7516/2013/06/031 [arXiv:1303.3839 [astro-ph.CO]].
  * (19) J. A. Adams, B. Cresswell and R. Easther, Phys. Rev. D 64, 123514 (2001) doi:10.1103/PhysRevD.64.123514 [arXiv:astro-ph/0102236 [astro-ph]].
  * (20) R. Bean, X. Chen, G. Hailu, S. H. H. Tye and J. Xu, JCAP 03, 026 (2008) doi:10.1088/1475-7516/2008/03/026 [arXiv:0802.0491 [hep-th]].
  * (21) M. J. Mortonson, C. Dvorkin, H. V. Peiris and W. Hu, Phys. Rev. D 79, 103519 (2009) doi:10.1103/PhysRevD.79.103519 [arXiv:0903.4920 [astro-ph.CO]].
  * (22) D. K. Hazra, M. Aich, R. K. Jain, L. Sriramkumar and T. Souradeep, JCAP 10, 008 (2010) doi:10.1088/1475-7516/2010/10/008 [arXiv:1005.2175 [astro-ph.CO]].
  * (23) D. K. Hazra, A. Shafieloo, G. F. Smoot and A. A. Starobinsky, JCAP 08, 048 (2014) doi:10.1088/1475-7516/2014/08/048 [arXiv:1405.2012 [astro-ph.CO]].
  * (24) V. Miranda, W. Hu and C. Dvorkin, Phys. Rev. D 91, no.6, 063514 (2015) doi:10.1103/PhysRevD.91.063514 [arXiv:1411.5956 [astro-ph.CO]].
  * (25) A. A. Starobinsky, JETP Lett. 55, 489-494 (1992)
  * (26) X. Chen, R. Easther and E. A. Lim, JCAP 06, 023 (2007) doi:10.1088/1475-7516/2007/06/023 [arXiv:astro-ph/0611645 [astro-ph]].
  * (27) A. Achucarro, J. O. Gong, S. Hardeman, G. A. Palma and S. P. Patil, JCAP 01, 030 (2011) doi:10.1088/1475-7516/2011/01/030 [arXiv:1010.3693 [hep-ph]].
  * (28) P. Adshead, C. Dvorkin, W. Hu and E. A. Lim, Phys. Rev. D 85, 023531 (2012) doi:10.1103/PhysRevD.85.023531 [arXiv:1110.3050 [astro-ph.CO]].
  * (29) X. Gao, D. Langlois and S. Mizuno, JCAP 10, 040 (2012) doi:10.1088/1475-7516/2012/10/040 [arXiv:1205.5275 [hep-th]].
  * (30) V. Miranda, W. Hu and P. Adshead, Phys. Rev. D 86, 063529 (2012) doi:10.1103/PhysRevD.86.063529 [arXiv:1207.2186 [astro-ph.CO]].
  * (31) N. Bartolo, D. Cannone and S. Matarrese, JCAP 10, 038 (2013) doi:10.1088/1475-7516/2013/10/038 [arXiv:1307.3483 [astro-ph.CO]].
  * (32) J. Fumagalli, S. Renaux-Petel and L. T. Witkowski, JCAP 08, 030 (2021) doi:10.1088/1475-7516/2021/08/030 [arXiv:2012.02761 [astro-ph.CO]].
  * (33) M. Braglia, X. Chen and D. K. Hazra, JCAP 03, 005 (2021) doi:10.1088/1475-7516/2021/03/005 [arXiv:2012.05821 [astro-ph.CO]].
  * (34) D. K. Hazra, D. Paoletti, I. Debono, A. Shafieloo, G. F. Smoot and A. A. Starobinsky, doi:10.1088/1475-7516/2021/12/038 [arXiv:2107.09460 [astro-ph.CO]].
  * (35) M. Braglia, X. Chen and D. K. Hazra, JCAP 06, 005 (2021) doi:10.1088/1475-7516/2021/06/005 [arXiv:2103.03025 [astro-ph.CO]].
  * (36) Z. Lalak, D. Langlois, S. Pokorski and K. Turzynski, JCAP 07, 014 (2007) doi:10.1088/1475-7516/2007/07/014 [arXiv:0704.0212 [hep-th]].
  * (37) M. Braglia, D. K. Hazra, L. Sriramkumar and F. Finelli, JCAP 08, 025 (2020) doi:10.1088/1475-7516/2020/08/025 [arXiv:2004.00672 [astro-ph.CO]].
  * (38) W. J. Handley, M. P. Hobson and A. N. Lasenby, Mon. Not. Roy. Astron. Soc. 450, no.1, L61-L65 (2015) doi:10.1093/mnrasl/slv047 [arXiv:1502.01856 [astro-ph.CO]].
  * (39) W. J. Handley, M. P. Hobson and A. N. Lasenby, Mon. Not. Roy. Astron. Soc. 453, no.4, 4385-4399 (2015) doi:10.1093/mnras/stv1911 [arXiv:1506.00171 [astro-ph.IM]].
  * (40) M. Powell, “The BOBYQA Algorithm for Bound Constrained Optimization without Derivatives,” Technical Report, Department of Applied Mathematics and Theoretical Physics.
  * (41) X. Chen, R. Easther and E. A. Lim, JCAP 04, 010 (2008) doi:10.1088/1475-7516/2008/04/010 [arXiv:0801.3295 [astro-ph]].
  * (42) N. Aghanim et al. [Planck], Astron. Astrophys. 641, A1 (2020) doi:10.1051/0004-6361/201833880 [arXiv:1807.06205 [astro-ph.CO]].
  * (43) R. J. Thornton, P. A. R. Ade, S. Aiola, F. E. Angilè, M. Amiri, J. A. Beall, D. T. Becker, H. M. Cho, S. K. Choi and P. Corlies, et al. Astrophys. J. Suppl. 227, no.2, 21 (2016) doi:10.3847/1538-4365/227/2/21 [arXiv:1605.06569 [astro-ph.IM]].
  * (44) D. Dutcher et al. [SPT-3G], Phys. Rev. D 104, no.2, 022003 (2021) doi:10.1103/PhysRevD.104.022003 [arXiv:2101.01684 [astro-ph.CO]].
  * (45) A. Lewis and S. Bridle, Phys. Rev. D 66, 103511 (2002) doi:10.1103/PhysRevD.66.103511 [arXiv:astro-ph/0205436 [astro-ph]].
  * (46) R. E. Kass and A. E. Raftery, J. Am. Statist. Assoc. 90, no.430, 773-795 (1995) doi:10.1080/01621459.1995.10476572
  * (47) G. Cañas-Herrera, J. Torrado and A. Achúcarro, Phys. Rev. D 103, 123531 (2021) doi:10.1103/PhysRevD.103.123531 [arXiv:2012.04640 [astro-ph.CO]].
  * (48) G. Efstathiou and S. Gratton, doi:10.21105/astro.1910.00483 [arXiv:1910.00483 [astro-ph.CO]].
  * (49) T. L. Smith, V. Poulin, J. L. Bernal, K. K. Boddy, M. Kamionkowski and R. Murgia, Phys. Rev. D 103, no.12, 123542 (2021) doi:10.1103/PhysRevD.103.123542 [arXiv:2009.10740 [astro-ph.CO]].
  * (50) M. Braglia, M. Ballardini, F. Finelli and K. Koyama, Phys. Rev. D 103, no.4, 043528 (2021) doi:10.1103/PhysRevD.103.043528 [arXiv:2011.12934 [astro-ph.CO]].
  * (51) N. Aghanim et al. [Planck], Astron. Astrophys. 594, A11 (2016) doi:10.1051/0004-6361/201526926 [arXiv:1507.02704 [astro-ph.CO]].
  * (52) P. D. Meerburg and D. N. Spergel, Phys. Rev. D 89 (2014) no.6, 063537 doi:10.1103/PhysRevD.89.063537 [arXiv:1308.3705 [astro-ph.CO]].
  * (53) H. Peiris, R. Easther and R. Flauger, JCAP 09 (2013), 018 doi:10.1088/1475-7516/2013/09/018 [arXiv:1303.2616 [astro-ph.CO]].
  * (54) R. Flauger, L. McAllister, E. Pajer, A. Westphal and G. Xu, JCAP 06, 009 (2010) doi:10.1088/1475-7516/2010/06/009 [arXiv:0907.2916 [hep-th]].
  * (55) R. Flauger and E. Pajer, JCAP 01, 017 (2011) doi:10.1088/1475-7516/2011/01/017 [arXiv:1002.0833 [hep-th]].
  * (56) X. Chen, JCAP 12, 003 (2010) doi:10.1088/1475-7516/2010/12/003 [arXiv:1008.2485 [hep-th]].
  * (57) M. Hazumi et al. [LiteBIRD], Proc. SPIE Int. Soc. Opt. Eng. 11443, 114432F (2020) doi:10.1117/12.2563050 [arXiv:2101.12449 [astro-ph.IM]].
  * (58) P. Ade et al. [Simons Observatory], JCAP 02, 056 (2019) doi:10.1088/1475-7516/2019/02/056 [arXiv:1808.07445 [astro-ph.CO]].
  * (59) Y. Inoue et al. [POLARBEAR], Proc. SPIE Int. Soc. Opt. Eng. 9914, 99141I (2016) doi:10.1117/12.2231961 [arXiv:1608.03025 [astro-ph.IM]].
  * (60) L. Moncelsi, P. A. R. Ade, Z. Ahmed, M. Amiri, D. Barkats, R. Basu Thakur, C. A. Bischoff, J. J. Bock, V. Buza and J. Cheshire, et al. Proc. SPIE Int. Soc. Opt. Eng. 11453, 1145314 (2020) doi:10.1117/12.2561995 [arXiv:2012.04047 [astro-ph.IM]].
  * (61) K. N. Abazajian et al. [CMB-S4], [arXiv:1610.02743 [astro-ph.CO]].
  * (62) M. H. Abitbol et al. [CMB-S4], [arXiv:1706.02464 [astro-ph.IM]].
  * (63) J. Delabrouille et al. [CORE], JCAP 04, 014 (2018) doi:10.1088/1475-7516/2018/04/014 [arXiv:1706.04516 [astro-ph.IM]].
  * (64) http://cmb-bharat.in/
  * (65) S. Hanany et al. [NASA PICO], [arXiv:1902.10541 [astro-ph.IM]].
  * (66) L. Knox, Phys. Rev. D 52, 4307-4318 (1995) doi:10.1103/PhysRevD.52.4307 [arXiv:astro-ph/9504054 [astro-ph]].
  * (67) M. Tegmark, Phys. Rev. D 56, 4514-4529 (1997) doi:10.1103/PhysRevD.56.4514 [arXiv:astro-ph/9705188 [astro-ph]].
  * (68) S. Hamimeche and A. Lewis, Phys. Rev. D 77, 103013 (2008) doi:10.1103/PhysRevD.77.103013 [arXiv:0801.0554 [astro-ph]].
  * (69) Z. Huang, L. Verde and F. Vernizzi, JCAP 04, 005 (2012) doi:10.1088/1475-7516/2012/04/005 [arXiv:1201.5955 [astro-ph.CO]].
  * (70) D. K. Hazra, JCAP 03, 003 (2013) doi:10.1088/1475-7516/2013/03/003 [arXiv:1210.7170 [astro-ph.CO]].
  * (71) X. Chen, C. Dvorkin, Z. Huang, M. H. Namjoo and L. Verde, JCAP 11, 014 (2016) doi:10.1088/1475-7516/2016/11/014 [arXiv:1605.09365 [astro-ph.CO]].
  * (72) M. Ballardini, F. Finelli, C. Fedeli and L. Moscardini, JCAP 10, 041 (2016) [erratum: JCAP 04, E01 (2018)] doi:10.1088/1475-7516/2016/10/041 [arXiv:1606.03747 [astro-ph.CO]].
  * (73) G. A. Palma, D. Sapone and S. Sypsas, JCAP 06, 004 (2018) doi:10.1088/1475-7516/2018/06/004 [arXiv:1710.02570 [astro-ph.CO]].
  * (74) B. L’Huillier, A. Shafieloo, D. K. Hazra, G. F. Smoot and A. A. Starobinsky, Mon. Not. Roy. Astron. Soc. 477, no.2, 2503-2512 (2018) doi:10.1093/mnras/sty745 [arXiv:1710.10987 [astro-ph.CO]].
  * (75) M. Ballardini, F. Finelli, R. Maartens and L. Moscardini, JCAP 04, 044 (2018) doi:10.1088/1475-7516/2018/04/044 [arXiv:1712.07425 [astro-ph.CO]].
  * (76) A. Vasudevan, M. M. Ivanov, S. Sibiryakov and J. Lesgourgues, JCAP 09, 037 (2019) doi:10.1088/1475-7516/2019/09/037 [arXiv:1906.08697 [astro-ph.CO]].
  * (77) F. Beutler, M. Biagetti, D. Green, A. Slosar and B. Wallisch, Phys. Rev. Res. 1, no.3, 033209 (2019) doi:10.1103/PhysRevResearch.1.033209 [arXiv:1906.08758 [astro-ph.CO]].
  * (78) M. Ballardini, R. Murgia, M. Baldi, F. Finelli and M. Viel, JCAP 04, no.04, 030 (2020) doi:10.1088/1475-7516/2020/04/030 [arXiv:1912.12499 [astro-ph.CO]].
  * (79) I. Debono, D. K. Hazra, A. Shafieloo, G. F. Smoot and A. A. Starobinsky, Mon. Not. Roy. Astron. Soc. 496, no.3, 3448-3468 (2020) doi:10.1093/mnras/staa1765 [arXiv:2003.05262 [astro-ph.CO]].
  * (80) S. F. Chen, Z. Vlah and M. White, JCAP 11, 035 (2020) doi:10.1088/1475-7516/2020/11/035 [arXiv:2007.00704 [astro-ph.CO]].
  * (81) Y. Li, H. M. Zhu and B. Li, [arXiv:2102.09007 [astro-ph.CO]].
  * (82) X. Chen, P. D. Meerburg and M. Münchmeyer, JCAP 09, 023 (2016) doi:10.1088/1475-7516/2016/09/023 [arXiv:1605.09364 [astro-ph.CO]].
  * (83) Y. Xu, J. Hamann and X. Chen, Phys. Rev. D 94, no.12, 123518 (2016) doi:10.1103/PhysRevD.94.123518 [arXiv:1607.00817 [astro-ph.CO]].
  * (84) D. K. Hazra, L. Sriramkumar and J. Martin, JCAP 05, 026 (2013) doi:10.1088/1475-7516/2013/05/026 [arXiv:1201.0926 [astro-ph.CO]].
  * (85) J. R. Fergusson, H. F. Gruetjen, E. P. S. Shellard and M. Liguori, Phys. Rev. D 91, no.2, 023502 (2015) doi:10.1103/PhysRevD.91.023502 [arXiv:1410.5114 [astro-ph.CO]].
  * (86) J. R. Fergusson, H. F. Gruetjen, E. P. S. Shellard and B. Wallisch, Phys. Rev. D 91, no.12, 123506 (2015) doi:10.1103/PhysRevD.91.123506 [arXiv:1412.6152 [astro-ph.CO]].
  * (87) A. Lewis, [arXiv:1910.13970 [astro-ph.IM]].
  * (88) S. Aiola et al. [ACT], JCAP 12, 047 (2020) doi:10.1088/1475-7516/2020/12/047 [arXiv:2007.07288 [astro-ph.CO]].
  * (89) S. K. Choi et al. [ACT], JCAP 12, 045 (2020) doi:10.1088/1475-7516/2020/12/045 [arXiv:2007.07289 [astro-ph.CO]].