\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\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 On Certain Sums of Stirling Numbers \\
\vskip .11in
with Binomial Coefficients
}
\vskip 1cm
H. W. Gould\\
Department of Mathematics\\
West Virginia University\\
Morgantown, WV 26506\\
USA\\
\href{mailto:henrygou@gmail.com}{\tt henrygou@gmail.com}\\
\ \\
Harris Kwong\\
Department of Mathematical Sciences\\
SUNY Fredonia\\
Fredonia, NY 14063\\
USA\\
\href{mailto:kwong@fredonia.edu}{\tt kwong@fredonia.edu}\\
\ \\
Jocelyn Quaintance\\
Department of Computer Science\\
University of Pennsylvania\\
Philadelphia, PA 19104\\
USA\\
\href{mailto:jocelynq@seas.upenn.edu}{\tt jocelynq@seas.upenn.edu} \\
\end{center}

\vskip .2 in

\def\N{\mathbb{N}}
\def\cS{{\cal S}}
\def\hcS{\widetilde{\cal S}}
\def\hf{\widehat{f}}
\def\hF{\widehat{F}}
\def\hg{\widehat{g}}
\def\hG{\widehat{G}}


\begin{abstract}
We study two sums
involving the Stirling numbers and binomial coefficients.
We find their closed forms, and discuss the
connection  between these sums.
\end{abstract}

\begin{center}\em
Dedicated to the memory of our mentors, \\
Professors Leonard Carlitz and Albert Nijenhuis.
\end{center}

\section{Introduction}

Stirling numbers of the first and second kind, denoted by $s(n,k)$ and
$S(n,k)$ respectively, in Riordan's \cite{Rio} popular notation, have
long fascinated mathematicians.  They were named for James Stirling
\cite{Stir} who used them in 1730.  In 1852 Schl\"{a}fli \cite{Sch}
studied relations between $s(n,k)$ and $S(n,k)$.  Then in 1960 Gould
\cite{Gou1} extended Schl\"{a}fli's work by discovering the pair of
dual relations
  \begin{eqnarray*}
  {(-1)^n} S(m,m-n) 
  &=& \sum_{k=0}^{n}  {n+m\choose n-k} {n-m\choose n+k} s(n+k,k), \\
  {(-1)^n} s(m,m-n) 
  &=& \sum_{k=0}^{n}  {n+m\choose n-k}{n-m\choose n+k} S(n+k,k).
  \end{eqnarray*}
Prompted by a recent problem \cite{AMM1} in the \textit{Amer.\ Math.\ 
Monthly} that asked the readers to find a closed form expression for
$\sum_{k=0}^n (-1)^k {2n\choose n+k} s(n+k,k)$, Gould tried to relate
this sum to the first of his dual sums.  By choosing $m = n+1$ and
noting that ${-1\choose n-k} = (-1)^{n+k}$, the first of Gould's
relations yields
  \[ \sum_{k=0}^{n} (-1)^{k} {2n+1\choose n-k}  s(n+k,k) 
  = S(n+1,1) = 1, \]
which is not quite the proposed result but suggested that we study a
wider range of sums. 

Motivated by this and other experiments using Maple, we study the 
following sums: 
  \begin{eqnarray*}
  f_m(n) &=& \sum_{k=0}^{n+m} (-1)^k {2n+m\choose n+k} s(n+k,k), \\
  F_m(n) &=& \sum_{k=0}^{n+m} (-1)^k {2n+m\choose n+k} S(n+k,k), \\
  g_m(n) &=& \sum_{k=0}^n (-1)^k {2n+m\choose n-k} s(n+k,k), \\
  G_m(n) &=& \sum_{k=0}^n (-1)^k {2n+m\choose n-k} S(n+k,k). 
  \end{eqnarray*}
For $m\geq0$, the closed forms for $f_m(n)$ and $F_m(n)$ are easy to 
obtain, but the sums $g_m(n)$ and $G_m(n)$ are more complicated.  We
also study the case of $m<0$.  We shall derive formulas for these
sums, and discuss their connections.  To simplify the notation, define 
  \[ \hf_m(n)=f_{-m}(n), \quad
  \hF_m(n) = F_{-m}(n), \quad
  \hg_m(n) = g_{-m}(n), \quad\mbox{and}\quad
  \hG_m(n) = G_{-m}(n). \]
Consequently, throughout this paper, unless otherwise stated, $m$ will
denote a nonnegative integer, and $n$ a positive integer.

\section{Closed forms for $f_m(n)$ and $F_m(n)$}

We start with $f_0(n)$ and determine its value using a combinatorial
argument.

\begin{theorem}  \label{thm:f0}
For any positive integer,
  \[ f_0(n)
  = \sum_{k=0}^n (-1)^k {2n\choose n+k} s(n,k) 
  = (2n-1)!!, \]
where $(2n-1)!!$ denotes the double factorial $(2n-1)(2n-3)\cdots
3\cdot1$.  
\end{theorem}

\begin{proof}
Recall that the unsigned Stirling number of the first kind $c(n,k) = 
(-1)^{n-k} s(n,k)$ counts the number of $n$-permutations with $k$
disjoint cycles.  Then
  \begin{eqnarray*} 
  f_0(n)
  &=& \sum_{k=0}^n (-1)^k {2n\choose n+k} s(n+k,k) \\
  &=& \sum_{k=0}^n (-1)^{n-k} {2n\choose n-k} c(n+k,k) \\
  &=& \sum_{j=0}^n (-1)^j {2n\choose j} c(2n-j,n-j).
  \end{eqnarray*}
Let $S$ be the set of $2n$-permutations with $n$ cycles, and $A_i$ 
be the subset of permutations of $S$ with $i$ as a fixed point.  Then
  \[ \big|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_j}|
  = c(2n-j,n-j). \]
It follows from the principle of inclusion-exclusion that $f_0(n)$ is
precisely the number of $2n$-permutations without fixed points.  
Notice that if a permutation in $S$ has no fixed point, it must be
a permutation with exactly $n$ transpositions (that is, 2-cycles).
After lining up $2n$ objects, we can take the elements two at a time
to form $n$ transpositions.  Since the order within each transposition
does not matter, it is just a matter of calculating the order among
the transpositions; hence, there are  
  \[ \frac{(2n)!}{n!\,2^n} 
  = (2n-1) (2n-3) \cdots 3\cdot 1
  = (2n-1)!! \]
permutations of $2n$ with exactly $n$ transpositions.  Thus, $f_0(n) =
(2n-1)!!$.  
\end{proof}

The proof suggests we should examine the combinatorial interpretation 
of $f_m(n)$.  Let $c^*(n,k)$ denote the number of $n$-permutations 
with $k$ cycles and no fixed points.  It is called the \emph{unsigned 
associated Stirling number of the first kind} (\cite[p.\ 256]{Com}
and \cite[p.\ 73]{Rio}).  In a similar fashion, we can define 
$S^*(n,k)$ as the number of partitions of an $n$-set into $k$ subsets 
with no singleton subset as any part.  The number $S^*(n,k)$ is the 
\emph{associated Stirling number of the second kind}
(\cite[p.\ 221]{Com} and \cite[p.\ 77]{Rio}).  See \cite{How} for a 
more thorough discussion of the associated Stirling numbers.

\begin{lemma}  \label{lem:fm}
The identity $f_m(n) = (-1)^m c^*(2n+m,n+m)$ holds for any integers
$m$ and $n$ such that $n+m\geq1$.  
\end{lemma}

\begin{proof}
Let $S$ be the set of $(2n+m)$-permutations with $n+m$ cycles, and
$A_i$ be the subset of permutations of $S$ with $i$ as a fixed point.  Then  
  \[ \big|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_j}\big| 
  = c(2n+m-j,n+m-j). \]
Therefore, according to the principle of inclusion-exclusion, 
  \begin{eqnarray*}
  c^*(2n+m,n+m)
  &=& \sum_{j=0}^{n+m} (-1)^j {2n+m\choose j} c(2n+m-j,n+m-j) \\
  &=& \sum_{k=n+m}^0 (-1)^{n+m-k} {2n+m\choose n+m-k} c(n+k,k) \\
  &=& (-1)^m \sum_{k=0}^{n+m} (-1)^k {2n+m\choose n+k} s(n+k,k).
  \end{eqnarray*}
Therefore, $c^*(2n+m,n+m) = (-1)^m f_m(n)$.
\end{proof}

By using an almost identical argument, we obtain a similar result for the 
associated Stirling numbers of the second kind.

\begin{lemma}  \label{lem:Fm}
The identity $F_m(n) = (-1)^{n+m} S^*(2n+m,n+m)$ holds for any integers
$m$ and $n$ such that $n+m\geq1$.  
\end{lemma}

These combinatorial interpretations allow us to determine the exact
values of $f_m(n)$ and $F_m(n)$ for $m\geq0$.  Again, due to their
similarity, we shall only prove the first result.

\begin{theorem}  \label{thm:fm_nonneg}
For any integer $n\geq1$, $f_0(n)=(2n-1)!!$, and $f_m(n)=0$ if $m>0$. 
\end{theorem}

\begin{proof}
Lemma~\ref{lem:fm} states that $f_m(n) = (-1)^m c^*(2n+m,n+m)$.  If
$m>0$, it is clear that $2n+m<2(n+m)$, hence $c^*(2n+m,n+m)=0$.  When 
$m=0$, we have $f_0(n)=c^*(2n,n)$, which counts the number of
permutations with exactly $n$ transpositions.  Hence, $f_0(n) =
(2n-1)!!$. 
\end{proof}

\begin{theorem}  \label{thm:Fm_nonneg}
For any integer $n\geq1$, $F_0(n)=(-1)^n (2n-1)!!$, and $F_m(n)=0$ if
$m>0$. 
\end{theorem}

The same conclusions can be drawn from generating functions.  

\begin{lemma}  \label{lem:gf_cT}
Let $T$ be a nonempty set of positive integers.  Define $c_T(n,k)$ as
the number of $n$-permutations with $k$ disjoint cycles whose lengths
belong to $T$.  Then 
  \[ c_T(x,y) 
  := \sum_{n,k\geq0} c_T(n,k)\,\frac{x^n}{n!}\,y^k
  = \exp\left( y \sum_{j\in T} \frac{x^j}{j} \right). \]
\end{lemma}

\begin{proof}
The result follows easily from the exponential formula \cite{Wil}.
Alternatively, we can prove it directly as follows.  For any
$n$-permutation, let $n_j$ denotes the number of $j$-cycles. 
It is a routine exercise to show that
  \[ c_T(n,k) 
  = {\sum}_T \frac{n!}{\prod_{j\in T} n_j!\,j^{n_j}}, \]
where the summation ${\sum}_T$ is taken over all $n_j\geq0$, where $j\in
T$, such that $\sum_{j\in T} n_j = k$, and $\sum_{j\in T} jn_j = n$.
Then
  \begin{eqnarray*}
  \sum_{n,k\geq0} c_T(n,k)\,\frac{x^n}{n!}\,y^k
  &=& \sum_{n,k\geq0} {\sum}_T 
      \prod_{j\in T} \frac{x^{jn_j}y^{n_j}}{n_j!\,j^{n_j}} \\
  &=& \sum_{n,k\geq0} {\sum}_T 
      \prod_{j\in T} \frac{1}{n_j!} \left(\frac{x^jy}{j}\right)^{n_j}. 
  \end{eqnarray*}
Noting that this is in the form of a convolution, we determine that
  \[ c_T(x,y)
  = \prod_{j\in T} \sum_{n_j\geq0} 
    \frac{1}{n_j!} \left(\frac{x^jy}{j}\right)^{n_j} 
  = \prod_{j\in T} \exp\left(\frac{x^jy}{j}\right)  
  = \exp\left(y\sum_{j\in T} \frac{x^j}{j}\right). \]
\end{proof}

\begin{lemma} \label{lem:gf_ST}
Let $T$ be a nonempty set of positive integers.  Define $S_T(n,k)$ as
the number of ways to partition an $n$-set into $k$ subsets with
cardinalities belonging to $T$.  Then
  \[ S_T(x,y) 
  := \sum_{n,k\geq0} S_T(n,k)\,\frac{x^n}{n!}\,y^k
  = \exp\left( y \sum_{j\in T} \frac{x^j}{j!} \right). \]
\end{lemma}

\begin{proof}
The proof is identical to that of Lemma~\ref{lem:gf_cT}, except that 
  \[ S_T(n,k) 
  = {\sum}_T \frac{n!}{\prod_{j\in T} n_j!\,(j!)^{n_j}}. \]
\end{proof}

For our purpose, we need $T=\N-\{1\}$.  We find
  \begin{equation}
  c^*(x,y)
  := \sum_{n,k\geq0} c^*(n,k)\,\frac{x^n}{n!}\,y^k
  = \exp\left(y \sum_{j\geq2} \frac{x^j}{j}\right)
  = (1-x)^{-y} e^{-xy}, 
  \label{eqn:gf_cstart}
  \end{equation}
and
  \begin{equation}
  S^*(x,y)
  := \sum_{n,k\geq0} S^*(n,k)\,\frac{x^n}{n!}\,y^k
  = \exp\left(y \sum_{j\geq2} \frac{x^j}{j!}\right)
  = e^{y(e^x-1-x)}. 
  \label{eqn:gf_Sstar}
  \end{equation}
From the generating function $c^*(x,y)$, it is clear that the coefficient
of $x^r y^t$ is zero if $r<2t$.  Hence, $f_m(n) = (-1)^m c^*(2n+m,n+m)
= 0$ if $m>0$.  For $m=0$, the coefficient of $\frac{x^{2n}}{(2n)!}\,
y^n$ is $\frac{(2n)!}{n!\,2^n} = (2n-1)!!$.   The argument for
$F_m(n)$ is similar. 

\section{Formulas for $\hf_m(n)$ and $\hF_m(n)$}

Lemma \ref{lem:fm} shows that $f_m(n) = (-1)^m c^*(2n+m,n+m)$.  Its
combinatorial interpretation implies that $f_m(n)$ is nonzero if
$1-n\leq m\leq0$.  We obtain the following result.

\begin{theorem} \label{thm:fm_neg}
For any integer $m$ that satisfies $0<m\leq n-1$, 
  \[ \hf_m(n) = \sum 
  \frac{(-1)^m (2n-m)!}{\prod_{i\geq2} n_i!\,i^{n_i}}, \]
where the summation is taken over all integers $n_2,n_3,n_4,\ldots
\geq0$ such that $\sum_{i\geq2} n_i = n-m$, and $\sum_{i\geq2} in_i =
2n-m$. 
\end{theorem}

We shall present an analytic proof as well as a combinatorial proof. 

\begin{proof}
Since $f_m(n) = (-1)^m c^*(2n+m,n+m)$, we gather from the generating
function $c^*(x,y)$ that $f_m(n)$ is $(-1)^m (2n+m)!$ times the
coefficient of $x^{2n+m} y^{n+m}$ in the power series expansion of
  \[ \exp\left[y\left(
  \frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)\right]
  = \sum_{k=0}^\infty \frac{y^k}{k!} 
  \left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)^k. \]
We conclude that $f_m(n)$ is $(-1)^m (2n+m)!/(n+m)!$ times the
coefficient of $x^{2n+m}$ in the power series expansion of 
  \[ \left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)^{n+m}. \]
For $m<0$, replace $m$ with $-m$.  Then $\hf_m(n)$ is $(-1)^m
(2n-m)!/(n-m)!$ times the coefficient of $x^{2n-m}$ in the expansion  
of the polynomial  
  \[ \left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^2}{4}
  +\cdots\,\right)^{n-m}. \]
Applying the multinomial theorem yields the result immediately.
\end{proof}

Here is an alternate proof.

\begin{proof}
Since $\hf_m(n) = f_{-m}(n) = (-1)^m c^*(2n-m,n-m)$, it suffices to
find a formula for the number of permutations of $2n-m$ with exactly
$n-m$ cycles none of which is a 1-cycle.  Assume there are $n_i$
cycles of length $i$, then $n_2,n_3,n_4,\ldots\geq0$, and 
  \begin{eqnarray*}
  n_2+n_3+n_4+\cdots    &=& n-m, \\
  2n_2+3n_3+4n_4+\cdots &=& 2n-m,
  \end{eqnarray*}
and there are 
  \[ \frac{(2n-m)!}{\prod_{i\geq2} n_i!\,i^{n_i}} \]
such permutations.  This, when combined with the addition principle,
completes the proof. 
\end{proof}

An almost identical argument leads to the next result.

\begin{theorem} \label{thm:Fm_neg}
For any integer $m$ that satisfies $0<m\leq n-1$, 
  \[ \hF_m(n) = \sum 
  \frac{(-1)^{n+m} (2n-m)!}{\prod_{i\geq2} n_i!\,(i!)^{n_i}}, \]
where the summation is taken over all integers $n_2,n_3,n_4,\ldots
\geq0$ such that $\sum_{i\geq2} n_i = n-m$, and $\sum_{i\geq2} in_i =
2n-m$. 
\end{theorem}

In order to use these two results effectively, take note that the two 
conditions on the $n_i$'s imply that
  \[ n_3+2n_4+3n_5+4n_6+\cdots = m. \]
The possible solutions for $0\leq m\leq4$ are summarized below.
  \[ \renewcommand{\arraystretch}{1.65}
  \begin{array}{|*{9}{c|}} \hline
  m & 2n-m & n_2 & n_3 & n_4 & n_5 & n_6
  & \frac{(2n-m)!}{\prod_{i\geq2} n_i!\,i^{n_i}} 
  & \frac{(2n-m)!}{\prod_{i\geq2} n_i!\,(i!)^{n_i}} \\ \hline
  0 & 2n
  & n & 0 & 0 & 0 & 0
  & \frac{(2n)!}{n!\,2^n} 
  & \frac{(2n)!}{n!\,2^n} \\ \hline
  1 & 2n-1
  & n-2 & 1 & 0 & 0 & 0 
  & \frac{(2n-1)!}{3(n-2)!\,2^{n-2}} 
  & \frac{(2n-1)!}{6(n-2)!\,2^{n-2}} \\ \hline
  2 & 2n-2
  & n-3 & 0 & 1 & 0 & 0 
  & \frac{(2n-2)!}{4(n-3)!\,2^{n-3}} 
  & \frac{(2n-2)!}{24(n-3)!\,2^{n-3}} \\ \cline{2-9}
  && n-4 & 2 & 0 & 0 & 0 
  & \frac{(2n-2)!}{18(n-4)!\,2^{n-4}} 
  & \frac{(2n-2)!}{72(n-4)!\,2^{n-4}} \\ \hline
  3 & 2n-3
  & n-4 & 0 & 0 & 1 & 0 
  & \frac{(2n-3)!}{5(n-4)!\,2^{n-4}}
  & \frac{(2n-3)!}{120(n-4)!\,2^{n-4}} \\ \cline{2-9}
  && n-5 & 1 & 1 & 0 & 0
  & \frac{(2n-3)!}{12(n-5)!\,2^{n-5}}
  & \frac{(2n-3)!}{144(n-5)!\,2^{n-5}} \\ \cline{2-9}
  && n-6 & 3 & 0 & 0 & 0
  & \frac{(2n-3)!}{162(n-6)!\,2^{n-6}}
  & \frac{(2n-3)!}{1296(n-6)!\,2^{n-6}} \\ \hline
  4 & 2n-4
  & n-5 & 0 & 0 & 0 & 1
  & \frac{(2n-4)!}{6(n-5)!\,2^{n-5}}
  & \frac{(2n-4)!}{720(n-5)!\,2^{n-5}} \\ \cline{2-9}
  && n-6 & 1 & 0 & 1 & 0 
  & \frac{(2n-4)!}{15(n-6)!\,2^{n-6}}
  & \frac{(2n-4)!}{720(n-6)!\,2^{n-6}} \\ \cline{2-9}
  && n-6 & 0 & 2 & 0 & 0 
  & \frac{(2n-4)!}{32(n-6)!\,2^{n-6}}
  & \frac{(2n-4)!}{1152(n-6)!\,2^{n-6}} \\ \cline{2-9}
  && n-7 & 2 & 1 & 0 & 0
  & \frac{(2n-4)!}{72(n-7)!\,2^{n-7}}
  & \frac{(2n-4)!}{1728(n-7)!\,2^{n-7}} \\ \cline{2-9}
  && n-8 & 4 & 0 & 0 & 0
  & \frac{(2n-4)!}{1944(n-8)!\,2^{n-8}}
  & \frac{(2n-4)!}{31104(n-8)!\,2^{n-8}} \\ \hline
  \end{array} \]
Theorem~\ref{thm:fm_neg} asserts that
  \begin{eqnarray*}
  \hf_1(n) &=& -\frac{(2n-1)!}{3(n-2)!\,2^{n-2}}, \\
  \hf_2(n) &=& \frac{(2n-2)!}{4(n-3)!\,2^{n-3}}
              +\frac{(2n-2)!}{18(n-4)!\,2^{n-4}}, \\
  \hf_3(n) &=&-\frac{(2n-3)!}{5(n-4)!\,2^{n-4}}
              -\frac{(2n-3)!}{12(n-5)!\,2^{n-5}}
              -\frac{(2n-3)!}{162(n-6)!\,2^{n-6}}, \\
  \hf_4(n) &=& \frac{(2n-4)!}{6(n-5)!\,2^{n-5}}
              +\frac{47(2n-4)!}{480(n-6)!\,2^{n-6}}
              +\frac{(2n-4)!}{72(n-7)!\,2^{n-7}}
              +\frac{(2n-4)!}{1944(n-8)!\,2^{n-8}}.
  \end{eqnarray*}
The first few absolute values of each of these four sequences are 
tabulated in Table~\ref{table1}.  All of them appear in the OEIS
\cite{OEIS}.  More information about these sequences, including their
combinatorial meanings, can be found in OEIS.  
\begin{center}
\begin{table}[htb]
\[ \renewcommand{\arraystretch}{1.35}
\begin{array}{|c||*{8}{r|}|c|} \hline
n & 1 \hfil & 2 \hfil & 3 \hfil & 4 \hfil & 5 \hfil 
  & 6 \hfil & 7 \hfil & 8 \hfil & \mbox{OEIS~\#} \\ \hline\hline
\big|\hf_1(n)\big|
& 0 & 2 & 20 & 210 & 2520 & 34650 & 540540 & 9459450 
& \mbox{A000906} \\ \hline
\big|\hf_2(n)\big|
& 0 & 0 & 6 & 130 & 2380 & 44100 & 866250 & 18288270 
& \mbox{A000907} \\ \hline
\big|\hf_3(n)\big|
& 0 & 0 & 0 & 24 & 924 & 26432 & 705320 & 18858840
& \mbox{A001784} \\ \hline
\big|\hf_4(n)\big|
& 0 & 0 & 0 & 0 & 120 & 7308 & 303660 & 11098780
& \mbox{A001785} \\ \hline
\end{array} \]
\caption{The first eight values of $\hf_m(n)$ for $m=1,2,3,4$.}
\label{table1}
\end{table}
\end{center}

Likewise, Theorem~\ref{thm:Fm_neg} yields
  \begin{eqnarray*}
  \hF_1(n) &=& \frac{(-1)^{n+1}(2n-1)!}{6(n-2)!\,2^{n-2}}, \\
  \hF_2(n) &=& \frac{(-1)^n(2n-2)!}{24(n-3)!\,2^{n-3}}
              +\frac{(-1)^n(2n-2)!}{72(n-4)!\,2^{n-4}}, \\
  \hF_3(n) &=& \frac{(-1)^{n+1}(2n-3)!}{120(n-4)!\,2^{n-4}}
              + \frac{(-1)^{n+1}(2n-3)!}{144(n-5)!\,2^{n-5}}
              + \frac{(-1)^{n+1}(2n-3)!}{1296(n-6)!\,2^{n-6}}, \\
  \hF_4(n) &=& \frac{(-1)^n(2n-4)!}{720(n-5)!\,2^{n-5}}
              +\frac{(-1)^n13(2n-4)!}{5760(n-6)!\,2^{n-6}}
              +\frac{(-1)^n(2n-4)!}{1728(n-7)!\,2^{n-7}}
              +\frac{(-1)^n(2n-4)!}{31104(n-8)!\,2^{n-8}}.
  \end{eqnarray*}
See Table~\ref{table2}.  The last sequence does not appear in the
OEIS.  Note that $|\hf_1(n)|=2|\hF_1(n)|$.  We leave it as an exercise
to the readers to find a combinatorial explanation.
\begin{center}
\begin{table}[htb]
\[ \renewcommand{\arraystretch}{1.35}
\begin{array}{|c||*{8}{r|}|c|} \hline
n & 1 \hfil & 2 \hfil & 3 \hfil & 4 \hfil & 5 \hfil 
  & 6 \hfil & 7 \hfil & 8 \hfil & \mbox{OEIS~\#} \\ \hline\hline
\big|\hF_1(n)\big|
& 0 & 1 & 10 & 105 & 1260 & 17325 & 270270 & 4729725
& \mbox{A000457} \\ \hline
\big|\hF_2(n)\big|
& 0 & 0 & 1 & 25 & 490 & 9450 & 190575 & 4099095 
& \mbox{A000497} \\ \hline
\big|\hF_3(n)\big|
& 0 & 0 & 0 & 1 & 56 & 1918 & 56980 & 1636635 
& \mbox{A000504} \\ \hline
\big|\hF_4(n)\big|
& 0 & 0 & 0 & 0 & 1 & 119 & 6825 & 302995 
& \mbox{---} \\ \hline
\end{array} \]
\caption{The first eight values of $\hF_m(n)$ for $m=1,2,3,4$.}
\label{table2}
\end{table}
\end{center}

\section{Formulas for $\hg_m(n)$ and $\hG_m(n)$}

Next, we study the combinatorial significance of the two sums 
  \begin{eqnarray*}
  \hg_m(n) &=& \sum_{k=0}^n (-1)^k {2n-m\choose n-k} s(n+k,k), \\
  \hG_m(n) &=& \sum_{k=0}^n (-1)^k {2n-m\choose n-k} S(n+k,k), 
  \end{eqnarray*}
where $m$ is a nonnegative integer, an $n$ a positive integer such
that $2n\geq m$.

Recall that the unsigned Stirling number of the first kind $c(n,k) =
(-1)^{n-k} s(n,k)$ counts the number of $n$-permutations with $k$
disjoint cycles.  We find
  \begin{eqnarray*}
  \hg_m(n)
  &=& \sum_{k=0}^n (-1)^k {2n-m\choose n-k} s(n+k,k) \\
  &=& \sum_{k=0}^n (-1)^k {2n-m\choose n+k-m} s(n+k,k) \\
  &=& \sum_{k=0}^n (-1)^{n-k} {2n-m\choose 2n-k-m} s(2n-k,n-k) \\
  &=& \sum_{k=0}^n (-1)^{n-k} {2n-m\choose k} s(2n-k,n-k) \\
  &=& \sum_{k=0}^n (-1)^k {2n-m\choose k} c(2n-k,n-k).
  \end{eqnarray*}
Similarly, we have
  \[ \hG_m(n)
  = (-1)^n \sum_{k=0}^n (-1)^k {2n-m\choose k} S(2n-k,n-k), \]
where the Stirling number of the second kind $S(n,k)$ counts the
number of ways to partition an $n$-set into $k$ nonempty subsets.   

For any positive integer $m$, define $[m]=\{1,2,\ldots,m\}$.  Let $n$
be a fixed positive integer.  For any nonnegative integer $m$,
define $\cS_m$ as the set of permutations of $[2n]$ with $n$ cycles
and no fixed points among $[2n-m]$.  Recall that if a permutation in
$\cS_m$ has no fixed point, it must be a permutation with exactly $n$
transpositions (that is, 2-cycles).  In addition, the fixed points in
any permutation from $\cS_m$ must belong to $[2n]\setminus[2n-m]$;
this implies that the permutations in $\cS_m$ has at most $m$ fixed
points. 

In an analogous manner, define $\hcS_m$ as the set of partitions of
$[2n]$ into $n$ nonempty subsets none of which is a singleton subset
of $[2n-m]$.  If a partition in $\hcS_m$ has no singleton subset, it
must have $n$ parts, each of which a 2-subset.  If a partition in
$\hcS_m$ has a singleton subset, its element must be among $[2n]
\setminus [2n-m]$, hence it has at most $m$ singleton subsets as
its parts.

We first us the same argument in Theorem~\ref{thm:f0} to derive two
preliminary results about $|\cS_m|$ and $\big|\hcS_m\big|$.   

\begin{lemma}  \label{lem:ga}
For positive integers $m$ and $n$ that satisfy $2n\geq m$, 
  \[ \hg_m(n) 
  = \sum_{k=0}^n (-1)^k {2n-m\choose n-k} s(n+k,k)
  = |\cS_m|. \]
\end{lemma}

\begin{proof}
In light of our earlier discussion, it suffices to show that
  \[ |\cS_m|
  = \sum_{k=0}^n (-1)^k {2n-m\choose k} c(2n-k,n-k). \]
Let $S$ be the set of all permutations of $[2n]$ with $n$ cycles,
without any restriction.  For each $j\in[2n-m]$, define $A_j$ 
to be the set of permutations of $[2n]$ with $j$ as a fixed point.  If
a permutation belongs to $A_{i_1}\cap A_{i_2} \cap\cdots\cap A_{i_k}$,
it still has $n-k$ cycles whose elements come from $[2n] \setminus
\{i_1,i_2,\ldots,i_k\}$.  Thus, 
  \[ \big|A_{i_1}\cap A_{i_2} \cap \cdots \cap A_{i_k}\big|
  = c(2n-k,n-k), \]
and there are ${2n-m\choose k}$ choices for $\{i_1,i_2,\ldots,i_k\}$.
Since the permutations in $S$ comprise of $n$ cycles, we obviously need
$0\leq k\leq n$.  The result now follows from the principle of
inclusion-exclusion. 
\end{proof}

It is clear that a similar result for $\big|\hcS_m\big|$ also holds.

\begin{lemma}  \label{lem:Ga}
For positive integers $m$ and $n$ that satisfy $2n\geq m$, 
  \[ \hG_m(n) 
  = \sum_{k=0}^n (-1)^k {2n-m\choose n-k} S(n+k,k)
  = (-1)^n \big|\hcS_m\big|. \]
\end{lemma}

\begin{theorem}  \label{thm:ga}
For positive integers $m$ and $n$ that satisfy $2n\geq m$, 
  \[ \hg_m(n) 
  = \sum_{j=0}^m {m\choose j} c^*(2n-j,n-j) 
  = \sum_{j=0}^m {m\choose j} \sum
   \frac{(2n-j)!}{\prod_{i\geq2} n_i!\,i^{n_i}}, \]
where the inner sum $\sum$ is taken over all integers $n_2,n_3,n_4, 
\ldots\geq0$ such that $\sum_{i\geq2} n_i = n-j$, and $\sum_{i\geq2}
in_i = 2n-j$.   
\end{theorem}

\begin{proof}
We need to determine $|\cS_m|$.  Let $j$ be the number of fixed points
in a permutation from $\cS_m$.  Since the fixed points come from $[2n]
\setminus [2n-m]$, there are ${m\choose j}$ ways to choose these fixed
points.  The other $2n-j$ elements form $n-j$ cycles, all with length
at least~2.  Assume there are $n_i$ cycles of length $i$, then
$n_2,n_3,\ldots\geq0$, and 
  \begin{eqnarray*}
  n_2+n_3+n_4+\cdots    &=& n-j, \\
  2n_2+3n_3+4n_4+\cdots &=& 2n-j,
  \end{eqnarray*}
and there are 
  \[ \frac{(2n-j)!}{\prod_{i\geq2} n_i!\,i^{n_i}} \]
such permutations.  The proof is completed by applying the addition
principle, and recalling that $0\leq j\leq m$.
\end{proof}

Notice that the sum $\sum (2n-j)! / \prod_{i\geq2} n_i!\,i^{n_i}$
also appeared in the last section.  It is equal to $c^*(2n-j,n-j)$.    
Then, according to Theorem~\ref{thm:ga}, 
  \begin{eqnarray*}
  \hg_1(n)
  &=& \frac{(2n)!}{n!\,2^n} 
      + \frac{(2n-1)!}{3(n-2)!\,2^{n-2}}, \\
  \hg_2(n)
  &=& \frac{(2n)!}{n!\,2^n} 
      + \frac{2(2n-1)!}{3(n-2)!\,2^{n-2}} 
      + \frac{(2n-2)!}{4(n-3)!\,2^{n-3}}       
      + \frac{(2n-2)!}{18(n-4)!\,2^{n-4}}, \\
  \hg_3(n)
  &=& \frac{(2n)!}{n!\,2^n} 
      + \frac{(2n-1)!}{(n-2)!\,2^{n-2}} 
      + \frac{3(2n-2)!}{4(n-3)!\,2^{n-3}}       
      + \frac{(2n-2)!}{6(n-4)!\,2^{n-4}} \\
  & & {}
      + \frac{(2n-3)!}{5(n-4)!\,2^{n-4}}
      + \frac{(2n-3)!}{12(n-5)!\,2^{n-5}}
      + \frac{(2n-3)!}{162(n-6)!\,2^{n-6}}, \\
  \hg_4(n)
  &=& \frac{(2n)!}{n!\,2^n} 
      + \frac{4(2n-1)!}{3(n-2)!\,2^{n-2}} 
      + \frac{3(2n-2)!}{2(n-3)!\,2^{n-3}}       
      + \frac{(2n-2)!}{3(n-4)!\,2^{n-4}} \\
  & & {}
      + \frac{4(2n-3)!}{5(n-4)!\,2^{n-4}}
      + \frac{(2n-3)!}{3(n-5)!\,2^{n-5}}
      + \frac{2(2n-3)!}{81(n-6)!\,2^{n-6}} \\ 
  & & {}
      + \frac{(2n-4)!}{6(n-5)!\,2^{n-5}}
      + \frac{47(2n-4)!}{480(n-6)!\,2^{n-6}}
      + \frac{(2n-4)!}{72(n-7)!\,2^{n-7}} \\
  & & {}
      + \frac{(2n-4)!}{1944(n-8)!\,2^{n-8}}.      
  \end{eqnarray*}
It is easy to verify that 
  \[ \hg_1(n) = \frac{(2n+1)!!}{3}. \]
Since $\hg_0(n)=(2n-1)!!$, we find 
  \[ 3\hg_1(n) = \hg_0(n+1). \]
We invite the readers to find a combinatorial proof of this simple
identity.  We also find
  \begin{eqnarray*}
  \hg_2(n)
  &=& \frac{1}{9}\,(4n^3+9n^2-n-3)(2n-3)!! \\
  &=& \frac{1}{18}\,(2n+3)!!+\frac{1}{12}\,(2n+1)!!
     -\frac{1}{12}\,(2n-3)!!.
  \end{eqnarray*}
It becomes clear that $\hg_m(n)$ can be written as a linear combination
of the double falling factorials of the form $m!!$ for some odd
integers $m$.  We invite the readers to devise a combinatorial
argument to find its coefficients.

The sequence $\{\hg_1(n)\}_{n\geq1}$ appears in the OEIS \cite{OEIS} as
Sequence A051577, but the other sequences $\{\hg_2(n)\}_{n\geq1}$, 
$\{\hg_3(n)\}_{n\geq1}$, and $\{\hg_4(n)\}_{n\geq1}$ do not appear in the
OEIS.  Their numeric values for $n\leq8$ are listed in
Table~\ref{table3}. 

\begin{center}
\begin{table}[htb]
\[ \renewcommand{\arraystretch}{1.35}
\begin{array}{|c||*{8}{r|}|c|} \hline
n & 1 \hfil & 2 \hfil & 3 \hfil & 4 \hfil & 5 \hfil 
  & 6 \hfil & 7 \hfil & 8 \hfil & \mbox{OEIS~\#} \\ \hline\hline
\hg_1(n)
& 1 & 5 & 35 & 315 & 3465 & 45045 & 675675 & 11486475 
& \mbox{A051577} \\ \hline
\hg_2(n)
& 1 & 7 & 61 & 655 & 8365 & 123795 & 2082465 & 39234195 
& \mbox{---} \\ \hline
\hg_3(n)
& 1 & 9 & 93 & 1149 & 16569 & 273077 & 5060825 & 104129025 
& \mbox{---} \\ \hline
\hg_4(n)
& 1 & 11 & 131 & 1821 & 29121 & 526631 & 10619735 & 236128585 
& \mbox{---} \\ \hline
\end{array} \]
\caption{The first eight values of $\hg_m(n)$ for $m=1,2,3,4$.}
\label{table3}
\end{table}
\end{center}

A similar argument yields the next result.

\begin{theorem}  \label{thm:Ga}
For positive integers $m$ and $n$ that satisfy $2n\geq m$, 
  \[ \hG_m(n) 
  = \sum_{j=0}^m (-1)^n {m\choose j} S^*(2n-j,n-j) 
  = \sum_{j=0}^m {m\choose j} \sum
  \frac{(-1)^n (2n-j)!}{\prod_{i\geq2} n_i!\,(i!)^{n_i}}, \]
where the inner sum $\sum$ is taken over all integers $n_2,n_3,n_4,
\ldots\geq0$ such that $\sum_{i\geq2} n_i = n-j$, and $\sum_{i\geq2}
in_i = 2n-j$.  
\end{theorem}

Theorem~\ref{thm:Ga} yields the following:
  \begin{eqnarray*}
  \hG_1(n)
  &=& \frac{(-1)^n (2n)!}{n!\,2^n}
      + \frac{(-1)^n (2n-1)!}{6(n-2)!\,2^{n-2}}, \\
  \hG_2(n)
  &=& \frac{(-1)^n (2n)!}{n!\,2^n}
      + \frac{(-1)^n (2n-1)!}{3(n-2)!\,2^{n-2}} 
      + \frac{(-1)^n (2n-2)!}{24(n-3)!\,2^{n-3}} 
      + \frac{(-1)^n (2n-2)!}{72(n-4)!\,2^{n-4}}, \\
  \hG_3(n)
  &=& \frac{(-1)^n (2n)!}{n!\,2^n} 
      + \frac{(-1)^n (2n-1)!}{2(n-2)!\,2^{n-2}} 
      + \frac{(-1)^n (2n-2)!}{8(n-3)!\,2^{n-3}} 
      + \frac{(-1)^n (2n-2)!}{24(n-4)!\,2^{n-4}} \\ 
  & & {}
      + \frac{(-1)^n (2n-3)!}{120(n-4)!\,2^{n-4}} 
      + \frac{(-1)^n (2n-3)!}{144(n-5)!\,2^{n-5}} 
      + \frac{(-1)^n (2n-3)!}{1296(n-6)!\,2^{n-6}}, 
  \end{eqnarray*}
  \begin{eqnarray*}
  \hG_4(n)
  &=& \frac{(-1)^n (2n)!}{n!\,2^n} 
      + \frac{(-1)^n 2(2n-1)!}{3(n-2)!\,2^{n-2}} 
      + \frac{(-1)^n (2n-2)!}{4(n-3)!\,2^{n-3}} 
      + \frac{(-1)^n (2n-2)!}{12(n-4)!\,2^{n-4}} \\
  & & {}
      + \frac{(-1)^n (2n-3)!}{30(n-4)!\,2^{n-4}} 
      + \frac{(-1)^n (2n-3)!}{36(n-5)!\,2^{n-5}} 
      + \frac{(-1)^n (2n-3)!}{324(n-6)!\,2^{n-6}} \\
  & & {}
      + \frac{(-1)^n (2n-4)!}{720(n-5)!\,2^{n-5}} 
      + \frac{(-1)^n 13(2n-4)!}{5760(n-6)!\,2^{n-6}} 
      + \frac{(-1)^n (2n-4)!}{1728(n-7)!\,2^{n-7}} \\
  & & {}
      + \frac{(-1)^n (2n-4)!}{31104(n-8)!\,2^{n-8}}.
  \end{eqnarray*}
The first eight absolute values of each sequence are tabulated in
Table~\ref{table4}.  None of these sequences appear in the OEIS.  

\begin{center}
\begin{table}[htb]
\[ \renewcommand{\arraystretch}{1.35}
\begin{array}{|c||*{8}{r|}|c|} \hline
n & 1 \hfil & 2 \hfil & 3 \hfil & 4 \hfil & 5 \hfil 
  & 6 \hfil & 7 \hfil & 8 \hfil & \mbox{OEIS~\#} \\ \hline\hline
\big|\hG_1(n)\big|
& 1 & 4 & 25 & 210 & 2205 & 27720 & 405405 & 6756750 
& \mbox{---} \\ \hline
\big|\hG_2(n)\big|
& 1 & 5 & 36 & 340 & 3955 & 54495 & 866250 & 15585570
& \mbox{---} \\ \hline
\big|\hG_3(n)\big|
& 1 & 6 & 48 & 496 & 6251 & 92638 & 1574650 & 30150120
& \mbox{---} \\ \hline
\big|\hG_4(n)\big|
& 1 & 7 & 61 & 679 & 9150 & 144186 & 2594410 & 52390030
& \mbox{---} \\ \hline
\end{array} \]
\caption{The first eight values of $\hG_m(n)$ for $m=1,2,3,4$.}
\label{table4}
\end{table}
\end{center}

\section{Connections between the sums}

Theorem~\ref{thm:ga} states that $\hg_m(n) = \sum_{j=0}^m {m\choose j}
c^*(2n-j,n-j)$.  Together with Lemma~\ref{lem:fm} which implies
$c^*(2n-j,n-j) = (-1)^j \hf_j(n)$, we immediately obtain the identity  
  \[ \hg_m(n)
  = \sum_{j=0}^m (-1)^j {m\choose j} \hf_j(n). \]
Likewise, we also have 
  \[ \hG_m(n)
  = \sum_{j=0}^m (-1)^j {m\choose j} \hF_j(n). \]
Using the binomial inversion formula (see, for example, \cite{Aig}),
we also obtain 
  \begin{eqnarray*}
  \hf_m(n) &=& \sum_{j=0}^m (-1)^j {m\choose j} \hg_j(n), \\
  \hF_m(n) &=& \sum_{j=0}^m (-1)^j {m\choose j} \hG_j(n). 
  \end{eqnarray*}

Symbolically, we can apply the idea from umbral calculus \cite{RR} to 
abbreviate these results as 
  \begin{eqnarray*}
  \hg_m(n) &=& L\Big(\big(1-\hf(n)\big)^m\Big), \\
  \hG_m(n) &=& L\Big(\big(1-\hF(n)\big)^m\Big), \\
  \hf_m(n) &=& L\Big(\big(1-\hg(n)\big)^m\Big), \\
  \hF_m(n) &=& L\Big(\big(1-\hG(n)\big)^m\Big).
  \end{eqnarray*}
where $L$ is the linear operator that maps $t(n)^j$ to $t_j(n)$.

\section{Formulas for $g_m(n)$ and $G_m(n)$}

Let $S_1(n,k)$ denote the sum of the ${n\choose k}$ products composed
of $k$ distinct factors from $[n]$, and $S_2(n,k)$ the sum of the
${n-k+1\choose k}$ possible products (repetition allowed) of $k$
factors from $[n]$.  It is obvious that
  \[ \sum_{k=0}^\infty S_1(n,k)\,x^k
  = \prod_{j=1}^n (1+jx), 
  \qquad\mbox{and}\qquad 
  \sum_{k=0}^\infty S_2(n,k)\,x^k
  = \prod_{j=1}^n \frac{1}{1-jx}. \]
Comparing them to the well-known identities 
  \[ \sum_{k=0}^\infty s(n,k)\,x^k
  = \prod_{j=0}^{n-1} (x-j),
  \qquad\mbox{and}\qquad
  \sum_{n=k}^\infty S(n,k)\,x^n 
  = \prod_{j=1}^k \frac{x}{1-jx}, \]
it is not difficult to see that 
  \begin{equation}
  S_1(n,k) = (-1)^k s(n+1,n+1-k),
  \label{eqn:S1Stir1}
  \end{equation}
and
  \begin{equation}
  S_2(n,k) = S(n+k,n).
  \label{eqn:S2Stir2}
  \end{equation}
Their equivalent forms also appear on \cite[pages~71 and~72]{Gou2}. 

Gould obtained \cite[Equation~1.9]{Gou1}
  \[ \sum_{k=0}^n {n-\ell\choose n+k} {n+\ell\choose n-k} S_1(n+k-1,n)
  = S_2(\ell-n,n), \]
and proved the following identity \cite[Equation~1.4]{Gou1} from
\cite{Sch}:  
  \[ \sum_{k=0}^n {n-\ell\choose n+k} {n+\ell\choose n-k} S_2(k,n)
  = S_1(\ell-1,n). \]
Applying (\ref{eqn:S1Stir1}) and (\ref{eqn:S2Stir2}) to them yields
the identities
  \[ \sum_{k=0}^n {n-\ell\choose n+k} {n+\ell\choose n-k} s(n+k,k)
  = (-1)^n S(\ell,\ell-n), \]
and
  \[ \sum_{k=0}^n {n-\ell\choose n+k} {n+\ell\choose n-k} S(n+k,k)
  = (-1)^n s(\ell,\ell-n). \]
These are the two identities mentioned in the Introduction.  Sun
recently derived similar results \cite[Theorem~2.3]{Sun} that relate 
the Stirling numbers of the same kind.  We note that his results are
implied by those found in \cite{Gou1}.   

Setting $\ell=n+m$ leads to the next key result. 

\begin{lemma}  \label{lem:StirStir}
The following identities 
  \begin{eqnarray}
  \sum_{k=0}^n {-m\choose n+k} {2n+m\choose n-k} s(n+k,k)
  &=& (-1)^n S(n+m,m), 
  \label{eqn:Stir1Stir2} \\
  \sum_{k=0}^n {-m\choose n+k} {2n+m\choose n-k} S(n+k,k)
  &=& (-1)^n s(n+m,m),
  \label{eqn:Stir2Stir1}
  \end{eqnarray}
hold for all positive integers $m$.
\end{lemma}

Since ${-1\choose n+k} = (-1)^{n+k}$, $S(n+1,1)=1$, and $s(n+1,1) =
(-1)^n n!$, Lemma~\ref{lem:StirStir} immediately yields the formulas 
for $g_1(n)$ and $G_1(n)$.

\begin{theorem}  \label{thm:g1G1}
For all positive integers $n$, 
  \[ g_1(n) = \sum_{k=0}^n (-1)^k {2n+1\choose n-k} s(n+k,k) 
  = 1, \]
and
  \[ G_1(n) = \sum_{k=0}^n (-1)^k {2n+1\choose n-k} S(n+k,k) 
  = (-1)^n n!. \]
\end{theorem}

For $m>1$, the simplification becomes more complicated.

\begin{theorem}  \label{thm:g2}
For all positive integers $n$, 
  \[ g_2(n) = \sum_{k=0}^n (-1)^k {2n+2\choose n-k} s(n+k,k) 
  = 2n+3-2^{n+1}. \]
\end{theorem}

\begin{proof}
Since ${-2\choose n+k} = (-1)^{n+k} (n+k+1)$, and $S(n+2,2)
= 2^{n+1}-1$, we deduce from (\ref{eqn:Stir1Stir2}) that 
  \[ \sum_{k=0}^n (-1)^k (n+k+1) {2n+2\choose n-k} s(n+k,k)
  = 2^{k+1}-1. \]
From $(n+k+2) {2n+2\choose n-k} = (2n+2) {2n+1\choose n-k}$, we obtain 
  \[ (n+k+1) {2n+2\choose n-k}
  = (2n+2) {2n+1\choose n-k} - {2n+2\choose n-k}. \]
Thus, we can further reduce the previous identity to 
  \[ (2n+2) g_1(n) - g_2(n) = 2^{n+1}-1, \]
which completes the proof because $g_1(n)=1$.
\end{proof}

Encouraged by what we found, we used a computer algebra system to
compute the value of $g_m(n)$ for $m=1,2,3,4,5$.  This led us to 
the following conclusion:

\begin{theorem}  \label{thm:gm}
For any positive integer $m$,
  \[ g_m(n) 
  = \sum_{j=1}^m (-1)^{j-1} {2n+m\choose m-j} S(n+j,j). \]
\end{theorem}

\begin{proof}
It follows from (\ref{eqn:Stir1Stir2}) that, for $j\geq1$,
  \begin{eqnarray*}
  S(n+j,j)
  &=& (-1)^n \sum_{k=0}^n {-j\choose n+k} {2n+j\choose n-k} s(n+k,k) \\
  &=& \sum_{k=0}^n (-1)^k {n+k+j-1\choose n+k} {2n+j\choose n-k} s(n+k,k).
  \end{eqnarray*}
Therefore,
  \begin{eqnarray*}
  \lefteqn{\sum_{j=1}^m (-1)^{j-1} {2n+m\choose m-j} S(n+j,j)} \\
  &=& \sum_{j=1}^m (-1)^{j-1} {2n+m\choose m-j} 
      \sum_{k=0}^n (-1)^k 
      {n+k+j-1\choose n+k} {2n+j\choose n-k} s(n+k,k) \\
  &=& \sum_{k=0}^n (-1)^k {2n+m\choose n-k} s(n+k,k)
      \sum_{j=1}^m (-1)^{j-1} {n+m+k\choose m-j} {n+k+j-1\choose n+k}.
  \end{eqnarray*}
Using Vandermonde convolution (see, for example,
\cite[Equation~3.1]{Gou3}), the inner sum simplifies to 
  \begin{eqnarray*}
  \sum_{j=1}^m (-1)^{j-1} {n+m+k\choose m-j} {n+k+j-1\choose n+k}
  &=& \sum_{j=1}^m (-1)^{j-1} {n+m+k\choose m-j} {n+k+j-1\choose j-1} \\
  &=& \sum_{j=1}^m {n+m+k\choose m-j} {-n-k-1\choose j-1} \\
  &=& {m-1\choose m-1},
  \end{eqnarray*}
from which the desired result follows.
\end{proof}

When $m=1,2$, the formulas reduce to those in Theorems~\ref{thm:g1G1}
and~\ref{thm:g2}.  We also find 
  \[ g_3(n)
  = {2n+3\choose2} S(n+1,1) - (2n+3)\,S(n+2,2) + S(n+3,3). \]
Using an analogous argument, we obtain the following result.

\begin{theorem}  \label{thm:Gm}
For any positive integer $m$,
  \[ G_m(n) 
  = \sum_{j=1}^m (-1)^{j-1} {2n+m\choose m-j} s(n+j,j). \]
\end{theorem}

Accordingly, 
  \begin{eqnarray*}
  G_2(n) &=& (2n+2)\,s(n+1,1) - s(n+2,2), \\
  G_3(n) &=& {2n+3\choose2} s(n+1,1) - (2n+3)\,s(n+2,2) + s(n+3,3).
  \end{eqnarray*}
While the similarity between the formulas for $g_m(n)$ and $G_m(n)$ is
striking, there is an important difference between them.  It is
well-known (see, for example, \cite[Equation~77]{Gou2}) that
  \[ S(n,k) = \frac{1}{k!}
  \sum_{j=0}^k (-1)^{k-j} {k\choose j} j^n. \]
This suggests that it is possible to find a closed form for $g_m(n)$
without any reference to $S(n,k)$.  For example, after simplification, 
  \[ g_3(n)
  = 2n^2+7n+4-2^{n+1}(2n-5) - \frac{3^n}{2}. \]
The same cannot be said of $G_m(n)$, because there does not exist a
simple summation formula for $s(n,k)$.  

We invite interested readers to find alternative combinatorial and/or
generating function proofs which provide closed forms for $g_m(n)$ and
$G_m(n)$ for $m>0$.

\section{Acknowledgments}

We would like to express our appreciation to the anonymous referee for
his/her helpful comments and suggestions.

\begin{thebibliography}{99}

\bibitem{Aig}
M. Aigner, \textit{Combinatorial Theory}, Springer-Verlag, 1979.  

\bibitem{Com}
L. Comtet, \textit{Advanced Combinatorics}, Reidel, 1974.

\bibitem{Gou1} 
H. W. Gould, Stirling number representation problems, \textit{Proc.\
Amer.\ Math.\ Soc.} \textbf{11} (1960), 447--451.   

\bibitem{Gou2} 
H. W. Gould, \textit{Topics in Combinatorics}, Second Edition,
Morgantown, WV, 2000. 

\bibitem{Gou3} 
H. W. Gould, \textit{Combinatorial Identities, A Standardized Set of
Tables Listing 500 Binomial Coefficient Summations}, Revised Edition,
published by the author, Morgantown, WV, 1972.

\bibitem{How}
F. T. Howard, Associated Stirling numbers, \textit{Fibonacci Quart.}
\textbf{18} (1980), 303--315. 

\bibitem{AMM1} 
M. Kauers and S.-L. Ko, Problem 11545, \textit{Amer.\ Math. Monthly}  
\textbf{118} (2011), 84. 

\bibitem{Rio}
J. Riordan, \textit{An Introduction to Combinatorial Analysis},
John Wiley, 1958.

\bibitem{RR}
S. M. Roman and G. C. Rota, The umbral calculus, \textit{Advances in
Math.} \textbf{27} (1978), 95--188.  

\bibitem{Sch} 
L. Schl\"{a}fli, Sur les coefficients du d\'{e}veloppement du produit
$1(1+x)(1+2x)\cdots(1+(n-1)x)$ suivant les puissance ascendantes de
$x$, \textit{J. Reine Angew.\ Math.} \textbf{43} (1852), 1--22.

\bibitem{AMM2} 
J. Simons and K. McInturff, Solutions to Problem 11545, \textit{Amer.\
Math. Monthly} \textbf{119} (2012), 885--886. 

\bibitem{OEIS}
N. A. J. Sloane, \textit{The Online Encyclopedia of Integer Sequences},
https://oeis.org.  

\bibitem{Stir}
J. Stirling, \textit{Methodus Differentialis: sive Tractatus de
Summatione et Interpolatione Serierum Infinitarum}, 1730. 

\bibitem{Sun}
Z.-H.\ Sun, Some inversion formulas and formulas for Stirling numbers,
\textit{Graphs Combin.} \textbf{29} (2013), 1087--1100.

\bibitem{Wil}
H. S. Wilf, \textit{generatingfunctionology}, Academic Press, 1990.

\end{thebibliography} 

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B73; Secondary 11B65, 05A10.

\noindent \emph{Keywords: } 
Stirling number of first kind, Stirling number of second kind,
binomial coefficient.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000457},
\seqnum{A000497},
\seqnum{A000504}, 
\seqnum{A000906}, 
\seqnum{A000907}, 
\seqnum{A001784},
\seqnum{A001785}, and 
\seqnum{A051577}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 25 2015;
revised versions received  August 14 2015; August 19 2015.
Published in {\it Journal of Integer Sequences}, August 20 2015.

\bigskip
\hrule
\bigskip

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


\end{document}