\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}}}

\usepackage{tikz}
\usetikzlibrary{calc,positioning,arrows.meta}

\newcommand{\stirI}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\stirII}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}
\newcommand{\fp}[2]{{#1}^{\underline{#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 Some New Identities for Stirling Numbers
}
\vskip 1cm
\large
Kwankyu Lee \\
Department of Mathematics Education \\
Chosun University\\
309, Pilmun-daero, Dong-gu, Gwangju, 61452 \\
Republic of Korea \\
\href{mailto:kwankyu@chosun.ac.kr}{\tt kwankyu@chosun.ac.kr} \\
\end{center}

\vskip .2 in
\begin{abstract}
We present six identities involving Stirling numbers of both kinds. The first two convolution identities appear to be new, and we prove them by algebraic methods using falling powers and generating functions. 
The other four are recurrence relations for Stirling numbers that recently appeared as conjectures. Two of these were proved, in equivalent forms, elsewhere by algebraic methods. However, we provide novel combinatorial proofs for all of them. 
\end{abstract}

\section{Introduction}

Many identities are known involving Stirling numbers of the first kind $\stirI{n}{k}$
and of the second kind $\stirII{n}{k}$, which are sequences \seqnum{A132393} and \seqnum{A008277} respectively in the On-Line Encyclopedia of Integer Sequences (OEIS). See the basic references \cite{deza2023,graham1994,mezo2019,quaintance2015}. Here we add six more to the list.

The first identity 
\[
	\stirI{n+1}{m+1}=\sum_{k=m}^n\stirI{n}{k}\binom{k}{m}(-1)^{n-k}n^{k-m}
\]
is a convolution identity involving Stirling numbers of the first kind and binomial coefficients. This is noteworthy as it parallels the well-known convolution identity
\[
	\stirI{n+1}{m+1}=\sum_{k=m}^n\stirI{n}{k}\binom{k}{m}.
\]
We prove it in Theorem \ref{thm:cksdd} using falling powers. A similar identity  
\[
	\stirII{n}{m}=\sum_{k=m}^n\binom{n}{k}\stirII{k}{m}m^{n-k}(-1)^{k-m}
\]
holds for Stirling numbers of the second kind. This is comparable to the well-known identity
\[
	\stirII{n+1}{m+1}=\sum_{k=m}^n\binom{n}{k}\stirII{k}{m}.
\]
We prove the new identity in Theorem \ref{thm:kscasc} by the generating function technique. 

Sections \ref{sec:kscsd} and \ref{sec:kcsdf} are devoted to proving several conjectured recurrences for Stirling numbers of the second kind and of the first kind, respectively. We prove the recurrences
\[
	\stirII{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}\binom{n}{j}\stirII{n-j+1}{k}(-1)^j
\]
and
\[
	\stirII{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}(j-2)!\binom{-k}{j}\stirII{n}{k+j-1}
\]
in Theorem \ref{thm:mxcnd} and Theorem \ref{thm:dwdwf}, respectively. Using the former recurrence, the numbers 
$\stirII{k+1}{k}$, $\stirII{k+2}{k}$, \dots, $\stirII{n}{k}$ can be computed 
recursively, starting with $\stirII{k}{k}=1$. Using the latter recurrence,
the numbers $\stirII{n}{n-1}$, $\stirII{n}{n-2}$, \dots, $\stirII{n}{k}$ can be computed recursively, starting
with $\stirII{n}{n}=1$. 

In Section \ref{sec:kcsdf}, the recurrences
\[
	\stirI{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}\binom{n}{j}\stirI{n-j+1}{k}(j-2)!
\]
and
\[
	\stirI{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}\stirI{n}{k+j-1}\binom{k+j-1}{j}
\]
are proved in Theorem \ref{thm:mdkda} and Theorem \ref{thm:dwfmc}, respectively. Using the former recurrence, the numbers 
$\stirI{k+1}{k}$, $\stirI{k+2}{k}$, \dots, $\stirI{n}{k}$ can be recursively computed starting with $\stirI{k}{k}=1$. Using the latter recurrence, the numbers $\stirI{n}{n-1}$, $\stirI{n}{n-2}$, \dots, $\stirI{n}{k}$ can be computed recursively starting
with $\stirI{n}{n}=1$. 

The two recurrences in Theorems \ref{thm:mxcnd} and \ref{thm:dwfmc} are not strictly new. Algebraic proofs for them are found in \cite{quaintance2015}. See Section \ref{sec:kofes} for more details. However, we here prove all the recurrences by novel combinatorial arguments. To facilitate the combinatorial proofs, we set up some notation. By the set $[n]$, we mean the set of the first $n$ positive integers. The set $C(n,k)$ denotes the set of $k$-element subsets of the set $[n]$. The set $S(n,k)$ denotes the set of partitions of the set $[n]$ into $k$ subsets. The set $K(n,k)$ denotes the set of partitions of the set $[n]$ into $k$ cycles. Obviously $|C(n,k)|=\binom{n}{k}$, $|S(n,k)|=\stirII{n}{k}$, and $|K(n,k)|=\stirI{n}{k}$. A cycle is denoted by brackets, as usual.

\section{Convolution identities for Stirling numbers}

We recall the basic identity
\[
	\fp{x}{n}=\sum_{k=0}^n\stirI{n}{k}(-1)^{n-k}x^k
\]
that relates the $n$-th falling power on the left-hand side with ordinary powers via Stirling numbers of the first kind.

\begin{theorem}\label{thm:cksdd}
We have
\[
	\stirI{n+1}{m+1}=\sum_{k=m}^n\stirI{n}{k}\binom{k}{m}(-1)^{n-k}n^{k-m}
\]
for $0\le m\le n$.
\end{theorem}

\begin{proof}
Note that
\[
	\begin{split}
	(x+1)(x+2)\cdots(x+n)=\fp{(x+n)}{n}&=\sum_{k=0}^n\stirI{n}{k}(-1)^{n-k}(x+n)^k \\
	&=\sum_{k=0}^n\stirI{n}{k}(-1)^{n-k}\sum_{l=0}^k\binom{k}{l}n^{k-l}x^l \\
	&=\sum_{k=0}^n\sum_{l=0}^k\stirI{n}{k}\binom{k}{l}(-1)^{n-k}n^{k-l}x^l.
	\end{split}
\]
On the other hand, 
\[
	\begin{split}
	(-x)(-x-1)\cdots(-x-n)=\fp{(-x)}{n+1}&=\sum_{k=0}^{n+1}\stirI{n+1}{k}(-1)^{n+1-k}(-x)^k \\
	&=\sum_{k=0}^{n+1}\stirI{n+1}{k}(-1)^{n+1}x^k.
	\end{split}
\]
Hence
\[
	\sum_{k=0}^{n+1}\stirI{n+1}{k}x^k=x(x+1)\cdots(x+n)
	=x\sum_{k=0}^n\sum_{l=0}^k\stirI{n}{k}\binom{k}{l}(-1)^{n-k}n^{k-l}x^l.
\]	
Now by comparing the coefficients of $x^{m+1}$ on both sides for $0\le m\le n$, we obtain
\[
	\stirI{n+1}{m+1}=\sum_{k=m}^n\stirI{n}{k}\binom{k}{m}(-1)^{n-k}n^{k-m}.
\]
\end{proof}

We recall that the exponential generating function of the Stirling numbers of the second kind is
\[
	\sum_{n=0}^\infty\stirII{n}{m}\frac{x^n}{n!}=\frac{(e^x-1)^m}{m!}.
\]

\begin{theorem}\label{thm:kscasc}
We have
\begin{equation}\label{equ:abcfw}
	\stirII{n}{m}=\sum_{k=m}^n\binom{n}{k}\stirII{k}{m}m^{n-k}(-1)^{k-m}
\end{equation}
for $0\le m\le n$.
\end{theorem}

\begin{proof}
We consider the exponential generating function of the right-hand side of \eqref{equ:abcfw}:
\[
	\begin{split}
	&\sum_{n=0}^\infty\left(\sum_{k=m}^n\binom{n}{k}\stirII{k}{m}m^{n-k}(-1)^{k-m}\right)\frac{x^n}{n!} \\
	&\quad=\sum_{n=0}^\infty\left(\sum_{k=0}^\infty\binom{n}{k}\stirII{k}{m}m^{n-k}(-1)^{k-m}\right)\frac{x^n}{n!} \\
	&\quad=\sum_{k=0}^\infty\stirII{k}{m}(-1)^{k-m}\sum_{n=k}^\infty\binom{n}{k}m^{n-k}\frac{x^n}{n!} \\
	&\quad=\sum_{k=0}^\infty\stirII{k}{m}(-1)^{k-m}\sum_{i=0}^\infty\binom{i+k}{k}m^{i}\frac{x^{i+k}}{(i+k)!} \\	
	&\quad=\sum_{k=0}^\infty\stirII{k}{m}(-1)^{k-m}\frac{x^k}{k!}\sum_{i=0}^\infty\frac{(mx)^i}{i!} \\		
	&\quad=e^{mx}(-1)^m\sum_{k=0}^\infty\stirII{k}{m}\frac{(-x)^k}{k!} \\	
	&\quad=e^{mx}(-1)^m\frac{(e^{-x}-1)^m}{m!}=\frac{(e^x-1)^m}{m!}.
	\end{split}
\]
Hence we obtain the identity.
\end{proof}

\section{Recurrences for Stirling numbers of the second kind}\label{sec:kscsd}

Let $1\le j\le n$. Let $C(n,j)\times S(n-j+1,k)$ denote the set of partitions into $k$ subsets of the set of a distinguished subset of $j$ elements chosen from the set $[n]$ and the remaining $n-j$ elements. Obviously
\[
	|C(n,j)\times S(n-j+1,k)|=\binom{n}{j}\stirII{n-j+1}{k}.
\]
Replacing the distinguished subset with its own elements, we get a member of $S(n,k)$. We denote this correspondence by $\Phi$.

\begin{example}
A partition of the set of a chosen subset $\{5,6,7\}$ from the set $[9]$ and the remaining elements 
\[
	\{1\},\,\{2,3\},\,\{4\},\,\{\{5,6,7\},8,9\}
\]
is a member of $C(9,3)\times S(7, 4)$. Then we have
\[
	\{1\},\,\{2,3\},\,\{4\},\,\{\{5,6,7\},8,9\}\quad\overset{\Phi}{\longrightarrow}\quad 
	\{1\},\,\{2,3\},\,\{4\},\,\{5,6,7,8,9\}
\]
where the right-hand side is a member of $S(9,4)$ obtained from the partition on the left-hand side by replacing $\{\{5,6,7\},8,9\}$ with $\{5,6,7,8,9\}$.
\end{example}

\begin{theorem}\label{thm:mxcnd}
We have
\[
	\stirII{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}\binom{n}{j}\stirII{n-j+1}{k}(-1)^j
\]
for $1\le k\le n-1$.
\end{theorem}

\begin{proof}
Let
\[
	A(n,k)=\sum_{j=2}^{n-k+1}\binom{n}{j}\stirII{n-j+1}{k}(-1)^j.
\]
Note that 
\[
	\begin{split}
	\binom{n}{j}\stirII{n-j+1}{k}&=|C(n,j)\times S(n-j+1,k)| \\
	&=\sum_{s\in S(n,k)}|\Phi^{-1}(s)\cap C(n,j)\times S(n-j+1,k)|
	\end{split}
\]
for $2\le j\le n-k+1$. For $s\in S(n,k)$, let
\[
	t_{s,j} = |\Phi^{-1}(s)\cap C(n,j)\times S(n-j+1,k)|.
\]
Observe that $t_{s,j}$ depends only on the partition pattern of $s$. That is, if $a_1$, $a_2$, \dots, $a_k$ are the sizes of the $k$ subsets forming $s$, then $n=a_1+a_2+\dots+a_k$ and
\[
	t_{s,j} = \binom{a_1}{j}+\binom{a_2}{j}+\dots+\binom{a_k}{j}.
\]
Note that $1\le a_i\le n-k+1$ for $1\le i\le k$. Hence
\[
	\begin{split}
	\sum_{j=2}^{n-k+1}t_{s,j}(-1)^j&=\sum_{j=2}^{n-k+1}\left(\binom{a_1}{j}+\binom{a_2}{j}+\dots+\binom{a_k}{j}\right)(-1)^j \\
	&=\sum_{j=2}^{\infty}\binom{a_1}{j}(-1)^j+\sum_{j=2}^{\infty}\binom{a_2}{j}(-1)^j+\dots+\sum_{j=2}^{\infty}\binom{a_k}{j}(-1)^j \\
	&=\sum_{j=0}^{\infty}\binom{a_1}{j}(-1)^j+a_1-1+\sum_{j=0}^{\infty}\binom{a_2}{j}(-1)^j+a_2-1 +\cdots \\
	&\quad+\sum_{j=0}^{\infty}\binom{a_k}{j}(-1)^j+a_k-1 \\
	&=a_1-1+a_2-1+\dots+a_k-1=n-k
	\end{split}
\]
since $\sum_{j=0}^{\infty}\binom{a}{j}(-1)^j=0$ for any positive integer $a$. Therefore 
\[
	A(n,k)=\sum_{j=2}^{n-k+1}\sum_{s\in S(n,k)}t_{s,j}(-1)^j=\sum_{s\in S(n,k)}(n-k)=(n-k)\stirII{n}{k}.
\]
\end{proof}

\begin{example}\label{ex:kscgr}
Since $\stirII{n}{n-1}=\binom{n}{2}$, the recurrence shows that Stirling numbers of the second kind can be expressed as
a rational combination of products of binomial coefficients. For instance,
\[
	\begin{aligned}
	2!\stirII{n}{n-2}&=\binom{n}{2}\binom{n-1}{2}-\binom{n}{3}, \\
	3!\stirII{n}{n-3}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}-\binom{n}{2}\binom{n-1}{3} \\
	&\quad-2\binom{n}{3}\binom{n-2}{2}+2\binom{n}{4}, \\
	4!\stirII{n}{n-4}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}\binom{n-3}{2}-\binom{n}{2}\binom{n-1}{2}\binom{n-2}{3} \\
	&\quad-2\binom{n}{2}\binom{n-1}{3}\binom{n-3}{2}-3\binom{n}{3}\binom{n-2}{2}\binom{n-3}{2} \\
	&\quad+2\binom{n}{2}\binom{n-1}{4}+3\binom{n}{3}\binom{n-2}{3}+6\binom{n}{4}\binom{n-3}{2}-6\binom{n}{5}.
	\end{aligned}
\]
\end{example}

The following lemma is used in the proof of the next recurrence. 

\begin{lemma}\label{lem:mjkfwd}
The identity
\begin{equation}\label{equ:abc}
	\sum_{j=2}^{a}\stirII{a}{j}(j-2)!(-1)^j=a-1
\end{equation}
holds for $a\ge 1$.
\end{lemma}

\begin{proof}
Let
\[
	A(x)=\sum_{a=1}^\infty\left(\sum_{j=2}^\infty\stirII{a}{j}(j-2)!(-1)^j\right)\frac{x^a}{a!}.
\]
Then
\[
	\begin{split}
	A(x)&=\sum_{j=2}^\infty(j-2)!(-1)^j\sum_{a=1}^\infty\stirII{a}{j}\frac{x^a}{a!}=\sum_{j=2}^\infty(j-2)!(-1)^j\frac{(e^x-1)^j}{j!} \\
		&=\sum_{j=2}^\infty\left(\frac{1}{j-1}-\frac{1}{j}\right)(1-e^x)^j \\
		&=(1-e^x)\sum_{j=2}^\infty\frac{(1-e^x)^{j-1}}{j-1}-\sum_{j=2}^\infty\frac{(1-e^x)^j}{j} \\
		&=(1-e^x)(-x)-(-x-(1-e^x))=xe^x+1-e^x=\sum_{a=1}^\infty(a-1)\frac{x^a}{a!}.
	\end{split}
\]
Hence we get the identity.
\end{proof}

Let $S(n,k)\times C(k,j)$ denote the set of combinations of $j$ subsets chosen from the $k$ subsets forming a partition in $S(n,k)$. Clearly
\[
	|S(n,k)\times C(k,j)|=\stirII{n}{k}\binom{k}{j}.
\]
Note that to each member of $S(n,k)\times C(k,j)$, we can associate a member of $S(n,k-j+1)$ by replacing the chosen $j$ subsets with the union of them. Let $\Psi$ denote this correspondence from $S(n,k)\times C(k,j)$ to $S(n,k-j+1)$.

\begin{example}
A combination of $3$ subsets chosen from $5$ subsets partitioning the set $[8]$
\begin{center}
\begin{tikzpicture}
    \node (set1) at (0,0) {$\{1\}$,};
    \node (set2) [right=.2cm of set1] {$\{2,3\}$,}; 
    \node (set3) [right=.2cm of set2] {$\{4,5\}$,};
    \node (set4) [right=.2cm of set3] {$\{6\}$,};
    \node (set5) [right=.2cm of set4] {$\{7,8\}$};   

    \def\lineheight{.3cm}   

    \draw (set3.north) -- ($(set3.north) + (0,\lineheight)$);
    \draw (set4.north) -- ($(set4.north) + (0,\lineheight)$);
    \draw (set5.north) -- ($(set5.north) + (0,\lineheight)$);    
    \draw ($(set3.north) + (0,\lineheight)$) -- ($(set5.north) + (0,\lineheight)$); 
\end{tikzpicture}
\end{center}
is a member of $S(8,5)\times C(5,3)$. Then we have
\begin{center}
\begin{tikzpicture}
    \node (set1) at (0,0) {$\{1\}$,};
    \node (set2) [right=.2cm of set1] {$\{2,3\}$,}; 
    \node (set3) [right=.2cm of set2] {$\{4,5\}$,};
    \node (set4) [right=.2cm of set3] {$\{6\}$,};
    \node (set5) [right=.2cm of set4] {$\{7,8\}$};   

    \def\lineheight{.3cm}   

    \draw (set3.north) -- ($(set3.north) + (0,\lineheight)$);
    \draw (set4.north) -- ($(set4.north) + (0,\lineheight)$);
    \draw (set5.north) -- ($(set5.north) + (0,\lineheight)$);    
    \draw ($(set3.north) + (0,\lineheight)$) -- ($(set5.north) + (0,\lineheight)$);

    \node (arrow_start) at ($(set5.east) + (.2cm, 0)$) {}; 
    
    \node (set_new1) [right=1cm of arrow_start] {$\{1\}$,}; 
    \node (set_new2) [right=.2cm of set_new1] {$\{2,3\}$,};
    \node (set_new3) [right=.2cm of set_new2] {$\{4,5,6,7,8\}$}; 
    
    \node (arrow_end) at ($(set_new1.west) - (.2cm, 0)$) {};  

    \draw[->] (arrow_start) -- (arrow_end) node[midway, above] {$\Psi$};   
\end{tikzpicture}
\end{center}
where the right-hand side of the arrow is a member of $S(8,3)$.
\end{example}

\begin{theorem}\label{thm:dwdwf}
We have
\[
	\stirII{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}(j-2)!\binom{-k}{j}\stirII{n}{k+j-1}
\]
for $1\le k\le n-1$.
\end{theorem}

\begin{proof}
Note that
\[
	\sum_{j=2}^{n-k+1}(j-2)!\binom{-k}{j}\stirII{n}{k+j-1}=\sum_{j=2}^{n-k+1}\stirII{n}{k+j-1}\binom{k+j-1}{j}(j-2)!(-1)^{j}.	
\]	
Let
\[
	A(n,k)=\sum_{j=2}^{n-k+1}\stirII{n}{k+j-1}\binom{k+j-1}{j}(j-2)!(-1)^{j}.
\]
Note that
\[
	\begin{split}
	\stirII{n}{k+j-1}\binom{k+j-1}{j}&=|S(n,k+j-1)\times C(k+j-1,j)|\\
	&=\sum_{s\in S(n,k)}|\Psi^{-1}(s)\cap S(n,k+j-1)\times C(k+j-1,j)|.
	\end{split}
\]
For $s\in S(n,k)$, let
\[
	t_{s,j}=|\Psi^{-1}(s)\cap S(n,k+j-1)\times C(k+j-1,j)|
\]	
for $2\le j\le n-k+1$. Observe that $t_{s,j}$ only depends on the partition pattern of $s$. We assume $n=a_1+a_2+\dots+a_k$ and $k$ subsets of the partition $s$ are of size $a_1$, $a_2$, \dots, $a_k$. Then
\[
	t_{s,j}=\stirII{a_1}{j}+\stirII{a_2}{j}+\dots+\stirII{a_k}{j}.
\]
Hence
\[	
	\begin{split}
	\sum_{j=2}^{n-k+1}t_{s,j}(j-2)!(-1)^j&=\sum_{j=2}^{n-k+1}\left(\stirII{a_1}{j}+\stirII{a_2}{j}+\dots+\stirII{a_k}{j}\right)(j-2)!(-1)^j \\
	&=a_1-1+a_2-1+\dots+a_k-1=n-k
	\end{split}
\]
by Lemma \ref{lem:mjkfwd}. Therefore 
\[
	A(n,k)=\sum_{j=2}^{n-k+1}\sum_{s\in S(n,k)}t_{s,j}(j-2)!(-1)^j=\sum_{s\in S(n,k)}(n-k)=(n-k)\stirII{n}{k}.
\]
\end{proof}

\begin{example}\label{ex:kdsvdw}
Since $\stirII{n}{n-1}=\binom{n}{2}$, the above recurrence also allows Stirling numbers of the first kind to be expressed as
a rational combination of products of binomial coefficients. For instance, we have
\[
	\begin{aligned}
	2!\stirII{n}{n-2}&=\binom{n}{2}\binom{n-1}{2}-\binom{n}{3}, \\
	3!\stirII{n}{n-3}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}-2\binom{n}{2}\binom{n-1}{3} \\
	&\quad-\binom{n}{3}\binom{n-2}{2}+4\binom{n}{4}, \\
	4!\stirII{n}{n-4}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}\binom{n-3}{2}-3\binom{n}{2}\binom{n-1}{2}\binom{n-2}{3} \\
	&\quad-2\binom{n}{2}\binom{n-1}{3}\binom{n-3}{2}-\binom{n}{3}\binom{n-2}{2}\binom{n-3}{2} \\
	&\quad+12\binom{n}{2}\binom{n-1}{4}+3\binom{n}{3}\binom{n-2}{3}+4\binom{n}{4}\binom{n-3}{2}-36\binom{n}{5}.	
	\end{aligned}
\]
Moreover, comparing with the previous identities in Example \ref{ex:kscgr}, we get identities such as 
\[
	\begin{aligned}
	2\binom{n}{4} &=\binom{n}{2}\binom{n-1}{3}-\binom{n}{3}\binom{n-2}{2}, \\
	15\binom{n}{5}&=\binom{n}{3}\binom{n-2}{2}\binom{n-3}{2}-\binom{n}{2}\binom{n-1}{2}\binom{n-2}{3}\\
	&\quad+5\binom{n}{2}\binom{n-1}{4}-\binom{n}{4}\binom{n-3}{2}
	\end{aligned}
\]
between binomial coefficients.
\end{example}

\section{Recurrences for Stirling numbers of the first kind}\label{sec:kcsdf}

Let $C(n,j)\times K(n-j+1,k)$ denote the set of partitions of a distinguished subset of $j$ elements from the set $[n]$ and the remaining $n-j$ elements into $k$ cycles. Clearly
\[
	|C(n,j)\times K(n-j+1,k)|=\binom{n}{j}\stirI{n-j+1}{k}.
\]
Replacing the cycles with the underlying subsets and the distinguished subset with its own elements, we get a member of $S(n,k)$. This correspondence is denoted by $\Phi$. In the same way, we set up a correspondence from $K(n,k)$ to $S(n,k)$, which we also denote by $\Phi$.

\begin{example}
A partition of the set consisting of a chosen subset $\{5,6,7\}$ from the set $[9]$ and the remaining elements into cycles
\[
	[1],\,[2,3],\,[4],\,[\{5,6,7\},8,9]
\]
is a member of $C(9,3)\times K(7, 4)$. 

We have 
\[
	[1],\,[2,3],\,[4],\,[\{5,6,7\},8,9]\quad\overset{\Phi}{\longrightarrow}\quad 
	\{1\},\,\{2,3\},\,\{4\},\,\{5,6,7,8,9\}
\]
where the right-hand side is a member of $S(9,4)$. We also have
\[
	[1],\,[2,3],\,[4],\,[5,6,7,8,9]\quad\overset{\Phi}{\longrightarrow}\quad 
	\{1\},\,\{2,3\},\,\{4\},\,\{5,6,7,8,9\}
\]	
by the correspondence $\Phi$ from $K(9,4)$ to $S(9,4)$. 
\end{example}

\begin{theorem}\label{thm:mdkda}
We have
\[
	\stirI{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}\binom{n}{j}\stirI{n-j+1}{k}(j-2)!
\]
for $1\le k\le n-1$.
\end{theorem}

\begin{proof}
Let
\[
	A(n,k)=\sum_{j=2}^{n-k+1}\binom{n}{j}\stirI{n-j+1}{k}(j-2)!.
\]
Note that 
\[
	\begin{split}
	\binom{n}{j}\stirI{n-j+1}{k}&=|C(n,j)\times K(n-j+1,k)| \\
	&=\sum_{s\in S(n,k)}|\Phi^{-1}(s)\cap C(n,j)\times K(n-j+1,k)|
	\end{split}
\]
for $2\le j\le n-k+1$. For $s\in S(n,k)$, let
\[
	t_{s,j} = |\Phi^{-1}(s)\cap C(n,j)\times K(n-j+1,k)|.
\]
Again $t_{s,j}$ depends only on the partition pattern of $s$. Let $n=a_1+a_2+\dots+a_k$ where $a_1$, $a_2$, \dots, $a_k$ are the sizes of the $k$ subsets. Then we see that
\[
	\begin{split}
	t_{s,j} &= \binom{a_1}{j}(a_1-j)!(a_2-1)!\cdots(a_k-1)! \\
	    &\quad+(a_1-1)!\binom{a_2}{j}(a_2-j)!(a_3-1)!\cdots(a_k-1)!+\cdots \\
	    &\quad+(a_1-1)!(a_2-1)!\cdots(a_{k-1}-1)!\binom{a_k}{j}(a_k-j)!.
	\end{split}
\]
Hence
\[
	\begin{split}
	\sum_{j=2}^{n-k+1}t_{s,j}(j-2)!&=(a_2-1)!\cdots(a_k-1)!\sum_{j=2}^{n-k+1}\binom{a_1}{j}(a_1-j)!(j-2)! \\
	&\quad+(a_1-1)!(a_3-1)!\cdots(a_k-1)!\sum_{j=2}^{n-k+1}\binom{a_2}{j}(a_2-j)!(j-2)!+\cdots \\
	&\quad+(a_1-1)!(a_2-1)!\cdots(a_{k-1}-1)!\sum_{j=2}^{n-k+1}\binom{a_k}{j}(a_k-j)!(j-2)!. 
	\end{split}
\]
It is verified that
\[
	\sum_{j=2}^{a}\binom{a}{j}(a-j)!(j-2)!=(a-1)(a-1)!
\]
for positive integer $a$. Therefore
\[
	\begin{split}
	\sum_{j=2}^{n-k+1}t_{s,j}(j-2)!&=(a_1-1+a_2-1+\cdots+a_k-1)(a_1-1)!(a_2-1)!\cdots(a_k-1)! \\
	&=(n-k)(a_1-1)!(a_2-1)!\cdots(a_k-1)! \\
	&=(n-k)|\Phi^{-1}(s)\cap K(n,k)|.
	\end{split}
\]
Hence
\[
	\begin{split}
	A(n,k)&=\sum_{j=2}^{n-k+1}\sum_{s\in S(n,k)}t_{s,j}(j-2)! \\
	&=(n-k)\sum_{s\in S(n,k)}|\Phi^{-1}(s)\cap K(n,k)| \\
	&=(n-k)|K(n,k)|=(n-k)\stirI{n}{k}.
	\end{split}
\]
\end{proof}

\begin{example}\label{ex:krgias}
Since $\stirI{n}{n-1}=\binom{n}{2}$, by the above recurrence, Stirling numbers of the first kind can be expressed as
a rational combination of products of binomial coefficients. For instance,
\[
	\begin{aligned}
	2!\stirI{n}{n-2}&=\binom{n}{2}\binom{n-1}{2}+\binom{n}{3}, \\
	3!\stirI{n}{n-3}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}+\binom{n}{2}\binom{n-1}{3} \\
	&\quad+2\binom{n}{3}\binom{n-2}{2}+4\binom{n}{4}, \\
	4!\stirI{n}{n-4}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}\binom{n-3}{2}+\binom{n}{2}\binom{n-1}{2}\binom{n-2}{3} \\
	&\quad+2\binom{n}{2}\binom{n-1}{3}\binom{n-3}{2}+3\binom{n}{3}\binom{n-2}{2}\binom{n-3}{2} \\
	&\quad+4\binom{n}{2}\binom{n-1}{4}+3\binom{n}{3}\binom{n-2}{3}+12\binom{n}{4}\binom{n-3}{2}+36\binom{n}{5}.
	\end{aligned}
\]
\end{example}

Let $K(n,k)\times C(k,j)$ denote the set of combinations of $j$ cycles from the $k$ cycles forming a partition in $K(n,k)$. Clearly
\[
	|K(n,k)\times C(k,j)|=\stirI{n}{k}\binom{k}{j}.
\]
Note that to each member of $K(n,k)\times C(k,j)$, we can associate a member of $S(n,k-j+1)$ by replacing the chosen $j$ cycles with the set of their elements and the other cycles with their underlying sets. Let $\Psi$ denote the correspondence from $K(n,k)\times C(k,j)$ to $S(n,k-j+1)$.

\begin{example}
A combination of $3$ cycles chosen from $5$ cycles partitioning the set $[8]$
\begin{center}
\begin{tikzpicture}
    \node (set1) at (0,0) {$[1]$,};
    \node (set2) [right=.2cm of set1] {$[2,3]$,}; 
    \node (set3) [right=.2cm of set2] {$[4,5]$,};
    \node (set4) [right=.2cm of set3] {$[6]$,};
    \node (set5) [right=.2cm of set4] {$[7,8]$};   

    \def\lineheight{.3cm}   

    \draw (set3.north) -- ($(set3.north) + (0,\lineheight)$);
    \draw (set4.north) -- ($(set4.north) + (0,\lineheight)$);
    \draw (set5.north) -- ($(set5.north) + (0,\lineheight)$);    
    \draw ($(set3.north) + (0,\lineheight)$) -- ($(set5.north) + (0,\lineheight)$);  
\end{tikzpicture}
\end{center}
is a member of $K(8,5)\times C(5,3)$. We have
\begin{center}
\begin{tikzpicture}
    \node (set1) at (0,0) {$[1]$,};
    \node (set2) [right=.2cm of set1] {$[2,3]$,}; 
    \node (set3) [right=.2cm of set2] {$[4,5]$,};
    \node (set4) [right=.2cm of set3] {$[6]$,};
    \node (set5) [right=.2cm of set4] {$[7,8]$};   

    \def\lineheight{.3cm}   

    \draw (set3.north) -- ($(set3.north) + (0,\lineheight)$);
    \draw (set4.north) -- ($(set4.north) + (0,\lineheight)$);
    \draw (set5.north) -- ($(set5.north) + (0,\lineheight)$);    
    \draw ($(set3.north) + (0,\lineheight)$) -- ($(set5.north) + (0,\lineheight)$);

    \node (arrow_start) at ($(set5.east) + (.2cm, 0)$) {}; 
    
    \node (set_new1) [right=1cm of arrow_start] {$\{1\}$,}; 
    \node (set_new2) [right=.2cm of set_new1] {$\{2,3\}$,};
    \node (set_new3) [right=.2cm of set_new2] {$\{4,5,6,7,8\}$}; 
    
    \node (arrow_end) at ($(set_new1.west) - (.2cm, 0)$) {};  

    \draw[->] (arrow_start) -- (arrow_end) node[midway, above] {$\Psi$};   
\end{tikzpicture}
\end{center}
 where the right-hand side is a member of $S(8,3)$.
\end{example}

\begin{theorem}\label{thm:dwfmc}
We have
\[
	\stirI{n}{k}=\frac{1}{n-k}\sum_{j=2}^{n-k+1}\stirI{n}{k+j-1}\binom{k+j-1}{j}
\]
for $1\le k\le n-1$.
\end{theorem}

\begin{proof}	
Let
\[
	A(n,k)=\sum_{j=2}^{n-k+1}\stirI{n}{k+j-1}\binom{k+j-1}{j}
\]
Note that
\[
	\begin{split}
	\stirI{n}{k+j-1}\binom{k+j-1}{j}&=|K(n,k+j-1)\times C(k+j-1,j)| \\
	&=\sum_{s\in S(n,k)}|\Psi^{-1}(s)\cap K(n,k+j-1)\times C(k+j-1,j)|
	\end{split}
\]
for $2\le j\le n-k+1$. For $s\in S(n,k)$, let
\[
	t_{s,j}=|\Psi^{-1}(s)\cap K(n,k+j-1)\times C(k+j-1,j)|.
\]
Supposing the partition pattern of $s$ is $n=a_1+a_2+\dots+a_k$ as before, we see that
\[
	\begin{split}
	t_{s,j}&=\stirI{a_1}{j}(a_2-1)!\cdots(a_k-1)! \\
	&\quad+(a_1-1)!\stirI{a_2}{j}(a_3-1)!\cdots(a_k-1)!+\cdots \\
	&\quad+(a_1-1)!(a_2-1)!\cdots(a_{k-1}-1)!\stirI{a_k}{j}.
	\end{split}
\]
Note that for any positive integer $a$,
\[
	\sum_{j=2}^{\infty}\stirI{a}{j}=a!-(a-1)!=(a-1)(a-1)!
\]
holds. Therefore
\[
	\begin{split}
	\sum_{j=2}^{n-k+1}t_{s,j}&=(n-k)(a_1-1)!(a_2-1)!\cdots(a_k-1)! \\
	&=(n-k)|\Psi^{-1}(s)\cap K(n,k)|.
	\end{split}
\]
Hence
\[
	\begin{split}
	A(n,k)&=\sum_{j=2}^{n-k+1}\sum_{s\in S(n,k)}t_{s,j}=(n-k)\sum_{s\in S(n,k)}|\Psi^{-1}(s)\cap K(n,k)| \\
	&=(n-k)|K(n,k)|=(n-k)\stirI{n}{k}.
	\end{split}
\]
\end{proof}

\begin{example}
Since $\stirI{n}{n-1}=\binom{n}{2}$, by the above recurrence, we obtain
\[
	\begin{aligned}
	2!\stirI{n}{n-2}&=\binom{n}{2}\binom{n-1}{2}+\binom{n}{3}, \\
	3!\stirI{n}{n-3}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}+2\binom{n}{2}\binom{n-1}{3} \\
	&\quad+\binom{n}{3}\binom{n-2}{2}+2\binom{n}{4}, \\
	4!\stirI{n}{n-4}&=\binom{n}{2}\binom{n-1}{2}\binom{n-2}{2}\binom{n-3}{2}+3\binom{n}{2}\binom{n-1}{2}\binom{n-2}{3} \\
	&\quad+2\binom{n}{2}\binom{n-1}{3}\binom{n-3}{2}+\binom{n}{3}\binom{n-2}{2}\binom{n-3}{2}+6\binom{n}{2}\binom{n-1}{4} \\
	&\quad+3\binom{n}{3}\binom{n-2}{3}+2\binom{n}{4}\binom{n-3}{2}+6\binom{n}{5}.	
	\end{aligned}
\]
Comparing with the identities in Example \ref{ex:krgias}, we get identities like
\[
	\begin{aligned}
	2\binom{n}{4} &=\binom{n}{2}\binom{n-1}{3}-\binom{n}{3}\binom{n-2}{2}, \\
	15\binom{n}{5}&=-\binom{n}{3}\binom{n-2}{2}\binom{n-3}{2}+\binom{n}{2}\binom{n-1}{2}\binom{n-2}{3}\\
	&\quad+\binom{n}{2}\binom{n-1}{4}-5\binom{n}{4}\binom{n-3}{2}.
	\end{aligned}
\]
between binomial coefficients. Note that the expression of $\binom{n}{5}$ is different from the one in Example \ref{ex:kdsvdw}. 
\end{example}

\section{Final remarks}\label{sec:kofes}

The recurrence relations proved in Sections \ref{sec:kscsd} and \ref{sec:kcsdf} appeared as conjectures in the Wikipedia 
article ``Stirling numbers of the second kind'' \cite{wikipedia-stirling}, as of August 2025. The original source of these conjectures is unknown to the present author. 

However, the recurrences in Theorems \ref{thm:mxcnd} and \ref{thm:dwfmc} turn out to be equivalent to the equations (14.44) and (14.40), respectively, in Section 14.2 of \cite{quaintance2015}. Algebraic proofs of these identities are provided there, where the author discusses the ``Hagen recurrences'' attributed to Hagen \cite{Hagen1891}. 

\section{Acknowledgments}

The author thanks the reviewer for careful reading of the manuscript. This study was supported by research fund from Chosun University 2024-205605-1.

\begin{thebibliography}{9}

\bibitem{deza2023}
Elena Deza, {\em Stirling Numbers}, Vol.~3, World Scientific, 2023.

\bibitem{graham1994}
Ronald~L. Graham, Donald~E. Knuth, and Oren Patashnik, {\em Concrete
  Mathematics: A Foundation for Computer Science}, 2nd edition,
  Addison-Wesley, 1994.

\bibitem{Hagen1891}
Johann G. Hagen, {\em Synopsis der H\"oheren Mathematik, Vol. 1:
  Arithmetische und Algebraische Analyse}, Felix L. Dames,
  1891.

\bibitem{mezo2019}
Istv\'an Mez\H{o}, {\em Combinatorics and Number Theory of Counting Sequences},
  Chapman and Hall/CRC, 2019.

\bibitem{quaintance2015}
Jocelyn Quaintance and H. W. Gould, {\em Combinatorial Identities for
  Stirling Numbers: The Unpublished Notes of H W Gould}, World Scientific, 2015.

\bibitem{wikipedia-stirling}
{Wikipedia contributors}, Stirling numbers of the second kind,
  {Wikipedia},
  \url{https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind},
  2026.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

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

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A008277} and
\seqnum{A132393}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 28 2025;
revised versions received October 30 2025; April 29 2026.
Published in {\it Journal of Integer Sequences}, May 3 2026.

\bigskip
\hrule
\bigskip

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


\end{document}