# Poly-Cauchy numbers - the combinatorics behind

Beáta Bényi  Faculty of Water Sciences, University of Public Service, Baja,
HUNGARY<EMAIL_ADDRESS>and  José L. Ramírez  Departamento de
Matemáticas, Universidad Nacional de Colombia, Bogotá, COLOMBIA
<EMAIL_ADDRESS>
###### Abstract.

We introduce poly-Cauchy permutations that are enumerated by the poly-Cauchy
numbers. We provide combinatorial proofs for several identities involving
poly-Cauchy numbers and some of their generalizations. The aim of this work is
to demonstrate the power and beauty of the elementary combinatorial approach.

###### Key words and phrases:

Poly-Cauchy numbers; permutations; poly-Bernoulli numbers.

###### 2010 Mathematics Subject Classification:

05A05, 05A19

##  1\. Introduction

Poly-Cauchy numbers were defined by Komatsu [11] motivated by the interesting
properties of poly-Bernoulli numbers. While since the introduction many
combinatorial interpretations and investigations appeared in the literature
about poly-Bernoulli numbers, there is no such direction about the poly-Cauchy
numbers yet.

Let $n$ and $k$ be integers with $n\geq 0$ and $k\geq 1$. The _poly-Cauchy
numbers of the first kind_ are defined by

$\displaystyle
c_{n}^{(k)}=n!\underbrace{\int_{0}^{1}\cdots\int_{0}^{1}}_{k}\binom{t_{1}t_{2}\cdots
t_{k}}{n}\,dt_{1}dt_{2}\cdots dt_{k},$

Moreover, the exponential generating function of $c_{n}^{(k)}$ is given by

$\displaystyle\text{\rm
Lif}_{k}(\ln(1+t))=\sum_{n=0}^{\infty}c_{n}^{(k)}\frac{t^{n}}{n!},$

where $\text{\rm Lif}_{k}(t)=\sum_{n=0}^{\infty}\frac{t^{n}}{n!(n+1)^{k}}$ is
the $k$-th _polylogarithm factorial function_. Similarly, the _poly-Cauchy
numbers of the second kind_ are defined by

$\displaystyle\hat{c}_{n}^{(k)}=n!\underbrace{\int_{0}^{1}\cdots\int_{0}^{1}}_{k}\binom{-t_{1}t_{2}\cdots
t_{k}}{n}\,dt_{1}\cdots dt_{k},$

and the exponential generating function of $\hat{c}_{n}^{(k)}$ is given by

$\displaystyle\text{\rm
Lif}_{k}(-\ln(1+t))=\sum_{n=0}^{\infty}\hat{c}_{n}^{(k)}\frac{t^{n}}{n!},\quad(k\in{\mathbb{Z}}).$

Notice that the above generating functions have a meaning as a formal power
series even if $k$ is non-positive. Therefore, the poly Cauchy numbers of both
kinds can be defined also for negative $k$. Poly-Cauchy numbers of the first
kind have the explicit formula

$\displaystyle
c_{n}^{(k)}=(-1)^{n}\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\frac{(-1)^{m}}{(m+1)^{k}},$

where $\genfrac{[}{]}{0.0pt}{}{n}{m}$ denotes the unsigned Stirling numbers of
the first kind that counts the number of permutations of
$[n]:=\\{1,2,\ldots,n\\}$ into $m$ non-empty cycles, and can algebraically
defined for instance by the following identity:

$\displaystyle\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}x^{m}=x(x+1)\cdots(x+n-1).$

Poly-Cauchy numbers of the second kind have the explicit formula

$\displaystyle\hat{c}_{n}^{(k)}=(-1)^{n}\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\frac{1}{(m+1)^{k}}.$

For more properties about these numbers see for example [8, 11, 12, 13].

In the literature, along the theory of poly-Bernoulli numbers and polynomials,
the (analytical) theory of poly-Cauchy numbers were also developed, including
several identities and generalizations (polynomials, $q$-parameters) etc.

We are interested from the combinatorial point of view in poly-Cauchy numbers
of the second kind with negative $k$-indices. In this case, these numbers are
clearly integers. However, one notice that we have negative and positive
integers as well, so actually $(-1)^{n}\hat{c}_{n}^{(-k)}$ are positive
integers. We give first a combinatorial interpretation for these numbers. For
the sake of simplicity, let us denote these numbers by $\hat{c}_{n,k}$. Table
1 shows the first few values of the sequence $\hat{c}_{n,k}$.

$n\backslash k$ | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
0 | 1 | 1 | 1 | 1 | 1 | 1
1 | 1 | 2 | 4 | 8 | 16 | 32
2 | 2 | 5 | 13 | 35 | 97 | 275
3 | 6 | 17 | 51 | 161 | 531 | 1817
4 | 24 | 74 | 244 | 854 | 3148 | 12134
Table 1. The first values of the sequence $\hat{c}_{n,k}$.

##  2\. Poly-Cauchy permutations

In this section we introduce a new family of permutations enumerated by the
sequence $\hat{c}_{n,k}$. First we recall some well-known facts about
permutations. Permutations can be defined and seen from different point of
views, as a map, as an arrangement, as a product of cycles, etc. It is useful
to switch between these point of views, however it is always important to be
conscious of the particular approach that is used in an argument. In our case
cycles will play the crucial role.

Any permutation is the product of cycles, and cycles can be recorded uniquely:
we write the largest element of each cycle first and we arrange the cycles in
increasing order of their first elements. This representation is called
_canonical cycle notation_.

On the other hand, considering a permutation as a map,
$\pi:[n]\rightarrow[n]$, $\pi_{i}=\pi(i)$ each permutation can be written in
one-line notation, $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$. There is a well-known
bijection between permutations of $[n]$ written in cycle notation and written
in one-line-notation, which we recall now. We say that $\pi_{i}$ is a _left-
to-right maximum_ if, for all $k<i$, we have $\pi_{k}<\pi_{i}$. For example,
the permutation $3261457$ has three left-to-right maxima. These are the
entries $3,6$, and $7$. Let $\pi$ be a permutation of $n$ elements written in
canonical cycle notation, and let $\pi^{\prime}$ be the permutation written in
the one-line notation that is obtained from $\pi$ by omitting all parentheses.
Notice that the canonical cycle notation can be obtained from the left-to-
right maxima of the permutation.

######  Definition 1.

Let $n$ and $k$ be non negative integers. A _$(n,k)$ -poly-Cauchy permutation_
is a permutation of $[n+k]$ with the following properties:

  * (A1)

each maximal contiguous substring whose support belongs to
$\\{n+1,n+2,\ldots,n+k\\}$ is increasing,

  * (A2)

the left-to-right maxima of the maximal contiguous substrings whose support
belongs to $\\{1,2,\ldots,n\\}$ are increasing from left to right, when
“reading” the whole permutation.

######  Example 2.

A $(9,6)$-poly-Cauchy permutation is

$\displaystyle\pi=11-13-6-1-2-15-7-4-8-10-12-14-9-5-3.$

We introduce now some terminology and notation. Let $\mathcal{P}_{n,k}$ denote
the set of all $(n,k)$-poly-Cauchy permutations. For simplicity of notation we
use the notation of red elements for
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2},\ldots,{\color[rgb]{1,0,0}n}\\}$
and the notation of blue elements for
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2},\ldots,{\color[rgb]{0,0,1}k}\\}$
instead of the set $\\{n+1,n+2,\ldots,n+k\\}$ (which is essentially the same).
Given an $(n,k)$-poly-Cauchy permutation $\pi\in\mathcal{P}_{n,k}$ we will
denote the arrangement of the elements
$\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$, seeing itself as a
permutation of $[n]$ as ${\color[rgb]{1,0,0}\pi^{n}}$. Similarly, the
permutation/or ordered partition on the elements
$\\{{\color[rgb]{0,0,1}1},\ldots,{\color[rgb]{0,0,1}k}\\}$ as
${\color[rgb]{0,0,1}\pi^{k}}$.

######  Example 3.

The permutation given in Example 2 is in this notation
${\color[rgb]{0,0,1}24}{\color[rgb]{1,0,0}612}{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}748}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}953}$.
Maximal contiguous is the whole sequence of red elements and blue elements,
respectively. In the first permutation the blue sequences are
${\color[rgb]{0,0,1}24}$, ${\color[rgb]{0,0,1}6}$, ${\color[rgb]{0,0,1}135}$,
and the red sequences: ${\color[rgb]{1,0,0}\textbf{6}12}$,
${\color[rgb]{1,0,0}\textbf{7}4\textbf{8}}$,
${\color[rgb]{1,0,0}\textbf{9}53}$. In the blue sequences are the elements
increasingly ordered and the bold elements in the red sequences denote the
left-to-right maxima.
${\color[rgb]{1,0,0}\pi^{n}}={\color[rgb]{1,0,0}612748953}$ and
${\color[rgb]{0,0,1}\pi^{k}}={\color[rgb]{0,0,1}246135}$.

Note that the merging ${\color[rgb]{1,0,0}\pi^{n}}$ and
${\color[rgb]{0,0,1}\pi^{k}}$ happens so that a blue sequence is always
inserted before a left-to-right maxima of ${\color[rgb]{1,0,0}\pi^{n}}$. On
the other hand, a red sequence is always inserted after a descent top of
${\color[rgb]{0,0,1}\pi^{k}}$. (A _descent top_ of a permutation $\sigma$ is
$\sigma_{i}$, if $\sigma_{i}>\sigma_{i+1}$, i.e., an element followed by a
smaller element.)

As a visualization of a poly-Cauchy permutation we can use permutation
matrices. Recall that for a permutation $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$, its
permutation matrix is obtained by placing a dot in columns $i$ and row
$\pi_{i}$ from below. The poly-Cauchy permutations can be represented by a
permutation matrix as in Figure 1.

Figure 1. Decomposition of a poly-Cauchy permutation.

######  Example 4.

For $n=2$ and $k=1$ we have the $5$ permutations:

$\displaystyle{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}21},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}12},\quad{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}.$

For $n=2$ and $k=2$ we have the $13$ permutations:

$\displaystyle{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}12},\quad{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}21},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}2},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}2},\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}2},\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}$
$\displaystyle{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}12},\quad{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}12},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}2},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}2},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}1}.$

######  Theorem 5.

The $(n,k)$-poly-Cauchy permutations are enumerated by the sequence
$\hat{c}_{n,k}$.

###### Proof.

The $(n,k)$-poly-Cauchy permutations can be constructed by the following
procedure:

  1. (1)

First, permute the elements
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2},\ldots,{\color[rgb]{1,0,0}n}\\}$,
and write it into canonical cycle notation. This step will ensure the
condition (A2).

  2. (2)

Secondly, insert the elements of
$\\{{\color[rgb]{0,0,1}1},\ldots,{\color[rgb]{0,0,1}k}\\}$ in between the
cycles (before or after). Notice that we have $m+1$ spaces and some of them
may be left empty. The elements in between the cycles are written in
increasing order. This step will ensure the condition (A1).

This way we obtain an alternating sequence of cycles of
$\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$ and blocks of
$\\{{\color[rgb]{0,0,1}1},\ldots,{\color[rgb]{0,0,1}k}\\}$. It is clear that
the number of $(n,k)$-poly-Cauchy permutations constructed by this procedure
is given by

$\displaystyle\hat{c}_{n,k}=\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}(m+1)^{k}.$

In Figure 2 we give an example of this procedure for a $(9,6)$-poly-Cauchy
permutation.

Figure 2. Procedure to construct a poly-Cauchy permutation.

∎

We give some examples for some particular values of $n$ and $k$.

######  Example 6.

For $k=0$ we have $\hat{c}_{n,0}=n!$, since $(n,0)$-poly-Cauchy permutation is
simple a permutation of $[n]$.

######  Example 7.

For $n=1$ we have $\hat{c}_{1,k}=2^{k}$. To obtain a $(1,k)$-poly-Cauchy
permutation we insert ${\color[rgb]{1,0,0}1}$ in between two sets of the blue
elements (before or after),
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2},\ldots,{\color[rgb]{0,0,1}k}\\}$.
So, $|\mathcal{P}_{1,k}|$ is the number of choosing $i$ elements from
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2},\ldots,{\color[rgb]{0,0,1}k}\\}$
that are to the left of ${\color[rgb]{1,0,0}1}$, allowing $i$ to be $0$ and
$k$.

######  Example 8.

For $n=2$ we have $\hat{c}_{2,k}=2^{k}+3^{k}$. In this case, we have the sets
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2}\\}$ and
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2},\ldots,{\color[rgb]{0,0,1}k}\\}$,
so the number of ways we get such a permutation is to insert the string
${\color[rgb]{1,0,0}21}$ in between two sets of the blue elements, before or
after, so we have $2^{k}$ ways. We can also insert the strings
${\color[rgb]{1,0,0}1}$ and ${\color[rgb]{1,0,0}2}$ in between two sets
(possibly empty), so we have $3^{k}$ ways.

In the following theorems we will give combinatorial arguments of some
identities involving poly-Cauchy numbers, poly-Bernoulli numbers, Stirling
numbers of both kinds, and Eulerian numbers.

######  Theorem 9.

For non-negative $n$ and $k$ it holds

$\displaystyle\sum_{m=0}^{n}(-1)^{m}\genfrac{\\{}{\\}}{0.0pt}{}{n}{m}\hat{c}_{m,k}=(-1)^{n}(n+1)^{k}.$

###### Proof.

The right hand side is (besides the $(-1)$ factor) a poly-Cauchy permutation
where the elements $\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$
are in increasing order (with some blocks of the elements
$\\{{\color[rgb]{0,0,1}1},\ldots,{\color[rgb]{0,0,1}k}\\}$ in between, before
or after them), ${\color[rgb]{1,0,0}\pi^{n}}$ is the identity permutation. We
call such a permutation _id-poly-Cauchy permutation_.

We define an involution, $\phi$, to show that the left hand side counts id-
poly-Cauchy permutations of size $(n,k)$. The involution $\phi$ is defined on
the set of poly-Cauchy permutations with an extra structure on the red
elements. Partition the elements
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2},\ldots,{\color[rgb]{1,0,0}n}\\}$
into $m$ non-empty blocks (write the elements of a block into decreasing
order, and consider the greatest element of a block as its “representative”).
Then permute these blocks into a permutation with $j$ cycles, $j\leq m\leq n$.
Insert between the cycles of blocks the blue elements,
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2}\ldots,{\color[rgb]{0,0,1}k}\\}$.
in order to obtain a $(n,k)$-poly-Cauchy permutation with an extra structure
on the substrings of red elements (the blocks). Note $j$ is the number of
left-to-right maxima among the elements
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2},\ldots,{\color[rgb]{1,0,0}n}\\}$.

For example, one set partition of
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2},\ldots,{\color[rgb]{1,0,0}9}\\}$
into $m=5$ blocks is
$B_{1}=\\{{\color[rgb]{1,0,0}4},{\color[rgb]{1,0,0}2},{\color[rgb]{1,0,0}1}\\},B_{2}=\\{{\color[rgb]{1,0,0}5},{\color[rgb]{1,0,0}3}\\},B_{3}=\\{{\color[rgb]{1,0,0}6}\\},B_{4}=\\{{\color[rgb]{1,0,0}8},{\color[rgb]{1,0,0}7}\\},B_{5}=\\{{\color[rgb]{1,0,0}9}\\}$.
Now, we permute these five blocks to obtain a permutation in $j=3$ cycles. For
example, the permutation $(32)(4)(51)$ corresponds to the
$(B_{3},B_{2})(B_{4})(B_{5},B_{1})$. Finally, we insert the blue blocks, for
example we can insert the blocks
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}3}\\},\\{{\color[rgb]{0,0,1}2},{\color[rgb]{0,0,1}4},{\color[rgb]{0,0,1}5}\\},\\{{\color[rgb]{0,0,1}6}\\},$
and we obtain the $(9,6)$-poly-Cauchy permutation
${\color[rgb]{0,0,1}13}{\color[rgb]{1,0,0}653}{\color[rgb]{1,0,0}87}{\color[rgb]{0,0,1}245}{\color[rgb]{1,0,0}9421}{\color[rgb]{0,0,1}6}$.

If the number of cycles is $n$, that is $j=n$, that can happen only one way,
every block contains only one element and each cycle one block, hence, after
inserting the blocks of
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2}\ldots,{\color[rgb]{0,0,1}k}\\}$,
we obtain an id-poly-Cauchy permutations.

Otherwise, i.e., if the number of cycle is less than $n$, then there is at
least one cycle that contains at least two elements. Let $a$ be the greatest
element which is not alone in a cycle.

If $a$ is in a block alone, merge it with the block that follows it in the
cycle. If $a$ is not alone separate it into a block to be alone.

This way we defined an involution, $\phi$, between the set of poly-Cauchy
permutations with extra structure with even number of left-to-right maxima in
${\color[rgb]{1,0,0}\pi^{n}}$ and odd number of left-to-right maxima in
${\color[rgb]{1,0,0}\pi^{n}}$.

∎

Many formulas given in the literature are consequences of Theorem 9 and
modified forms of the involution $\phi$ can be used to provide combinatorial
proofs for them. For instance, Komatsu presents a formula in [14] (Theorem 3)
that can be seen as a generalization of Theorem 9. Let
$\genfrac{\\{}{\\}}{0.0pt}{}{n}{k}_{r}$ denote the $r$-Stirling numbers of the
second kind that count for instance the number of partitions of $[n]$ into $k$
non-empty blocks such that $\\{1,2,\ldots,r\\}$ are in distinct blocks. These
numbers were introduced by Broder [7].

######  Theorem 10 ([14], Theorem 3).

For non-negative $n$, $k$ and $r$, with $r\leq n$, it holds

(1)
$\displaystyle\sum_{j=r}^{n}(-1)^{j}\genfrac{\\{}{\\}}{0.0pt}{}{n}{j}_{r}\hat{c}_{j,k}=\sum_{\ell=1}^{r}\genfrac{[}{]}{0.0pt}{}{r}{\ell}(n-r+\ell+1)^{k}.$

###### Proof.

The idea of the proof is the same as in the proof of Theorem 9. Partition the
elements $\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$ into $j$
non-empty blocks such that the elements
$\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}r}\\}$ are in distinct
blocks. As usual, we call these elements _special elements_ and the remaining
elements, $\\{{\color[rgb]{1,0,0}r+1},\ldots,{\color[rgb]{1,0,0}n}\\}$, as
_non-special elements_. Arrange the blocks into $i$ cycles ($i\leq j\leq n$).
Merge the so obtained permutation with blocks of
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2}\ldots,{\color[rgb]{0,0,1}k}\\}$
in order to obtain a $(n,k)$-poly-Cauchy permutation with an extra structure
on the substrings of red elements (the blocks). As before, if the number of
cycles is $n$, every block contains only one element, and each cycle one
block, hence after merging with the blocks of
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2}\ldots,{\color[rgb]{0,0,1}k}\\}$
we obtain an id-poly-Cauchy permutations.

If $j\not=n$, there is at least one cycle that contains at least two elements.
Note that the involution $\phi$, we defined in the proof of Theorem 9 can not
be used in that form, since we can not merge blocks containing the special
elements. We will modify slightly the definition of $a$, the base element of
our involution, $\phi^{\prime}$. Let $a$ be the greatest non-special element
which is not alone in a cycle.

If such an $a$ exists, we can apply the involution $\phi$ based on this
element, i.e., if $a$ is in a block alone, merge it with the block that
follows it in the cycle. If $a$ is not alone separate it into a block to be
alone.

However, such an $a$ does not have to exist. If such an $a$ does not exist, it
means, all the non-special elements are in a distinct cycle, (and so distinct
blocks), while the special elements are in distinct blocks by definition but
not necessarily in distinct cycles. ${\color[rgb]{1,0,0}\pi^{n}}$ is a
permutation of the form:
${\color[rgb]{1,0,0}\pi^{n}}=(c_{1})(c_{2})\cdots(c_{\ell})(r+1)(r+2)\cdots(n)$,
where $\ell$ is the number of cycles into the special elements are ordered.
Note that these cycles contain only special elements (otherwise $a$ with the
required property would exist). The blue elements are inserted in the poly-
Cauchy permutation in between these cycles of ${\color[rgb]{1,0,0}\pi^{n}}$
(before or after).

The involution $\phi^{\prime}$ shows that the left hand side of the identity
(1) counts such poly-Cauchy permutations.

On the other hand, such poly-Cauchy permutations can be constructed by the
following procedure. First arrange the $r$ special elements into $\ell$
cycles, and take the non-special elements as fix points. Record this
permutation in canonical cycle notation and insert the blue elements $[k]$ in
between, before or after the cycles decoding this insertion by a word
$w=w_{1}w_{2}\cdots w_{k}$, where $w_{i}$ is the number of cycles to the left
of the element $i$. The number of ways of doing this is clearly given by the
formula of the right hand side of the Identity (1). ∎

Theorem 9 implies also the formula that connects poly-Cauchy numbers and poly-
Bernoulli numbers [16]. The _poly–Bernoulli numbers_ , denoted by
$B_{n}^{(k)}$, where $n$ is a positive integer and $k$ is an integer, are
defined by the following exponential generating function [9]

(2) $\sum_{n=0}^{\infty}B_{n}^{(k)}\frac{x^{n}}{n!}=\frac{\text{\rm
Li}_{k}(1-e^{-x})}{1-e^{-x}},$

where $\text{\rm Li}_{k}(z)=\sum_{i=1}^{\infty}\frac{z^{i}}{i^{k}}$ is the
$k$-th polylogarithm function. Note that for $k=1$ we recover the classical
Bernoulli numbers, that is, $B_{n}^{(1)}=(-1)^{n}B_{n}$, for $n\geq 0$, where
$B_{n}$ denotes the $n$-th Bernoulli number. Poly-Bernoulli numbers were
introduced by Kaneko in 1997 [9] as he noticed that the generating function of
the usual Bernoulli numbers can be generalized by using the polylogarithm
function. From the combinatorial point of view the array with negative $k$
indices are interesting, since these numbers are integers (see sequence
A099594 in [20]). Table 2 shows the first few values of the sequence
$B_{n}^{(k)}$.

$k\backslash n$ | 0 | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---|---
0 | 1 | 1 | 1 | 1 | 1 | 1
-1 | 1 | 2 | 4 | 8 | 16 | 32
-2 | 1 | 4 | 14 | 46 | 146 | 454
-3 | 1 | 8 | 46 | 230 | 1066 | 4718
-4 | 1 | 16 | 146 | 1066 | 6902 | 41506
-5 | 1 | 32 | 454 | 4718 | 41506 | 329462
Table 2. The first values of the sequence $B_{n}^{(k)}$.

The poly-Bernoulli numbers count several combinatorial objects (see for
example [1, 3, 4, 5, 6]), in particular count Callan permutations [2]. An
_$(n,k)$ –Callan permutation_ is a permutation of $[n+k]$ such that each
maximal contiguous substring whose support belongs to $\\{1,2,\ldots,n\\}$
(respectively $\\{n+1,n+2,\ldots,n+k\\}$) is increasing (respectively
decreasing). It is easy to see that an $(n,k)$-Callan permutation can be seen
as an alternating sequence of blocks of partitions of
$\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$ and
$\\{{\color[rgb]{0,0,1}1},{\color[rgb]{0,0,1}2},\ldots,{\color[rgb]{0,0,1}k}\\}$.

######  Theorem 11 ([16], Theorem 3.2).

For non-negative $n$ and $k$ it holds

$\displaystyle
B_{n}^{(-k)}=(-1)^{n}\sum_{\ell=1}^{n}\sum_{m=1}^{n}m!\genfrac{\\{}{\\}}{0.0pt}{}{n}{m}\genfrac{\\{}{\\}}{0.0pt}{}{m}{\ell}\hat{c}_{\ell}^{(-k)}.$

###### Proof.

Let us rewrite the identity as follow:

$\displaystyle
B_{n}^{(-k)}=(-1)^{n}\sum_{m=1}^{n}m!\genfrac{\\{}{\\}}{0.0pt}{}{n}{m}\sum_{\ell=1}^{m}(-1)^{\ell}\genfrac{\\{}{\\}}{0.0pt}{}{m}{\ell}\hat{c}_{\ell,k}.$

By Theorem 9 the inner sum equals to $(-1)^{m}(m+1)^{k}$, and we obtain the
classical formula of poly-Bernoulli numbers:

$\displaystyle
B_{n}^{(-k)}=\sum_{m=1}^{n}m!\genfrac{\\{}{\\}}{0.0pt}{}{n}{m}(-1)^{n+m}(m+1)^{k}.$

Combinatorially, by the proof of the Theorem 9 after applying the involution,
$\phi$, the inner sum
$\sum_{\ell=1}^{m}(-1)^{\ell}\genfrac{\\{}{\\}}{0.0pt}{}{m}{\ell}\hat{c}_{\ell,k}$
counts $(m,k)$-id-poly-Cauchy permutations. Now let $A_{m}$ be the set of
Callan permutations with at most $m$ different red blocks (blocks of elements
$\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$). We obtain from an
$(m,k)$-id-poly-Cauchy permutation an $(n,k)$-Callan permutation from $A_{m}$
as follows. Given an id-poly-Cauchy permutation, permute first the $m$ red
elements in $m!$ ways. Then partition
$\\{{\color[rgb]{1,0,0}1},\ldots,{\color[rgb]{1,0,0}n}\\}$ into $m$ non-empty
blocks,
${\color[rgb]{1,0,0}B_{1}},{\color[rgb]{1,0,0}B_{2}},\ldots,{\color[rgb]{1,0,0}B_{m}}$,
and replace the red element $i$ in the poly-Cauchy permutation by a block
${\color[rgb]{1,0,0}B_{i}}$. Applying the inclusion-exclusion principle
completes the proof. ∎

The other direction can be seen similarly combinatorially.

######  Theorem 12 ([16], Theorem 3.1).

For non-negative $n$ and $k$ it holds

$\displaystyle\hat{c}_{n}^{(-k)}=(-1)^{n}\sum_{\ell=1}^{n}\sum_{m=1}^{n}\frac{1}{m!}\genfrac{[}{]}{0.0pt}{}{n}{m}\genfrac{[}{]}{0.0pt}{}{m}{\ell}B_{\ell}^{(-k)}.$

###### Proof.

Take now a $(\ell,k)$-Callan permutation and a permutation of $[m]$ into
$\ell$ cycles. Replace each red element in the Callan permutation by a cycle.
If there are more cycles in a block take the product of that cycles and record
this way $m$ elements in between the blue blocks of the Callan permutation.
(So, the $m$ elements are not in cycles anymore, but create subsequences of a
permutation of $m$ with places in between.) (Note that if we ignore the blue
blocks, the red elements determine a permutation of $m$, and summing up on all
$\ell$, every permutation will occur.) Order the elements
$\\{{\color[rgb]{1,0,0}1},{\color[rgb]{1,0,0}2},\ldots,{\color[rgb]{1,0,0}n}\\}$
into $m$ cycles and replace each red element in our construction by a cycle in
the canonical order (first the cycle with the least greatest element and so
on). This way we obtain a poly-Cauchy permutation. ∎

######  Example 13.

We show the procedure in the proof along an example. Let $n=9$, $m=5$,
$\ell=3$, $k=6$. Let the $(\ell,k)$-Callan permutation be
${\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}23}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}24}$.
The permutation of $[m]$ into $\ell$ cycles $(1)(43)(52)$, and the permutation
of $[n]$ into $m$ cycles $(43)(5)(71)(82)(96)$.

$\displaystyle{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}23}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}24}\quad\rightarrow\quad{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}(43)(52)}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}(1)}{\color[rgb]{0,0,1}24}\quad\rightarrow\quad{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}5432}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}24}$
$\displaystyle{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}\emptyset\emptyset\emptyset\emptyset}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}\emptyset}{\color[rgb]{0,0,1}24}\quad\rightarrow\quad{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}4357182}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}96}{\color[rgb]{0,0,1}24}.$

Next we provide a combinatorial proof for the closed formula of poly-Cauchy
numbers.

######  Theorem 14.

For non-negative $n$ and $k$ it holds

(3)
$\displaystyle\hat{c}_{n,k}=\sum_{j=0}^{k}j!\genfrac{[}{]}{0.0pt}{}{n+1}{j+1}\genfrac{\\{}{\\}}{0.0pt}{}{k+1}{j+1}.$

###### Proof.

We construct the $(n,k)$-poly-Cauchy permutations as follows. Let
$\overline{K}$ be the set $[k]$ extended by a special element
${\color[rgb]{0,0,1}*}$. First partition the set $\overline{K}$ into $j+1$
non-empty blocks. Second, order the set $[n]$ into $\ell$ cycles in the
canonical cycle notation, with $j\leq\ell\leq n$. Then we choose $j$ of these
cycles to insert a blue ordinary block (blocks without the element
${\color[rgb]{0,0,1}*}$) directly before each cycle, so we have
$\ell(\ell-1)\cdots(\ell-j+1)=\binom{\ell}{j}j!$ options to insert and
organize these blocks. Finally, the extra block, that contains
${\color[rgb]{0,0,1}*}$ is inserted after the last red cycle, at the end of
the arrangement, and we delete the element ${\color[rgb]{0,0,1}*}$. So if the
extra block contains only ${\color[rgb]{0,0,1}*}$ our poly-Cauchy permutation
ends with a red element, if it contains also other elements, it ends with a
blue element. Therefore we have:

$\displaystyle\hat{c}_{n,k}=\sum_{j=0}^{k}\genfrac{\\{}{\\}}{0.0pt}{}{k+1}{j+1}\sum_{\ell=j}^{n}\genfrac{[}{]}{0.0pt}{}{n}{\ell}\binom{\ell}{j}j!=\sum_{j=0}^{k}j!\genfrac{\\{}{\\}}{0.0pt}{}{k+1}{j+1}\genfrac{[}{]}{0.0pt}{}{n+1}{j+1}.$

Notice that in the last equality we use the identity
$\sum_{\ell=j}^{n}\binom{\ell}{j}\genfrac{[}{]}{0.0pt}{}{n}{\ell}=\genfrac{[}{]}{0.0pt}{}{n+1}{j+1}$.
∎

In the following two theorems we give recurrence relations to calculate the
sequence $\hat{c}_{n,k}$.

######  Theorem 15.

For $n\geq 1$ and $k\geq 0$ we have

$\displaystyle\hat{c}_{n,k}=(n-1)\hat{c}_{n-1,k}+\sum_{i=0}^{k}\binom{k}{i}\hat{c}_{n-1,k-i}.$

###### Proof.

The greatest red element, $n$, is surely in the last cycle of the permutation
${\color[rgb]{1,0,0}\pi^{n}}$, but we consider the cases when it is the very
last red element and when it is followed by some other red elements
separately. An $(n,k)$-poly-Cauchy permutation where $n$ is the last red
element can be obtained the following way. First we choose $i$ blue elements
($i$ can be empty) in a block say ${\color[rgb]{0,0,1}B}$. We take a
$(n-1,k-i)$-poly-Cauchy permutation and extend it by the sequence of
${\color[rgb]{1,0,0}n}{\color[rgb]{0,0,1}B}$ at the end. This can be done in
$\sum_{i=0}^{k}\binom{k}{i}\hat{c}_{n-1,k-i}$ ways.

In order to show that $(n,k)$-poly-Cauchy permutations where $n$ is not the
last red element is $(n-1)\hat{c}_{n-1,k}$ we establish a bijection.

Given an $(n-1,k)$-poly-Cauchy permutation $\pi$ and a value $1\leq i\leq n-1$
we construct an $(n,k)$-poly-Cauchy permutation $\overline{\pi}$ where $n$ is
not the last element as follows. $\pi$ is a merging of $\pi^{n-1}$ and
$\pi^{k}$. Consider $\pi^{n-1}$ as the product of cycles. Insert $n$ before
the element $i$ in its cycle, to obtain $\overline{\pi}^{n}$. Merge now
$\overline{\pi}^{n}$ and $\pi^{k}$ again together. Note that we did not change
the places of where the blue elements are inserted, but we possible changed
the relative order of the red cycles, since the cycle containing $9$ we be
shifted to the end, and other cycles may shifted to the left by one. Since
each step can be reversed, this procedure is a bijection, which implies our
statement. ∎

######  Example 16.

We give an example for making the bijection in the previous proof clearer. Let
$\pi={\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}43}{\color[rgb]{0,0,1}24}{\color[rgb]{1,0,0}561}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}827}$
and $i=6$. The cycles of $\pi^{8}$ are $({\color[rgb]{1,0,0}43})$,
$({\color[rgb]{1,0,0}5})$, $({\color[rgb]{1,0,0}61})$ and
$({\color[rgb]{1,0,0}827})$. We insert ${\color[rgb]{1,0,0}9}$ after
${\color[rgb]{1,0,0}6}$ and obtain
$({\color[rgb]{1,0,0}61})\rightarrow({\color[rgb]{1,0,0}691})=({\color[rgb]{1,0,0}916})$.
After merging the cycles and blocks again we obtain
$\overline{\pi}={\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}43}{\color[rgb]{0,0,1}24}{\color[rgb]{1,0,0}5827}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}916}$.

######  Theorem 17.

For $n\geq 1$ and $k\geq 0$ we have

$\displaystyle\hat{c}_{n,k}=\sum_{i=0}^{n}\sum_{j=0}^{k}(n-1)_{i}\binom{k}{j}\hat{c}_{n-1-i,k-j}.$

###### Proof.

Let $j$ be the number of the last blue block (possibly empty) and $i$ be the
number of elements that the last red cycle contain besides the element $n$.
(In the standard cycle notation the last cycle necessarily contains $n$.) We
choose the elements for the block in $\binom{k}{j}$ ways and construct the
last cycle by arranging $i$ elements after $n$ in $\binom{n-1}{i}i!=(n-1)_{i}$
ways. From the remaining elements we construct a poly-Cauchy permutation. ∎

The _Eulerian numbers_ $\genfrac{\langle}{\rangle}{0.0pt}{}{n}{k}$ counts the
number of permutations $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$ with $k-1$ descents,
that is $k-1=|\\{i\in[n-1]:\pi_{i}>\pi_{i+1}\\}|$. Note that a permutation
$\pi$ of $[n]$ with $k-1$ descents is the union of $k$ increasing subsequences
of consecutive entries, also called _ascending runs_. For example, if
$\pi=258193647$, then $3,5$, and $7$ are the descents. Moreover, $\pi$ is the
union of the ascending runs: $258,19,36$, and $47$. In Theorem 18 we give a
combinatorial identity involving the Eulerian numbers and the sequence
$\hat{c}_{n,k}$.

######  Theorem 18.

For non-negative $n$ and $k$ it holds

$\displaystyle\hat{c}_{n,k}=\sum_{m=0}^{n}\sum_{i=0}^{m}\binom{k-i}{m-i}\genfrac{\langle}{\rangle}{0.0pt}{}{k}{i}\genfrac{[}{]}{0.0pt}{}{n+1}{m+1}.$

###### Proof.

We turn now our point of view a little over and consider the construction of a
poly-Cauchy permutation as inserting red cycles into a permutation of blue
elements, ${\color[rgb]{0,0,1}\pi^{k}}$. The properties of poly-Cauchy
permutations require that the ascending runs of $\pi^{k}$ are separated by a
red cycle. But it is not forbidden to insert cycles after an ascent, cutting
ascending runs this way into more pieces. Hence, the $(n,k)$-poly-Cauchy
permutations can be constructed by the following process. Take a permutation
of $[k]$ with $i$ ascending runs and mark $m-i$ ascents. Permute the red
elements into at least $m$ cycles, say $\ell$, and choose $m$ out of them.
Merge the two permutation in order to obtain a poly-Cauchy permutation by
inserting a chosen cycle after each ascending runs and marked ascents. ∎

##  3\. Poly-Cauchy polynomials of the second kind

This section introduces a combinatorial interpretation for the poly-Cauchy
polynomials. The poly-Cauchy polynomials of the second kind, denoted by
$\hat{c}_{n}^{k}(z)$, where introduced by Kamano and Komatsu [10] by using the
following analytical formula

$\displaystyle\hat{c}_{n}^{(k)}(z):=n!\underbrace{\int_{0}^{1}\cdots\int_{0}^{1}}_{k}\binom{-x_{1}x_{2}\cdots
x_{k}-z}{n}\,dx_{1}\,dx_{2}\cdots dx_{k}.$

The above definition is equivalent to the explicit formula

$\displaystyle\hat{c}_{n}^{k}(z)=(-1)^{n}\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\sum_{i=0}^{m}\binom{m}{i}\frac{(-z)^{i}}{(m-i+1)^{k}}.$

We consider poly-Cauchy polynomials of the second kind without negative
$k$-indices and ignore the negative sign, i.e.,

(4)
$\displaystyle\hat{c}_{n,k}(z):=\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}(m-i+1)^{k}z^{i}$

We define _partial poly-Cauchy permutations_ as a pair $P=(\pi,\sigma)$, where
the reduction of $\pi$ on the red elements is a partial permutation of $[n]$
(not all elements of $[n]$ are included) and $\sigma$ is a permutation of the
remaining elements of $[n]$. Further, we define the weight of a partial poly-
Cauchy permutation, $w(P)=w(\pi,\sigma)$ as the number of cycles in the
permutation $\sigma$.

######  Example 19.

The weight of the partial poly-Cauchy permutation
$({\color[rgb]{0,0,1}24}{\color[rgb]{1,0,0}61}{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}78}{\color[rgb]{0,0,1}135}{\color[rgb]{1,0,0}93},{\color[rgb]{1,0,0}(24)(5)})$
is $2$.

Let $\mathcal{PP}_{n,k}$ denote the set of partial poly-Cauchy permutations.

######  Theorem 20.

We have

$\displaystyle\sum_{P\in\mathcal{PP}_{n,k}}(-z)^{w(P)}=\hat{c}_{n,k}(z).$

###### Proof.

The sum is clearly equal to the formula (4) according to our previous
considerations. ∎

Recall the well-known relation between the falling factorial
$(x)_{n}=x(x-1)\cdots(x-n+1)$ and the (signed) Stirling number of the first
kind, $s(n,k)$:

$\displaystyle(x)_{n}=\sum_{k=0}^{n}s(n,k)x^{k}.$

From the combinatorial point of view this identity expresses that if we weight
a permutation $\pi$ with the number of its cycles, i.e., $w(\pi)=\\#\,\mbox{of
cycles}$, we have

$(-1)^{n}(x)_{n}=\sum_{\pi\in S_{n}}(-x)^{w(\pi)},$

where $S_{n}$ denotes as usual the set of permutations of $[n]$. The following
theorem is based on this classical result.

######  Theorem 21 ([17], Theorem 7).

For non-negative $n$ and $k$ it holds

(5)
$\displaystyle\hat{c}_{n}^{(-k)}(z)=\sum_{m=0}^{n}\binom{n}{m}\hat{c}_{n-m}^{(-k)}(z)_{m}.$

###### Proof.

Let $m$ be the number of elements that are contained in $\sigma$ in the
partial poly-Cauchy permutation $P=(\pi,\sigma)$. Choose these $m$ elements in
$\binom{n}{m}$ ways and construct $\pi$ from the remaining elements in
$\hat{c}_{n-m,k}$ ways. Hence, we have

$\displaystyle\sum_{P\in\mathcal{PP}_{n,k}}(-z)^{w(P)}=\sum_{m=0}^{n}\binom{n}{m}\hat{c}_{n-m,k}(-1)^{m}(z)_{m}.$

Since $\hat{c}_{n-m,k}=(-1)^{n-m}\hat{c}_{n-m}^{(-k)}$, the theorem follows. ∎

The theorems proven in the previous section can be generalized easily to
partial poly-Cauchy permutations, and hence to poly-Cauchy polynomials. As an
example we present the combinatorial proof for the generalization of Theorem
9.

######  Theorem 22 ([10], Theorem 4).

For non-negative $n$ and $k$ it holds

$\displaystyle\sum_{m=0}^{n}(-1)^{m}\genfrac{\\{}{\\}}{0.0pt}{}{n}{m}\hat{c}_{m,k}(z)=\sum_{i=0}^{n}\binom{n}{i}(-1)^{i}z^{i}(n-i+1)^{k}.$

###### Proof.

Applying the involution $\phi$ of the proof of Theorem 9 on the set of partial
poly-Cauchy permutations, $\mathcal{PP}$, we recognize that only such partial
poly-Cauchy permutations do not cancel in that the red elements are in
increasing order. This means now that $\sigma$ is also fixed as an identity
permutation on the elements that are contained there. So the weight of
$\sigma$ is simply $(-z)^{i}$, if $i$ is the size of $\sigma$. ∎

As we see the proof is straightforward, so we omit the proof of other
generalizations. Instead, we show combinatorially two identities that are
typical for polynomials. Moreover, in these proofs we introduce another
combinatorial interpretation of the poly-Cauchy polynomials (which arises also
very naturally).

Looking at the formula (5) we can give the combinatorial interpretation for
$z$ positive integers as follow. Consider now a poly-Cauchy permutation with
$z$ ordered boxes. Choose some elements of $[n]$ and put them into one of the
boxes and form from the remaining elements a poly-Cauchy permutation. We call
such a construction an _extended poly-Cauchy permutations_. Having this
picture in mind, the following two identities are immediate.

######  Theorem 23 ([17]).

We have

(6) $\displaystyle\hat{c}_{n,k}(x+1)=\hat{c}_{n,k}(x)+n\hat{c}_{n-1,k}(x).$

###### Proof.

The left hand side counts extended poly-Cauchy permutations with $x+1$ boxes.
There are two cases, the last box contains an element, or not. If the last box
is empty, we can delete it and the number of such extended permutations is
just $\hat{c}_{n,k}(x)$. If the last box contains any of the $n$ elements
(that can be chosen in $n$ ways) the remaining $n-1$ elements create with the
$k$ elements an extended poly-Cauchy permutation with $x$ boxes. ∎

######  Theorem 24 ([17], Eq. (33)).

(7)
$\displaystyle\hat{c}_{n,k}(x+y)=\sum_{j=0}^{n}\binom{n}{j}\hat{c}_{j,k}(x)(y)_{n-j}$

###### Proof.

The left hand side counts extended poly-Cauchy permutations with $x+y$ boxes.
We obtain such an object by choosing $j$ elements out of $[n]$ from that we
construct an extended poly-Cauchy permutation with $x$ boxes, and we put the
remaining $n-j$ elements into the remaining $y$ boxes. This construction
corresponds to the right hand side. ∎

##  4\. Other generalizations

In this section we recall some of the generalizations of poly-Bernoulli
numbers and possible extensions of our combinatorial model in these
directions.

###  4.1. Shifted poly-Cauchy numbers

Let $\alpha$ be a positive real number. The shifted poly-Cauchy numbers of the
second kind have the explicit formula ([19])

$\displaystyle\hat{c}_{n,\alpha}^{k}:=(-1)^{n}\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\frac{1}{(m+\alpha)^{k}}.$

Let us define the objects _augmented poly-Cauchy permutations_. Such a
permutation is a poly-Cauchy permutation ending with a red element augmented
with $\alpha$ boxes at the end. Into the boxes we can place some blue
elements, boxes may be empty. An example with $\alpha=3$ is given below. The
boxes are indicated with $\alpha-1$ bars.

$\displaystyle{\color[rgb]{0,0,1}49}{\color[rgb]{1,0,0}612}{\color[rgb]{0,0,1}6}{\color[rgb]{1,0,0}748}{\color[rgb]{0,0,1}13}{\color[rgb]{1,0,0}953}||{\color[rgb]{0,0,1}27}|{\color[rgb]{0,0,1}58}.$

######  Theorem 25.

The $(n,k)$ augmented poly-Cauchy permutations are enumerated by the shifted
poly-Cauchy numbers,
$\hat{c}_{n,k,\alpha}=\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}(m+\alpha)^{k}$.

###### Proof.

The difference to the base case is that the possible places where blue
elements can be inserted are augmented by $\alpha-1$ bars. In a poly-Cauchy
permutation blue elements can be inserted between (before or after) red
cycles. Hence, there are now $m+\alpha$ possibilities, when we consider a red
permutation with $m$ cycles. ∎

A closed formula of the shifted poly-Cauchy numbers, the generalization of
Theorem 14, can be shown combinatorially as follow.

######  Theorem 26 ([19], Theorem 10).

For $n$, $k$, and $\alpha$ non-negative integers it holds

$\displaystyle\hat{c}_{n,k,\alpha}=\sum_{i=0}^{k}\sum_{j=0}^{i}j!\genfrac{[}{]}{0.0pt}{}{n+1}{j+1}\binom{k}{i}\genfrac{\\{}{\\}}{0.0pt}{}{i}{j}\alpha^{k-i}.$

###### Proof.

Let $k-i$ be the number of blue elements in the boxes. We choose these
elements in $\binom{k}{i}$ ways and put them into the boxes in $\alpha^{k-i}$
ways. To the left of the boxes there is a poly-Cauchy permutation on the red
elements $[n]$, and blue elements $[k]$, such that the last element is red.
The argument of Theorem 14 has to be a slightly modified to take the type of
the last element into account. Namely, we do not need the extra block, so we
do not extend the blue element set now with ${\color[rgb]{0,0,1}*}$. We take a
partition of the $i$ blue elements into $j$ blocks in
$\genfrac{\\{}{\\}}{0.0pt}{}{i}{j}$ ways and insert each block directly
_before_ the chosen cycles. ∎

###  4.2. Incomplete poly-Cauchy numbers of the second kind

The incomplete poly-Cauchy numbers of the second kind have the explicit
formula [15]

$\displaystyle\hat{c}_{n,\leq
m}^{k}:=(-1)^{n}\sum_{i=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{i}_{\leq
m}\frac{1}{(i+1)^{k}},$

where $\genfrac{[}{]}{0.0pt}{}{n}{k}_{\leq m}$ denotes the restricted Stirling
numbers of the first kind. This sequence counts the number of permutations on
$n$ elements with $k$ cycles that each cycle contains at most $m$ items. From
a similar argument we have that $\hat{c}_{n,k,\leq
m}=\sum_{i=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{i}_{\leq m}(i+1)^{k}$ counts the
number of poly-Cauchy permutations of $[n+k]$, such that the size of each
cycle in the cycle decomposition of the permutation whose support belongs to
$\\{1,2,\ldots,n\\}$ is at most $m$.

######  Example 27.

For $n=3$ and $k=1$, $m=2$ we have the following restricted poly-Cauchy
permutations:

$\displaystyle{\color[rgb]{1,0,0}123}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}3},\quad{\color[rgb]{1,0,0}132}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}23},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}32},\quad{\color[rgb]{1,0,0}213}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}3}$
$\displaystyle{\color[rgb]{1,0,0}231}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}31},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}123},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}132},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}213},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}231}$

So, $\hat{c}_{3,1,\leq 2}=13$.

The associated poly-Cauchy numbers of the second kind have the explicit
formula

$\displaystyle\hat{c}_{n,\leq
m}^{k}:=(-1)^{n}\sum_{i=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{i}_{\geq
m}\frac{1}{(i+1)^{k}},$

where $\genfrac{[}{]}{0.0pt}{}{n}{k}_{\geq m}$ denotes the associated Stirling
numbers of the first kind. This sequence counts the number of permutations on
$n$ elements with $k$ cycles with the restriction that each cycle contains at
least $m$ items. So, the sequence $\hat{c}_{n,k,\geq
m}:=\sum_{i=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{i}_{\geq m}(i+1)^{k}$ counts the
number of poly-Cauchy permutations of $[n+k]$, such that the size of each
cycle in the cycle decomposition of the permutation whose support belongs to
$\\{1,2,\ldots,n\\}$ is at least $m$.

######  Example 28.

For $n=3$ and $k=1$, $m=2$ we have the permutations

$\displaystyle{\color[rgb]{1,0,0}312}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{1,0,0}321}{\color[rgb]{0,0,1}1},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}312},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}321}.$

So, $\hat{c}_{3,1,\geq 2}=4$.

###  4.3. $q$-poly-Cauchy numbers

The $q$-poly-Cauchy numbers of the second kind have the explicit formula [12]

$\displaystyle\hat{c}_{n,q}^{(k)}:=(-1)^{n}\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\frac{q^{n-m}}{(m+1)^{k}}.$

It is clear that the sequence
$\hat{c}_{n,k}(q):=\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}q^{n-m}(m+1)^{k}$
counts the number of poly-Cauchy permutations of $[n+k]$ such that the non
left-to-right maxima of $\pi^{n}$ are colored by one of $q$ colors.

######  Example 29.

For $n=2$ and $k=2$ we have the permutations

$\displaystyle{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}12}\to
1,\quad{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}21}\to
q,\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}2}\to
1,\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}2}\to
q,\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}1}\to
1,\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}1}\to
q,\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}2}\to
1$
$\displaystyle{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}\to
1,\quad{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}12}\to
1,\quad{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}12}\to
q,\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}2}\to
1,\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}2}\to
1,\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}1}\to
1$

So, $\hat{c}_{2,2}(q)=4q+9.$

###  4.4. $q$-poly-Cauchy permutations with a parameter

There is another generalization, $q$-poly-Cauchy numbers with a parameter
[13], given by the explicit formula

$\displaystyle\hat{c}_{n,\rho,q}^{(k)}=(-1)^{n}\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\frac{\rho^{n-m}}{[m+1]_{q}^{k}},$

whith $[n]_{q}=1+q+\cdots+q^{n-1}$. The expression with negative $k$ and
ignoring the sign, defined as
$\hat{c}_{n,k,\rho,q}=\sum_{m=0}^{n}\genfrac{[}{]}{0.0pt}{}{n}{m}\rho^{n-m}[m+1]_{q}^{k}$
counts poly-Cauchy permutations with some weight on both the red elements and
blue elements. As in the case of $q$-poly-Cauchy permutations we can color the
non left-to-right maxima of $\pi^{n}$ by one of $\rho$ colors. This notion is
extended by a weight on each blue elements, $b$. Namely, $w(b)=q^{\\#\mbox{red
cycles to the left of $b$}}$. The weight of the poly-Cauchy permutation is the
product of weights of all the elements. Formally, let $\mathcal{P}_{n,k}$
denote the set of poly-Cauchy permutations of $[n+k]$, and $\mu(\pi)$ the
number of non left-to-right maxima in $\pi^{n}$. Then we have

$\displaystyle\hat{c}_{n,k,\rho,q}=\sum_{\pi\in\mathcal{P}}\rho^{\mu(\pi)}\prod_{i=1}^{k}q^{w(n+i)}.$

######  Example 30.

For $n=2$ and $k=2$ the weight of the permutations are

$\displaystyle{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}12}\to
1,\quad{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}21}\to\rho,\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}2}\to
q^{2},\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}2}\to
q\rho,\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}1}\to
q^{2},\quad{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}1}\to
q\rho,\quad{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}2}\to
q$
$\displaystyle{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}\to
q,\quad{\color[rgb]{1,0,0}12}{\color[rgb]{0,0,1}12}\to
q^{4},\quad{\color[rgb]{1,0,0}21}{\color[rgb]{0,0,1}12}\to
q^{2}\rho,\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}12}{\color[rgb]{1,0,0}2}\to
q^{2},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}1}{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}2}\to
q^{3},\quad{\color[rgb]{1,0,0}1}{\color[rgb]{0,0,1}2}{\color[rgb]{1,0,0}2}{\color[rgb]{0,0,1}1}\to
q^{3}.$

So, $\hat{c}_{n,k,\rho,q}=\rho(1+2q+q^{2})+(1+2q+3q^{2}+2q^{3}+q^{4})$.

##  5\. Conclusion

In this paper we presented a combinatorial interpretation of poly-Cauchy
numbers of the second kind. We showed how this model can be extended to some
of the generalizations that were introduced in the literature on these
numbers. However, this paper on this topic is not even aimed to be complete.
One of our goal was to show the power of combinatorial thinking, proofs with
pictures.

In this section we list some open questions that would be interesting to
understand combinatorially.

  * 1.

We studied in this work only the poly-Cauchy numbers (and their
generalizations) of the second kind. The question arises naturally, is it
possible to give a similar interpretation of the poly-Cauchy of the first
kind? The relation between the two kinds of poly-Cauchy numbers is given for
instance by the following formula:

$\displaystyle(-1)^{n}\frac{c_{n}^{k}}{n!}=\sum_{m=1}^{n}\binom{n-1}{m-1}\frac{\hat{c}_{m}^{k}}{m!}.$

  * 2.

We did not present a combinatorial proof for all of the formulas that are
known, though we think most of the identities could be attacked using our
combinatorial interpretation. The interested reader can try to find
combinatorial proof for them. For example, recently, Komatsu [14] (Theorem 8)
showed an annihilation formula

$\displaystyle\sum_{\ell=0}^{k}\genfrac{\\{}{\\}}{0.0pt}{}{n+1}{n-\ell+1}_{n-k}\hat{c}_{n-\ell}^{(-k)}=0.$

  * 3.

There are also several interesting identities involving generalizations of the
poly-Cauchy numbers that have a combinatorial “flavour”. As an example, we
recall the expression that was given by Komatsu and Szalay [19] in their study
about the shifted poly-Cauchy numbers.

######  Theorem 31.

[19]

$\displaystyle\hat{c}_{n,\alpha}^{(-k)}=(-1)^{\alpha-1}\sum_{\mu=0}^{\alpha-1}Q_{\mu}(n,\alpha)\hat{c}_{n+\mu}^{(-k)},$

where

$\displaystyle
Q_{\mu}(n,\alpha)=\sum_{i=0}^{\alpha-\mu-1}\binom{\alpha-1}{i}\genfrac{\\{}{\\}}{0.0pt}{}{\alpha-i-1}{\mu}n^{i},\quad(0\leq\mu\leq\alpha-1).$

  * 4.

There are even more generalizations in the literature, as multi-poly-Cauchy
numbers and polynomials (cf. [18]).

  * 5.

It would be of course very interesting to find other combinatorial
interpretations related to these numbers.

## References

  * [1] B. Bényi, Advances in bijective combinatorics. PhD thesis, (2014), available at http://www.math.u-szeged.hu/phd/dreposit/phdtheses/benyi-beata-d.pdf.
  * [2] B. Bényi and P. Hajnal. Combinatorics of poly-Bernoulli numbers. Studia Sci. Math. Hungarica 52 (2015), 537–558.
  * [3] B. Bényi and P. Hajnal. Combinatorial properties of poly-Bernoulli relatives. Integers 17 (2017) A31, 1–26.
  * [4] B. Bényi and G. V. Nagy. Bijective enumerations of $\Gamma$-free matrices. Adv. in Appl. Math. 96 (2018) 195–215.
  * [5] B. Bényi and J. L. Ramírez. On $q$-poly-Bernoulli numbers arising from combinatorial interpretations. arXiv:1909.09949.
  * [6] C. Brewbaker. A combinatorial interpretation of the poly-Bernoulli numbers and two Fermat analogues. Integers 8 (2008) # A02, 1–9.
  * [7] A. Z. Broder. The $r$-Stirling numbers. Disc. Math. 49 (1984), 241–259.
  * [8] M. Cenkci and P. T. Young. Generalizations of poly-Bernoulli and poly-Cauchy numbers. Eur. J. Math. 1 (5) (2015), 799–828.
  * [9] M. Kaneko. Poly-Bernoulli numbers. J. Théor. Nombres Bordeaux 9 (1997), 221–228.
  * [10] K. Kamano and T. Komatsu. Poly-Cauchy polynomials. Mosc. J. Comb. Number Theory (2013) 3 (2) (2013), 61–87.
  * [11] T. Komatsu. Poly-Cauchy numbers. Kyushu J. Math. 67 (2013), 143–153.
  * [12] T. Komatsu. Poly-Cauchy numbers with a $q$ parameter. Ramanujan J. 31 (2013), 353–371.
  * [13] T. Komatsu. $q$-poly-Bernoulli numbers and $q$-poly-Cauchy numbers with a parameter by Jackson’s integrals. Indag. Math. 27 (2016), 100–111.
  * [14] T. Komatsu. Recurrence relations of poly-Cauchy numbers by the $r$-Stirling transform.
arXiv:2103.15291

  * [15] T. Komatsu. Incomplete poly-Cauchy numbers. Monatsh Math 180 (2016), 271–288.
  * [16] T. Komatsu and F. Luca. Some relationships between poly-Cauchy numbers and poly-Bernoulli numbers. Ann. Math. Inform. 41 (2013), 99–105.
  * [17] D. S. Kim and T. Kim. Poly-Cauchy numbers and polynomials of the second kind. Adv. Differ. Equ. 36 (2014).
  * [18] D. S. Kim, T. Kim, T. Komatsu, and S.-H Rim. Multi-poly-Cauchy polynomials, J. Comput. Anal. Appl. 18 (2015), 536–550.
  * [19] T. Komatsu and L. Szalay. Shifted poly-Cauchy numbers. Lith. Math. J. 54 (2) (2014), 166–181.
  * [20] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences, http://oeis.org/.