<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\DeclareMathOperator{\ddet}{ddet}
\DeclareMathOperator{\pper}{pper}

\newcommand{\Lah}[2]{\genfrac{\lfloor}{\rfloor}{0pt}{}{#1}{#2}}
\newcommand{\stirling}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Combinatorial Proofs of Some Stirling Number Convolution Formulas\\
}
\vskip 1cm
\large
Mark Shattuck\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN\\
USA\\
\href{mailto:mshattuc@utk.edu}{\tt mshattuc@utk.edu}\\
\end{center}


\vskip .2 in

\begin{abstract}
Recently, some new convolution formulas extending the orthogonality
of the Stirling numbers of the first and second kind were shown by
algebraic techniques.  The formulas involve sums of products of the two
Stirling numbers wherein the inner arguments vary while differing by a
prescribed amount and the outer arguments are fixed.  Here, we provide
combinatorial proofs of these formulas using direct enumeration and
sign-changing involutions.  Our arguments may be extended to establish
generalizations of the foregoing results in terms of the $r$-Stirling
numbers.
\end{abstract}

\section{Introduction}

Perhaps two of the most prevalent number sequences in enumerative
combinatorics are the Stirling numbers of the first and second kind,
which will be denoted here by $\stirling{n}{k}$ and $\Stirling{n}{k}$
respectively in accordance with \cite{Kn}.  See sequences \seqnum{A008275} and
\seqnum{A008277} in the {\it On-Line Encyclopedia of Integer Sequences}
\cite{Slo} and references contained therein.  Recall
that $\stirling{n}{k}$ counts the permutations of $[n]=\{1,\ldots,n\}$
having $k$ cycles (and is often referred to as the \emph{signless}
Stirling number of the first kind), whereas $\Stirling{n}{k}$ enumerates
the partitions of $[n]$ with $k$ blocks.  Both kinds of Stirling numbers
satisfy a variety of identities; see, for example, the texts \cite[Chap.\
V]{Com}, \cite[\S6.1]{Gr}, and \cite{Qu} as well as the recent papers
\cite{Cai,Chu,Guo,Sh}.

We will need the following further notation.  Define the generalized harmonic number $\sigma_{\lambda}(m;n)$ by
$$\sigma_{\lambda}(m;n)=\sum_{m \leq i_1&lt;\cdots&lt; i_\lambda \leq n}\prod_{j=1}^\lambda \frac{1}{i_j}, \qquad \lambda&gt;0,$$
with $\sigma_0(m;n)=1$.  Denote the Lah number (see \cite[\seqnum{A008297}]{Slo}) by $\Lah{n}{k}$, which counts the partitions of $[n]$ into $k$ \emph{contents-ordered} blocks (i.e., blocks in which the order of the elements contained therein matters).  Recall that $\Lah{n}{k}$ is given explicitly by $\Lah{n}{k}=\frac{n!}{k!}\binom{n-1}{k-1}$ for $1 \leq k \leq n$, which is also seen to hold for $k=0$ and all $n \geq 0$ if one adopts the convention $\binom{i}{-1}=\delta_{i,-1}$ for integers $i \geq -1$.

Chu \cite{Chu} considered the following general sums where $\lambda$ denotes an arbitrary integer:
\begin{equation}\label{Phi}
\Phi_{m,n}(\lambda)=\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}\Stirling{k}{m}
\end{equation}
and
\begin{equation}\label{Psi}
\Psi_{m,n}(\lambda)=\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}\Stirling{k}{m}(-1)^{n-k}.
\end{equation}
Note that the evaluations of \eqref{Phi} and \eqref{Psi} when $\lambda=0$ correspond to the well-known identities
$$\sum_{k=m}^n\stirling{n}{k}\Stirling{k}{m}=\Lah{n}{m}$$
and
$$\sum_{k=m}^n\stirling{n}{k}\Stirling{k}{m}(-1)^{n-k}=\delta_{m,n},$$
see, e.g., \cite[\S6.1]{Gr}.
Further, the evaluation of \eqref{Psi} when $\lambda=1$ is known and gives
$$\sum_{k=m}^{n-1}\stirling{n}{k+1}\Stirling{k}{m}(-1)^{n-k}=(-1)^{n-m}\frac{(n-1)!}{m!},$$
which corresponds to \cite[Identity~6.25]{Gr}.

The following general identities for $\Phi_{m,n}(\lambda)$ and $\Psi_{m,n}(\lambda)$ were established in \cite{Chu} by algebraic methods using a connection coefficient approach:
\begin{align}
\Phi_{m,n}(\lambda)&amp;=\sum_{j=m}^{n-\lambda}\frac{(n-1)!}{m!}\binom{j-1}{m-1}\sigma_{\lambda-1}(j+1;n-1), \quad \lambda&gt;0,\label{Phipos}\\
\Phi_{m,n}(\lambda)&amp;=\sum_{i=0}^{-\lambda}\sum_{j=0}^i\frac{(-1)^{\lambda+j}}{n^{\lambda+i}}\binom{-\lambda}{i}\Stirling{i}{j}\Lah{j+n}{m}, \quad \lambda&lt;0, \label{Phineg}
\end{align}
\begin{align}
\Psi_{m,n}(\lambda)&amp;=(-1)^{n-m}\frac{(n-1)!}{m!}\sigma_{\lambda-1}(m+1;n-1), \quad \lambda&gt;0, \label{Psipos}\\
\Psi_{m,n}(\lambda)&amp;=\sum_{i=0}^{-\lambda}\frac{(-1)^\lambda}{n^{\lambda+i}}\binom{-\lambda}{i}\Stirling{i}{m-n}, \quad \lambda&lt;0. \label{Psineg}
\end{align}
Throughout, one may assume $n,m \geq 0$ with $\lambda \in \mathbb{Z}$, where it is seen that the lower index of summation in the definitions of $\Phi_{m,n}(\lambda)$ and $\Psi_{m,n}(\lambda)$  may be replaced by $k=\max\{m,-\lambda\}$.  Note also that both $\Phi_{m,n}(\lambda)$ and $\Psi_{m,n}(\lambda)$ are zero if $n&lt;m+\lambda$; hence, one may assume further $n \geq m+\lambda$ to avoid trivialities.

In the next section, we provide combinatorial proofs of \eqref{Phipos}--\eqref{Psineg}.  We make use of direct enumeration to show \eqref{Phipos}, together with sign-changing involutions to prove \eqref{Phineg}--\eqref{Psineg}.  Our proofs may be extended to afford combinatorial explanations of some related recurrences from \cite{Chu} for $\Phi_{m,n}(\lambda)$ and $\Psi_{m,n}(\lambda)$.  In the third section, we generalize \eqref{Phipos}--\eqref{Psineg} to the $r$-Stirling numbers of the first and second kind, which are denoted by $\stirling{n}{k}_r$ and $\Stirling{n}{k}_r$.  See \cite{Br,Mer}, where these numbers were introduced, and \cite{NR} for a list of useful properties.

Recall that $\stirling{n}{k}_r$ enumerates the permutations of $[n+r]$ having $k+r$ cycles in which the elements of $[r]$ lie in distinct cycles, while $\Stirling{n}{k}_r$ counts partitions of $[n+r]$ with $k+r$ blocks in which the elements of $[r]$ belong to distinct blocks. Note that $\stirling{n}{k}_r$ and $\Stirling{n}{k}_r$ reduce respectively to $\stirling{n}{k}$ and
$\Stirling{n}{k}$ when $r=0$.  Using the combinatorial interpretation for the $r$-Stirling numbers, one may extend the arguments of the subsequent section and find formulas for the sums obtained by replacing $\stirling{n}{k+\lambda}$ and $\Stirling{k}{m}$ in \eqref{Phi} and \eqref{Psi} with $\stirling{n}{k+\lambda}_r$ and $\Stirling{k}{m}_s$ respectively for arbitrary non-negative $r$ and $s$. Our formulas will be seen to reduce to those given in \eqref{Phipos}--\eqref{Psineg} above in the case $r=s=0$.

\section{Combinatorial proofs}

In this section, we provide combinatorial explanations of formulas \eqref{Phipos}--\eqref{Psineg} above.\medskip

\begin{proof}[Proof of \eqref{Phipos}] We construct a set of configurations comprising the elements of $[n]$ and provide two different enumerations of this set.  Given $\lambda&gt;0$ and $m \leq k \leq n-\lambda$, first arrange the members of $[n]$ according to a permutation having $k+\lambda$ cycles $C_1,\ldots,C_{k+\lambda}$, where the smallest element is first in each cycle and cycles are ordered according to the size of their respective first elements.  We then arrange the first $k$ cycles $C_1,\ldots,C_k$ according to a partition having $m$ blocks, where cycles within a block are written in decreasing order of their first elements.  Note that one may then erase the pair of parentheses enclosing each cycle so that now cycle starters correspond to left-right minima within $m$ contents-ordered blocks.  The remaining $\lambda$ cycles $C_{k+1},\ldots,C_{k+\lambda}$ are set aside.  Let $\mathcal{A}_k=\mathcal{A}_k^{(m,n,\lambda)}$ denote the set of configurations of $[n]$ that arise in this manner for $m \leq k \leq n-\lambda$.  Define $\mathcal{A}=\mathcal{A}^{(m,n,\lambda)}$ by $\mathcal{A}=\cup_{k=m}^{n-\lambda}\mathcal{A}_k$.  Then it is seen that $\Phi_m(\lambda)$ gives the cardinality of $\mathcal{A}$.

We now enumerate members of $\mathcal{A}$ by considering the smallest element $j+1$ belonging to cycle $C_{k+1}$.  To do so, we arrange the elements of $[j]$ according to an arbitrary permutation (written using the one-line notation) and insert $m-1$ internal dividers in any of $\binom{j-1}{m-1}$ ways.  Then elements between consecutive dividers (or preceding the first or following the last divider) constitute the elements within one of $m$ (nonempty) contents-ordered blocks.  Since the ordering of the blocks themselves is immaterial, we divide by $m!$, and hence there are $\frac{j!}{m!}\binom{j-1}{m-1}=\Lah{j}{m}$ ways in which to arrange the members of $[j]$.  Further, the number of ways in which to insert the elements of $[j+2,n]$ so that exactly $\lambda-1$ additional cycles are created is given by
$$\frac{(n-1)!}{j!}\sum_{j+1\leq i_1&lt;\cdots&lt;i_{\lambda-1} \leq n-1}\prod_{j=1}^{\lambda-1}\frac{1}{i_j}=\frac{(n-1)!}{j!}\sigma_{\lambda-1}(j+1;n-1)$$
if $\lambda&gt;1$ (which also holds if $\lambda=1$ since $\sigma_0(j+1;n-1)=1$).  To see this, note that $i_1+1,\ldots,i_{\lambda-1}+1$, where $i_\ell$ is as in the preceding multi-sum, would correspond to the starters of cycles $C_{k+2},\ldots,C_{k+\lambda}$, respectively.  Hence, each factor $i_\ell$ for $1 \leq \ell \leq \lambda-1$ is ``missed'' in the product $(j+1)(j+2)\cdots(n-1)=\frac{(n-1)!}{j!}$.  Thus, for each $j \in [m,n-\lambda]$, there are $\Lah{j}{m}\cdot \frac{(n-1)!}{j!}\sigma_{\lambda-1}(j+1;n-1)=\frac{(n-1)!}{m!}\binom{j-1}{m-1}\sigma_{\lambda-1}(j+1;n-1)$  members of $\mathcal{A}_j$ and considering all possible $j$ completes the proof. \end{proof}

\begin{proof}[Proof of \eqref{Phineg}] Let $n,m \geq 0$ be fixed with $\lambda&lt;0$.  Given $0 \leq j \leq i \leq -\lambda$, let $\mathcal{B}_{i,j}$ denote the set of configurations obtained as follows.  Choose exactly $i$ of the elements of $I=[n+1,n-\lambda]$ and arrange them according to an ordinary partition with $j$ blocks.  We then arrange these $j$ blocks $B_1,\ldots,B_j$, together with the members of $[n]$, according to a Lah distribution having $m$ blocks. Then insert the $-\lambda-i$ unchosen elements of $I$ into this Lah distribution so that at the time of insertion each element is placed so that it directly precedes some member of $[n]$ (and not any of the blocks $B_\ell$ for $\ell \in [j]$). Further, if $S=\{s_1&gt;\cdots&gt;s_{-\lambda-i}\}$ denotes the set of elements to be inserted, then $s_1$ is to be added first directly prior to some member of $[n]$ within one of the $m$ blocks.  The element $s_2$ is to be added in the same way, where if $s_2$ is placed in the same slot as $s_1$ was, then $s_2$ is to follow $s_1$ (this ensures that $s_2$ is also inserted directly prior to some element of $[n]$).  The remaining elements $s_3,\ldots,s_{-\lambda-i}$ are then to be added sequentially in this same manner.  Then the absolute value of the generic summand in the formula on the right-hand side of \eqref{Phineg} is seen to give $|\mathcal{B}_{i,j}|$ for all $i$ and $j$.  Define the sign of a member of $\mathcal{B}_{i,j}$ to be $(-1)^{\lambda+j}$ and let $\mathcal{B}=\cup_{i=0}^{-\lambda}\cup_{j=0}^i\mathcal{B}_{i,j}$.  Then the right side of \eqref{Phineg} gives the sum of the signs of all members of $\mathcal{B}$.

To complete the proof, we define a sign-changing involution on $\mathcal{B}$.  To do so, we will need the following further definitions.  First, we will refer to the blocks of $\pi \in \mathcal{B}$ whose members themselves are either individual elements of $[n-\lambda]$ or blocks whose elements belong to $I$ as \emph{super-blocks}.  We will refer to an internal block consisting of members of $I$ within a super-block as a \emph{sub-block}. Note that each member of $\mathcal{B}_{i,j}$ contains exactly $j$ sub-blocks in all and each member of  $\mathcal{B}$ has exactly $m$ super-blocks, the contents of which we now describe in further detail.  By a \emph{free} element within a super-block $B$, we mean a member of $I$ not belonging to any of the sub-blocks lying within $B$.  Given $a \in [n]$, let $\mathcal{L}_a$ denote the (ordered) set consisting of free elements and/or sub-blocks occurring to the left of $a$ if $a$ is the leftmost member of $[n]$ lying within its super-block or between $a$ and the next member of $[n]$ to its left if not.  If $b$ is the rightmost member of $[n]$ in its super-block, then let $\mathcal{M}_b$ denote the collection of sub-blocks occurring to the right of $b$.  Note that since free elements are to precede directly elements of $[n]$, no free elements can occur to the right of $b$ since it is rightmost and thus $\mathcal{M}_b$ consists solely of sub-blocks.  Finally, let $\mathcal{N}_c$ for $c \in I$ denote the contents of a super-block of $\pi$ that contains no elements of $[n]$ and whose smallest element lying within one of the sub-blocks is $c$.  Note that $\mathcal{N}_c$, like $\mathcal{M}_b$, can contain no free elements.  Further, within a nonempty $\mathcal{L}_a$, the sub-blocks are followed by any free elements (in decreasing order). Given $b \in [n]$ or $c \in I$, let $\mathcal{M}_b$ be empty if $b$ is not the rightmost element of $[n]$ in its super-block and let $\mathcal{N}_c$ be empty if $c$ does not correspond to the smallest element lying within a sub-block of a super-block containing no elements of $[n]$.

Let $p$ denote the smallest index $j \in [n-\lambda]$ such that at least one of the following holds:
\begin{align*}
(i)&amp;~j \in [n], \text{ with } \mathcal{L}_j \text { nonempty},\\
(ii)&amp;~j\in [n] \text{ and } \mathcal{M}_j \text{ is nonempty, with } \mathcal{M}_j\neq \{a_1\},\ldots,\{a_k\} \text{ for some } k \geq 1,\\
(iii)&amp;~j\in I \text{ and } \mathcal{N}_j \text{ is nonempty, with } \mathcal{N}_j\neq \{a_1\},\ldots,\{a_k\} \text{ for some } k \geq 1,
\end{align*}
where $a_1&lt;\cdots&lt;a_k$ in (\emph{ii}) and (\emph{iii}).  If both (\emph{i}) and (\emph{ii}) apply to the smallest $j$ as described, then consider only (\emph{i}).

We now can define the involution on $\mathcal{B}$.  Given $p$ as specified above, let $K_1,\ldots,K_r$ denote the individual sub-blocks (in order, from left to right) contained within $\mathcal{L}_p$, $\mathcal{M}_p$ or $\mathcal{N}_p$, whichever is applicable.  Let $u$ be the smallest element in $K_1\cup\cdots\cup K_r$. If $K_1\neq\{u\}$, then either add $u$ to the block directly preceding it if $K_j=\{u\}$ for some $j \in [2,r]$ or remove $u$ from the non-singleton to which it currently belongs and add it back as a singleton to follow this block.  Note that this operation always reverses the sign.  If $K_1=\{u\}$, then consider $K_2,\ldots,K_r$ and look to move the smallest element of $K_2\cup\cdots\cup K_r$ as before, if possible.  We continue until some element within $K_1\cup \cdots \cup K_r$ has been moved, or we have that these blocks consist of singletons arranged in increasing order (which can only occur in scenario (\emph{i}) above).  If $p$ applies to a situation in (\emph{i}) in which $r \geq 1$ and $K_i=\{a_i\}$ for $i \in [r]$ with $a_1&lt;\cdots&lt;a_r$ (followed by any free elements), or in which $r=0$ and $\mathcal{L}_p=b_1\cdots b_s$, where the $b_i$ are free elements with $b_1&gt;\cdots&gt;b_s$ and $s \geq 1$, then we change the status of $m=\max\{a_1,\ldots,a_r,b_1,\ldots,b_s\}$.  Note that $m$ occurs either as $K_r=\{m\}$ or as $b_1=m$; thus, we may either erase the brackets enclosing $m$ and designate $m$ a free element if the former, or vice versa, if the latter.  This operation again reverses the sign and completes the pairing of all possible $\pi$  for which $\mathcal{L}_i$ is nonempty for some $i$.

Let $\mathcal{B}^*\subseteq \mathcal{B}$ denote the set of survivors of the involution above.  Then $\mathcal{B}^*$ comprises those configurations in which $\mathcal{L}_i$ is empty for all $i \in [n]$, with $\mathcal{M}_j$ and $\mathcal{N}_j$ consisting of singletons (possibly none) arranged in ascending order for all $j$.  Then each member of $\mathcal{B}^*$ has positive sign and $|\mathcal{B}^*|=\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}\Stirling{k}{m}$.  To realize this, first note that any left-right minima belonging to $[n]$ within a super-block of $\rho \in \mathcal{B}^*$ may be viewed as a cycle starter (in some permutation of $[n]$).  If we denote the number of these cycles by $k+\lambda$, then it is seen that there are $k$ objects altogether ($k+\lambda$ cycles and $-\lambda$ singleton sub-blocks) to be arranged in the $m$ super-blocks of $\rho$, wherein the members of $I$ (written as singleton blocks) within a super-block must occur in ascending order following any elements of $[n]$ which are arranged in cycles written in decreasing order.  Thus, given any permutation of $[n]$ with $k+\lambda$ cycles, there are $\Stirling{k}{m}$ ways in which to arrange the cycles as described together with the $-\lambda$ elements of $I$ so as to form a member of $\mathcal{B}^*$.  Considering all possible $k$ implies $|\mathcal{B}^*|$ is as stated and completes the proof. \end{proof}

\begin{proof}[Proof of \eqref{Psipos}] Given $\lambda&gt;0$ and $m \leq k \leq n-\lambda$, let $\mathcal{C}_k=\mathcal{C}_k^{(m,n,\lambda)}$ denote the set of configurations that are obtained by first arranging the elements of $[n]$ according to a permutation having $k+\lambda$ cycles expressed in standard form and then forming a partition with $m$ blocks using the first $k$ of these cycles.  Here, cycles are assumed to be ordered by the size of their respective smallest (= first) elements.  Define the sign of each member of $\mathcal{C}_k$ to be $(-1)^{n-k}$.  Let $\mathcal{C}=\mathcal{C}^{(m,n,\lambda)}$ be given by $\mathcal{C}=\cup_{k=m}^{n-\lambda}\mathcal{C}_k$.  Then $\Psi_{m,n}(\lambda)$ gives the sum of the signs of all members of $\mathcal{C}$.

We define an involution on $\mathcal{C}$ as follows.  Given $\pi \in \mathcal{C}$, identify the block $B$ of $\pi$ containing the smallest element of $[n]$ within its cycles out of all the blocks of $\pi$ that contain at least two elements of $[\ell]$ within their respective cycles, where $\ell+1$ denotes the first element of the $\lambda$-th largest cycle of $\pi$ (i.e., if $\pi \in \mathcal{C}_k$ for some $k$, then $\ell+1$ is the first element of the $(k+1)$-st cycle).  Let $a$ and $b$ where $a&lt;b$ denote the two smallest elements of $[\ell]$ lying within the cycles of $B$. If $a$ and $b$ occur in the same cycle as $(a\cdots b \cdots)$, then we break this cycle at $b$ to get $(a\cdots)$ and $(b\cdots)$, and vice versa, if $a$ and $b$ occur in different cycles of $B$.

This operation defines a sign-changing involution on all of $\mathcal{C}$ except for those members in which $B$ fails to exist, i.e., for members of $\mathcal{C}_m$ in which the $(m+1)$-st cycle has first element $m+1$.  Note that the elements of $[m]$ in these members of $\mathcal{C}_m$ all belong to different cycles, with each of these cycles constituting a singleton block within the partition of cycles.  Upon erasing the outer brackets enclosing these singleton blocks, it is seen that the set of survivors of the involution above are synonymous with permutations of $[n]$ having $\lambda+m$ cycles altogether wherein the elements of $[m+1]$ belong to distinct cycles, and hence it is enumerated by the $(m+1)$-Stirling number of the first kind $\stirling{n-m-1}{\lambda-1}_{m+1}$.  Furthermore, each survivor has sign $(-1)^{n-m}$. Upon considering the elements $i_j+1$, where $j \in [\lambda-1]$ and $i_j&lt;i_{j+1}$ for all $j$, that start the final $\lambda-1$ cycles, we have
$$\stirling{n-m-1}{\lambda-1}_{m+1}=\frac{(n-1)!}{m!}\sum_{m+1\leq i_1&lt;\cdots&lt;i_{\lambda-1}\leq n-1}\prod_{j=1}^{\lambda-1}\frac{1}{i_j},$$
which implies $\Psi_{m,n}(\lambda)=(-1)^{n-m}\frac{(n-1)!}{m!}\sigma_{\lambda-1}(m+1;n-1)$ as desired. \end{proof}

\begin{proof}[Proof of \eqref{Psineg}] Given $\lambda&lt;0$ and $\max\{m,-\lambda\} \leq k \leq n-\lambda$, let $\mathcal{D}_k=\mathcal{D}_k^{(m,n,\lambda)}$ denote the set of configurations of $[n-\lambda]$ obtained by first arranging the elements of $[n]$ according to a permutation having $k+\lambda$ cycles and then placing these cycles in an $m$-block partition, together with the elements of $I=[n+1,n-\lambda]$ (which do not go in cycles).  Define the sign of a member of $\mathcal{D}_k$ by $(-1)^{n-k}$ and denote the union of all $\mathcal{D}_k$ by $\mathcal{D}$.  Identify the block $B$ of $\pi \in \mathcal{D}$ that contains the smallest element of $[n]$ out of all the blocks of $\pi$ that contain at least two elements of $[n]$ within their cycles.  Applying to $\pi$ the involution from the proof of \eqref{Psipos} above using the block $B$, we may consider only those members of $\mathcal{D}$ whose cycles all have length one, with at most one cycle per block of the partition.

Thus, if $m&lt;n$, we have $\Psi_{m,n}(\lambda)=0$, since there would be no survivors of the involution, which agrees with \eqref{Psineg} in this case since $\Stirling{i}{m-n}=0$ for all $i \geq 0$ as $m-n&lt;0$.  If $m=n$, then each block of a survivor contains a single $1$-cycle $(i)$ for some $i \in [n]$, with $n^{-\lambda}$ choices concerning the placement of the elements of $I$ within the blocks of the $m$-partition.  Note that the sign of each survivor is $(-1)^{n-k}=(-1)^{\lambda}$ since $k=n-\lambda$ in order for every cycle to have length one.  Thus, we get $(-n)^{-\lambda}$ in this case which agrees with the formula when $m=n$.  If $m&gt;n$, first note that all cycles must again have length one with these cycles going in $n$ distinct blocks of the partition within a survivor of the involution.  Then we select $\binom{-\lambda}{i}$ members of $[n+1,n-\lambda]$ to comprise $m-n$ additional blocks, which can be effected in $\Stirling{i}{m-n}$ ways.  Finally, the remaining members of $I$ go in the blocks already containing the $1$-cycles, which can be achieved in $n^{-\lambda-i}=\frac{1}{n^{\lambda+i}}$ ways.  Considering all possible $i$, where $0 \leq i \leq -\lambda$, implies the formula in the case $m&gt;n$ and completes the proof of \eqref{Psineg}. \end{proof}

We conclude this section by providing combinatorial proofs of some related recurrences for $\Phi_{m,n}(\lambda)$ and $\Psi_{m,n}(\lambda)$ which were shown in \cite{Chu} by other methods.  Counting members of the set $\mathcal{A}$ from the proof of \eqref{Phipos} in another way yields the following recurrence for $\Phi_{m,n}(\lambda)$:
\begin{equation}\label{Phirec}
\Phi_{m,n}(\lambda)=\sum_{i=m+\lambda-1}^{n-1}\frac{(n-1)!}{i!}\Phi_{m,i}(\lambda-1), \quad \lambda&gt;0.
\end{equation}
\begin{proof}
One may assume $n\geq m+\lambda$, for otherwise both sides of \eqref{Phirec} are zero.  Consider the smallest element $i+1$ of the last cycle within a member of $\mathcal{A}^{(m,n,\lambda)}$, where $m+\lambda-1 \leq i \leq n-1$.  Then the elements of $[i]$ are arranged according to some member of $\mathcal{A}^{(m,i,\lambda-1)}$ with $i+1$ going in a new cycle by itself.  Elements of $[i+2,n]$ are then inserted sequentially so that each $x \in [i+2,n]$ directly follows some element of $[x-1]$ occurring in either one of the $m$ (contents-ordered) blocks or in one of the $\lambda$ cycles that are set aside.  Note that no $x$ can be placed at the very beginning of one of the $m$ blocks since this would create implicitly a new cycle with first element $x$ contradicting that $i+1$ was the smallest element of the last cycle.  Thus, there are $(i+1)(i+2)\cdots (n-1)=\frac{(n-1)!}{i!}$ ways in which to insert the elements of $[i+2,n]$ and considering all possible $i$ implies \eqref{Phirec}.
\end{proof}

The argument used to show \eqref{Psipos} can be extended to prove the following recurrence relations from \cite{Chu}
for $\Psi_{m,n}(\lambda)$ where $\lambda&gt;0$:
\begin{align}
\Psi_{m,n}(\lambda)&amp;=\sum_{i=m+1}^{n-\lambda+1}(-1)^{i-m}\frac{(i-1)!}{m!}\Psi_{i,n}(\lambda-1)\label{Psirec1}\\
&amp;=\sum_{i=m+\lambda-1}^{n-1}(-1)^{n-i}\frac{(n-1)!}{i!}\Psi_{m,i}(\lambda-1)\label{Psirec2}.
\end{align}
\begin{proof}
Note that one may assume $\lambda&gt;1$ in \eqref{Psirec1} and \eqref{Psirec2}, as they are seen to hold when $\lambda=1$ since $\Psi_{m,n}(1)=(-1)^{n-m}\frac{(n-1)!}{m!}$ and $\Psi_{i,n}(0)=\delta_{i,n}$.  By the proof of \eqref{Psipos}, we have $\Psi_{m,n}(\lambda)=(-1)^{n-m}\stirling{n-m-1}{\lambda-1}_{m+1}$.  Upon replacing $m$ by $m-1$ and $\lambda$ by $\lambda+1$ in \eqref{Psirec1} and \eqref{Psirec2}, one may then show equivalently
\begin{align}
\stirling{n-m}{\lambda}_m&amp;=\sum_{i=m}^{n-\lambda}\frac{(i-1)!}{(m-1)!}\stirling{n-i-1}{\lambda-1}_{i+1} \label{Psirec1a}\\
&amp;=\sum_{i=m+\lambda-1}^{n-1}\frac{(n-1)!}{i!}\stirling{i-m}{\lambda-1}_m.\label{Psirec2a}
\end{align}

Before proceeding with the proof of \eqref{Psirec1a}, let us introduce a couple of definitions which we will also make use of in the next section.  Permutations enumerated by the $r$-Stirling number $\stirling{n}{k}_r$ are called $r$-permutations and we will refer to a cycle containing a member of $[r]$ within an $r$-permutation as \emph{special}, with all other cycles being \emph{non-special}.  The same descriptors will also be used for the elements themselves of the sets $[r]$ and of $[r+1,n+r]$, respectively.  Analogous terminology can be applied to the $r$-partitions enumerated by $\Stirling{n}{k}_r$.  Assume that the smallest element is first in all cycles.  To show \eqref{Psirec1a}, we argue that the right side counts the permutations enumerated by $\stirling{n-m}{\lambda}_m$ according to the smallest element $i+1$ of the first non-special cycle where $m \leq i \leq n-\lambda$.  Note that there are $\frac{(i-1)!}{(m-1)!}$ choices regarding the placement of the elements of $[i]$  since the elements of $[m]$ belong to different cycles, with $i+1$ going in a new cycle by itself.  At this point, we may regard each of the $i+1$ elements already inserted as special (each starting its own respective cycle) when placing the elements of $[i+2,n]$.  Note that $\lambda-1$ additional non-special cycles must be created when these elements are placed since already one non-special cycle has been started.  Thus, there are $\stirling{n-i-1}{\lambda-1}_{i+1}$ possibilities concerning the placement of the elements of $[i+2,n]$ and considering all $i$ completes the proof of \eqref{Psirec1a}.  A similar proof applies to \eqref{Psirec2a}, where instead one considers the element $i+1$ starting the \emph{last} non-special cycle for some $i\in[m+\lambda-1,n-1]$. \end{proof}

\section{Generalization}
Given $r, s \geq 0$, let
\begin{equation}\label{genPhi}
\Phi_{m,n}^{(r,s)}(\lambda)=\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}_r\Stirling{k}{m}_s
\end{equation}
and
\begin{equation}\label{genPsi}
\Psi_{m,n}^{(r,s)}(\lambda)=\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}_r\Stirling{k}{m}_s(-1)^{n-k}.
\end{equation}
In this section, we find formulas for \eqref{genPhi} and \eqref{genPsi} which generalize those above corresponding to the case $r=s=0$.  Let $x^{\overline{m}}=x(x+1)\cdots(x+m-1)$ for a positive integer $m$, with $x^{\overline{0}}=1$. We first consider $\Phi_{m,n}^{(r,s)}(\lambda)$.

\begin{theorem}\label{Phigenth}
 We have
\begin{equation}\label{Phigenpos}
\Phi_{m,n}^{(r,s)}(\lambda)=\sum_{\ell=m+\lambda}^n\sum_{j=m}^{\ell-\lambda}\frac{(\ell-1)!r^{\overline{n-\ell}}}{m!}\binom{n}{\ell}\binom{j+s-1}{m+s-1}\sigma_{\lambda-1}(j+1;\ell-1), \quad \lambda&gt;0,
\end{equation}
and
\begin{equation}\label{Phigenneg}
\Phi_{m,n}^{(r,s)}(\lambda)=\sum_{\ell=0}^n\sum_{i=0}^{-\lambda}\sum_{j=0}^i\frac{(-1)^{\lambda+j}(\ell+j)!r^{\overline{n-\ell}}}{\ell^{\lambda+i}m!}\binom{n}{\ell}\binom{-\lambda}{i}\Stirling{i}{j}\binom{\ell+j+s-1}{m+s-1}, \quad \lambda&lt;0.
\end{equation}
\end{theorem}
\begin{proof}
To show \eqref{Phigenpos}, we first generalize the sets $\mathcal{A}_k$ and $\mathcal{A}$ from the proof of \eqref{Phipos} above.  Define $\mathcal{A}_k^{(r,s)}$ to be the extension of $\mathcal{A}_k$  obtained by replacing $[n]$ with $[n+r]$ and allowing some of the elements of $J=[r+1,n+r]$ to go in special cycles starting with elements of $[r]$ and then allowing some of the first $k$ non-special cycles to go in  $s$ special blocks when forming a partition of cycles according the some $s$-partition enumerated by $\Stirling{k}{m}_s$.  Let $\mathcal{A}^{(r,s)}=\cup_{k=m}^{n-\lambda}\mathcal{A}_k^{(r,s)}$, which extends the prior set $\mathcal{A}$. Note that $\Phi_{m,n}^{(r,s)}$ gives $|\mathcal{A}^{(r,s)}|$.  To count the members of $\mathcal{A}^{(r,s)}$ in another way, first suppose $n-\ell$ elements of $J$ are to go in the special cycles.  Then there are $\binom{n}{\ell}r^{\overline{n-\ell}}$ ways in which to choose and arrange these elements.  Let $U=\{u_1&lt;\cdots&lt;u_\ell\}$ denote the subset of $J$ consisting of the unchosen members.  Proceeding at this point in a manner analogous to the proof of \eqref{Phipos} above, suppose $u_{j+1}$ is the smallest element of the $(k+1)$-st non-special cycle within a member of $\mathcal{A}_k^{(r,s)}$ for some $k$.  Then members of $V=\{u_1,\ldots,u_j\}$ form the cycles which constitute the non-special elements in a partition enumerated by $\Stirling{k}{m}_s$. Since a special block within such a partition need not contain a non-special cycle, it follows that there are $\frac{j!}{m!}\binom{j+s-1}{m+s-1}$ ways in which to arrange the elements of $V$. Then $u_{j+1}$ starts a new cycle and the remaining elements of $U-V$ can be inserted into the current structure in $\frac{(\ell-1)!}{j!}\sigma_{\lambda-1}(j+1;\ell-1)$ ways.  Considering all possible $\ell$ and $j$ then gives
\eqref{Phigenpos}.

To show \eqref{Phigenneg}, we consider sets $\mathcal{B}_{i,j,\ell}^{(r,s)}$ of configurations $\pi$ that are obtained as follows.  First, pick $n-\ell$  elements of $J$ which are to be placed in $r$ special cycles starting with elements of $[r]$.  Next, form an ordinary $j$-block partition utilizing exactly $i$ elements chosen from $K=[n+r+1,n+r-\lambda]$.  Using the elements of $U$, where $U$ is as in the prior paragraph, together with the $j$ blocks, we form a partition having $m+s$ contents-ordered blocks where the first $s$ blocks are labeled and allowed to be empty and the last $m$ blocks are unlabeled and nonempty.  Finally, to obtain a configuration $\pi$, the $-\lambda-i$ unchosen members of $K$ are added to this partition in decreasing order of size in such a way that each one is inserted directly preceding an element of $U$.  Let $\mathcal{B}^{(r,s)}$ denote the union of all possible $\mathcal{B}_{i,j,\ell}^{(r,s)}$ and define the sign of $\pi \in \mathcal{B}_{i,j,\ell}^{(r,s)}$ by $(-1)^{\lambda+j}$.  Then one may verify that the right side of \eqref{Phigenneg} gives the sum of the signs of all members of $\mathcal{B}^{(r,s)}$.  Apply now the involution used in the proof of \eqref{Phineg} above (considering also the contents of the $s$ labeled blocks above, if needed).  Then the set $L$ of survivors is as before, but with elements of $U$ in place of $[n]$ and where $s$ additional labeled super-blocks may contain sub-blocks and/or members of $U$.  Let $p$ denote the number of left-right minima corresponding to elements of $U$ within all the super-blocks of a member of $L$.  Then there are $\Stirling{k}{m}_s$ ways in which to arrange the elements of $U$ and $K$ within such a member of $L$, where $k=p-\lambda$.  Further, taking into account the placement of the elements of $J-U$ as well, there are $\stirling{n}{p}_r$ ways to arrange the elements of $J$.  Note that each member of $L$ has positive sign as $i=j=-\lambda$ is required.  Considering all possible $p$, it is seen that the cardinality of $L$ is given by $\Phi_{m,n}^{(r,s)}$, which completes the proof.
\end{proof}

Taking $r=0$ or $s=0$, for example, in \eqref{Phigenpos} gives identities for $\lambda&gt;0$ such as
$$\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}\Stirling{k}{m}_r=\sum_{j=m}^{n-\lambda}\frac{(n-1)!}{m!}\binom{j+r-1}{m+r-1}\sigma_{\lambda-1}(j+1;n-1)$$
and
$$\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}_r\Stirling{k}{m}=\sum_{\ell=m+\lambda}^n\sum_{j=m}^{\ell-\lambda}\frac{(\ell-1)!r^{\overline{n-\ell}}}{m!}\binom{n}{\ell}\binom{j-1}{m-1}\sigma_{\lambda-1}(j+1;\ell-1).$$
Note that letting $r=0$ in either of these formulas recovers \eqref{Phipos}.  Taking $\lambda=-1$ in \eqref{Phigenneg} yields
$$\sum_{k=m}^{n+1}\stirling{n}{k-1}_r\Stirling{k}{m}_s=\sum_{\ell=0}^n\frac{\ell!r^{\overline{n-\ell}}}{m!}\binom{n}{\ell}\left((\ell+1)\binom{\ell+s}{m+s-1}-\ell\binom{\ell+s-1}{m+s-1}\right).$$

There are the following comparable formulas for $\Psi_{m,n}^{(r,s)}(\lambda)$.

\begin{theorem}\label{Psigenth}
We have
\begin{equation}\label{Psigenpos}
\Psi_{m,n}^{(r,s)}(\lambda)=\sum_{i=0}^u\sum_{j=0}^{u-i}\frac{(-1)^{n-m-j}(n-i-1)!r^{\overline{i}}}{m!}\binom{n}{i}\binom{s}{j}\sigma_{\lambda-1}(m+j+1;n-i-1), \quad \lambda&gt;0,
\end{equation}
and
\begin{equation}\label{Psigenneg}
\Psi_{m,n}^{(r,s)}(\lambda)=\sum_{i=0}^n\sum_{j=0}^{n-i}\sum_{\ell=0}^{-\lambda}\frac{(-1)^{\lambda+i}j!r^{\overline{i}}}{(v_{i,j}+s)^{\lambda+\ell}}\binom{n}{i}\binom{s}{j}\binom{n-i}{j}\binom{-\lambda}{\ell}\Stirling{\ell}{m-v_{i,j}}, \quad \lambda&lt;0,
\end{equation}
where $u:=n-m-\lambda$ and $v_{i,j}:=n-i-j$.
\end{theorem}
\begin{proof}
To show \eqref{Psigenpos}, let $\mathcal{C}_k^{(r,s)}$ be obtained by first forming $r$-permutations of $[n+r]$ having $k+\lambda$ non-special cycles and then arranging the first $k$ non-special cycles according to an $s$-partition having $m$ non-special blocks.  Let members of $\mathcal{C}_k^{(r,s)}$ have sign $(-1)^{n-k}$ and $\mathcal{C}^{(r,s)}=\cup_{k=m}^{n-\lambda}\mathcal{C}_k^{(r,s)}$.  Then $\Psi_{m,n}^{(r,s)}$ gives the sum of the signs of all members of $\mathcal{C}^{(r,s)}$.  Applying the involution used in the proof of \eqref{Psipos} above (considering also any cycles placed in the $s$ special blocks, if necessary) implies that the set $M$ of survivors consists of those members of $\mathcal{C}^{(r,s)}$ in which $k=m+j$ for some $0 \leq j \leq s$  wherein the $k+1$ smallest members of $J$ belonging to non-special cycles each start their own cycle, with the first $k$ of these cycles lying in different blocks of the $s$-partition.  If $i$ denotes the number of members of $J$ going in special cycles within a member of $M$, then we have $j \leq u-i$ and there are $\frac{(n-i-1)!}{(m+j)!}\sigma_{\lambda-1}(m+j+1;n-i-1)$ ways in which to arrange those members of $J$ lying in non-special cycles but not starting one of the first $k+1$ non-special cycles.  Further, there are $\binom{m+j}{j}\binom{s}{j}j!$ ways to choose and then arrange the cycle starters of the cycles that go in the special blocks within a member of $M$.  Upon considering all possible values of $i$ and $j$, the right side of \eqref{Psigenpos} is seen to give the sum of the signs of members of $M$.

To show \eqref{Psigenneg}, we form the set $\mathcal{D}_k^{(r,s)}$ consisting of configurations obtained by first arranging the elements of $[n+r]$ according to an $r$-permutation having $k+\lambda$ non-special cycles and then arranging these non-special cycles, together with the elements of $K$, according to an $s$-partition of size $k+s$ having $m+s$ blocks.  Define the sign of members of $\mathcal{D}_k^{(r,s)}$ as $(-1)^{n-k}$ and let $\mathcal{D}^{(r,s)}$ be the union of all $\mathcal{D}_k^{(r,s)}$.
Let $i$ again denote the number of elements of $J$ going in one of the $r$ special cycles and $j$ be the number of special blocks that contain at least one non-special cycle in the $s$-partition.  Upon applying the prior involution, to determine the sum of the signs of all members of $\mathcal{D}^{(r,s)}$, we may assume that the non-special cycles all have length one and occur in different blocks of the $s$-partition.  Note that if $m&lt;v_{i,j}$, then it is seen that there are no survivors of the involution corresponding to such $i$ and $j$, and indeed the summands for such $i$ and $j$ in the sum on the right side of \eqref{Psigenneg} are all seen to be zero.  If $m=v_{i,j}$, then there are $(m+s)^{-\lambda}$ ways in which to add the elements of $K$ within a surviving configuration, which is accounted for by the terms in the sum where $\ell=0$.  Finally, if $m&gt;v_{i,j}$, then $\ell$ members of $K$ for some $1 \leq \ell \leq -\lambda$ must occupy the remaining unfilled non-special blocks, which implies the remaining terms in the sum account for survivors where $m&gt;v_{i,j}$.  Combining this case with the prior cases implies the right side of \eqref{Psigenneg} gives the sum of the signs of all survivors, which completes the proof.
\end{proof}


Letting, for example, $r=0$ or $s=0$ in \eqref{Psigenpos} gives for $\lambda&gt;0$ the identities
$$\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}\Stirling{k}{m}_r(-1)^{n-k}=\sum_{j=0}^u \frac{(-1)^{n-m-j}(n-1)!}{m!}\binom{r}{j}\sigma_{\lambda-1}(m+j+1;n-1)$$
and
$$\sum_{k=m}^{n-\lambda}\stirling{n}{k+\lambda}_r\Stirling{k}{m}(-1)^{n-k}=(-1)^{n-m}\sum_{i=0}^{u}\frac{(n-i-1)!r^{\overline{i}}}{m!}\binom{n}{i}\sigma_{\lambda-1}(m+1;n-i-1).$$

\begin{thebibliography}{99}

\bibitem{Br}
A.~Z.~Broder, The $r$-Stirling numbers, \textit{Discrete Math.} \textbf{49} (1984), 241--259.

\bibitem{Cai}
Y.~Cai, $q$-Stirling identities revisited, \textit{Electron. J. Combin.} \textbf{25} (2018), Paper \#P1.37.

\bibitem{Chu}
W.~Chu, Disjoint convolution sums of Stirling numbers, \textit{Math. Commun.} \textbf{26} (2021), 239--251.

\bibitem{Com}
L.~Comtet, \emph{Advanced Combinatorics}, Dordrecht-Holland, 1974.

\bibitem{Gr}
R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik, \textit{Concrete Mathematics: A Foundation for Computer Science}, second edition, Addison-Wesley, 1994.

\bibitem{Guo}
D.~Guo, Summation formulae involving Stirling and Lah numbers, \textit{Forum Math.} \textbf{32} (2020), 1407--1414.

\bibitem{Kn}
D.~E.~Knuth, Two notes on notation, \textit{Amer. Math. Monthly} \textbf{99} (1992), 403--422.

\bibitem{Mer}
R.~Merris, The $p$-Stirling numbers, \textit{Turkish J. Math.} \textbf{24} (2000), 379--399.

\bibitem{NR}
G.~Nyul and G.~R\'{a}cz, The $r$-Lah numbers, \textit{Discrete Math.} \textbf{338} (2015), 1660--1666.

\bibitem{Qu}
J.~Quaintance and H.~W.~Gould, \textit{Combinatorial Identities for Stirling Numbers}, World Scientific, 2016.

\bibitem{Sh}
M.~Shattuck, Combinatorial identities for Stirling numbers of the first kind via involution, \textit{Integers} \textbf{12} (2012), Paper \#A59.

\bibitem{Slo}
N.~J.~A.~Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2022. Available at \url{https://oeis.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary: 05A19; Secondary: 05A05.

\noindent \emph{Keywords:} combinatorial identity, Stirling number, Lah number, combinatorial proof.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A008275}, \seqnum{A008277}, and \seqnum{A008297}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 25 2021;
revised version received January 9 2022.
Published in {\it Journal of Integer Sequences}, January 29 2022.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}



</pre></body></html>