\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 Identities for Generalized Whitney \\
\vskip .1in
and Stirling Numbers} \vskip 1cm
\large
Mark Shattuck\\
Institute for Computational Science \\
and \\
Faculty of Mathematics and Statistics\\
Ton Duc Thang University\\
Ho Chi Minh City\\
Vietnam\\
\href{mailto:mark.shattuck@tdt.edu.vn}{\tt mark.shattuck@tdt.edu.vn}\\
\end{center}

\vskip .2 in
\begin{abstract}
In this paper, we prove by algebraic methods two further formulas
satisfied by the  $r$-Whitney numbers of the second kind, which have
been an object of recent study.  We establish a version of one of the
formulas for a polynomial generalization of the $r$-Whitney numbers.
As special cases, we obtain apparently new identities for the Stirling
numbers of the second kind and the Bell numbers.  Moreover, one may
obtain analogous formulas for Lah numbers and Stirling numbers of the
first kind.  \end{abstract}


\section{Introduction}

The $r$-\emph{Whitney numbers of the second kind}, which will be denoted by $W(n,k)=W(n,k;r,m)$, were studied by Cheon and Jung \cite{Ch}, where several algebraic properties are found (also see \cite{MeR}).  The $W(n,k)$ are connection constants in the polynomial identities
$$(mx+r)^n=\sum_{k=0}^n W(n,k)m^k(x)_k, \qquad n \geq 0,$$
where $(x)_k=x(x-1)\cdots (x-k+1)$ if $k \geq 1$, with $(x)_0=1$.  The parameter $r$ is usually taken to be a non-negative integer and the parameter $m$ a positive integer, but both may also be regarded as indeterminates.  Equivalently, the $W(n,k)$ are defined by the recurrence
$$W(n,k)=W(n-1,k-1)+(r+mk)W(n-1,k), \qquad n,k \geq 1,$$
with initial values $W(n,0)=r^n$ and $W(0,k)=\delta_{k,0}$ for $n,k \geq 0$.  The $r$-\emph{Dowling numbers} $D(n)=D(n;r,m)$ \cite{Ch} are defined as $D(n)=\sum_{k=0}^nW(n,k)$ for $n \geq0$.

The $r=1$ case of the $r$-Whitney and $r$-Dowling numbers are known simply as \emph{Whitney} and \emph{Dowling numbers}; see, e.g., \cite{Be1,Be2,Ra} for various properties.  When $r=0$ and $m=1$, the $r$-Whitney and $r$-Dowling numbers reduce, respectively, to the Stirling numbers of the second kind and to the Bell numbers (see sequences \seqnum{A008277} and \seqnum{A000110} in OEIS \cite{Slo}), which we will denote here by $S(n,k)$ and $B(n)$.  See \cite{MSc} and references contained therein for various generalizations of $S(n,k)$ and $B(n)$.  When $m=1$, the $W(n,k)$ and $D(n)$ reduce to the $r$-Stirling numbers \cite{Br} of the second kind and to the $r$-Bell numbers \cite{Me}.

In the next two sections of this paper, we prove two new identities for the $r$-Whitney and $r$-Dowling numbers.  We use generating function techniques to establish our results.  As special cases, we will obtain recurrence formulas for the Stirling and Bell numbers, which are also given combinatorial proofs.  For one of the identities, we in fact prove a polynomial generalization involving a recently introduced $(p,q)$-analogue \cite{MRS} of $W(n,k)$; also see \cite{MK} for a related $q$-analogue. This result (Theorem \ref{s2t1} below) is seen to generalize the well-known Stirling number recurrence \cite[Identity 1.11]{Wag} given by
$$S(n+1,k+1)=\sum_{i=0}^n\binom{n}{i}S(i,k), \qquad n,k \geq 0,$$
upon suitably selecting the parameters.  The comparable formula for the $r$-Dowling numbers (Corollary \ref{s2c1} below) is seen to generalize the Bell number recurrence \cite[p.\ 34]{St} given by
$$B(n+1)=\sum_{i=0}^n\binom{n}{i}B(i), \qquad n \geq 0.$$
We conclude by noting analogues of our results that hold for the Stirling numbers of the first kind and Lah numbers.


\section{Generalized $r$-Whitney formula}

In this section, we prove a formula for a polynomial generalization of the $r$-Whitney numbers.  Given an indeterminate $q$, let $[n]_q=1+q+\cdots+q^{n-1}$ if $n\geq 1$, with $[0]_q=0$.  Let $W_{p,q}(n,k)=W_{p,q}(n,k;r,m)$ denote the sequence of polynomials defined recursively by
$$W_{p,q}(n,k)=W_{p,q}(n-1,k-1)+([r]_p+m[k]_q)W_{p,q}(n-1,k), \qquad n,k \geq 1,$$
with $W_{p,q}(n,0)=[r]_p^n$ and $W_{p,q}(0,k)=\delta_{k,0}$ for $n,k \geq 0$, see \cite{MRS}.  Note that $W_{p,q}(n,k)$ reduces to $W(n,k)$ when $p=q=1$.  The column generating function for $W_{p,q}(n,k)$ is given by
\begin{equation}\label{s2e1}
\sum_{n\geq k}W_{p,q}(n,k)x^n=\frac{x^k}{\prod_{i=0}^k(1-([r]_p+m[i]_q)x)}, \qquad k \geq 0.
\end{equation}

We denote the special case of $W_{p,q}(n,k)$ when $r=0$ and $m=p=1$ by $S_q(n,k)$.  The $S_q(n,k)$ sequence is a polynomial generalization of the Stirling numbers which was introduced by Carlitz \cite{Car} and has since been studied (see, e.g., \cite{Wag}).  In what follows, we will make use of the well-known generating function formulas
\begin{equation}\label{s2e2}
\sum_{n\geq k}S_q(n,k)x^n=\frac{x^k}{\prod_{i=1}^k(1-[i]_qx)}, \qquad k \geq 0,
\end{equation}
and
\begin{equation}\label{s2e3}
\sum_{n\geq k}\binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}, \qquad k \geq 0.
\end{equation}
Before proving our main result, we will need a couple of lemmas.

\begin{lemma}\label{s2l1}
If $n>k \geq 0$, then
\begin{equation}\label{s2l1e1}
W_{p,q}(n,k+1)-[r]_pW_{p,q}(n-1,k+1)=\sum_{j=k}^{n-1}\binom{n-1}{j}(mq)^{j-k}(m+[r]_p)^{n-j-1}S_q(j,k).
\end{equation}
\end{lemma}
\begin{proof}
Computing the generating function for the right-hand side of \eqref{s2l1e1}, we have
\begin{align*}
\sum_{n\geq k+1}x^n\sum_{j=k}^{n-1}&\binom{n-1}{j}(mq)^{j-k}(m+[r]_p)^{n-j-1}S_q(j,k)\\
&=\sum_{j \geq k}S_q(j,k)(mq)^{j-k}(m+[r]_p)^{-j}x\sum_{n \geq j+1} \binom{n-1}{j}(m+[r]_p)^{n-1}x^{n-1}\\
&=\sum_{j \geq k}S_q(j,k)(mq)^{j-k}(m+[r]_p)^{-j}x\cdot \frac{(m+[r]_p)^jx^j}{(1-(m+[r]_p)x)^{j+1}}\\
&=\frac{(mq)^{-k}x}{1-(m+[r]_p)x}\sum_{j\geq k}S_q(j,k)\left(\frac{mqx}{1-(m+[r]_p)x}\right)^j\\
&=\frac{(mq)^{-k}x}{1-(m+[r]_p)x}\cdot\frac{(mqx)^k}{(1-(m+[r]_p)x)^k\prod_{i=1}^k\left(1-\frac{mq[i]_qx}{1-(m+[r]_p)x}\right)}\\
&=\frac{x^{k+1}}{\prod_{i=1}^{k+1}(1-([r]_p+m[i]_q)x)},
\end{align*}
by formulas \eqref{s2e3} and \eqref{s2e2} and since $m+mq[i]_q=m[i+1]_q$ for $i \geq0$.  By \eqref{s2e1}, the left-hand side of \eqref{s2l1e1} is seen to have this same generating function, which completes the proof.
\end{proof}

\begin{lemma}\label{s2l2}
If $d>k+1$, then
\begin{align}
&\sum_{n=k+1}^{d-1}(W_{p,q}(n,k+1)-[r]_pW_{p,q}(n-1,k+1))x^n\notag\\
&\qquad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell-1}\sum_{i=j}^{\ell-1}\binom{d-1}{\ell}\binom{i}{j}m^{j-\ell}q^j[r]_p^{i-j}S_q(j,k)x^{i+d-\ell}(1-mx)^{\ell-i-1}.\label{s2l2e2}
\end{align}
\end{lemma}
\begin{proof}
The right-hand side of \eqref{s2l2e2} is seen to be a polynomial in $x$ whose powers lie in the set $\{k+1,k+2,\ldots,d-1\}$.  If $k+1 \leq n \leq d-1$, then the coefficient of $x^n$ on the right side of \eqref{s2l2e2} is given by
\begin{align*}
&\frac{(-1)^{d-n}m^{n-k-1}}{q^k}\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell-1}\sum_{i=j}^{\ell-1}(-1)^{\ell-i}\binom{d-1}{\ell}\binom{i}{j}\binom{\ell-i-1}{d-n-1}m^{j-i}q^j[r]_p^{i-j}S_q(j,k)\\
&\quad=\frac{(-1)^{d-n}m^{n-k-1}}{q^k}\sum_{j=k}^{d-2}\sum_{i=j}^{d-2}(-1)^i\binom{i}{j}m^{j-i}q^j[r]_p^{i-j}S_q(j,k)\sum_{\ell=i+1}^{d-1}(-1)^\ell\binom{d-1}{\ell}\binom{\ell-i-1}{d-n-1}.
\end{align*}
Note that the innermost sum in the last expression is the coefficient of $x^{d-i-2}$ in the convolution product
$$(-1)^{d-1}(1-x)^{d-1}\cdot \frac{x^{d-n-1}}{(1-x)^{d-n}},$$
and is thus given by $$(-1)^{d-1}[x^{n-i-1}](1-x)^{n-1}=(-1)^{d-1}\binom{n-1}{n-1-i}(-1)^{n-i-1}=(-1)^{d+n-i}\binom{n-1}{i}.$$
Plugging this into the last expression implies that the aforementioned coefficient of $x^n$ is given by
\begin{align*}
&\sum_{j=k}^{d-2}(mq)^{j-k}S_q(j,k)\sum_{i=j}^{d-2}\binom{i}{j}\binom{n-1}{i}m^{n-i-1}[r]_p^{i-j}\\
&\qquad\qquad=\sum_{j=k}^{d-2}\binom{n-1}{j}(mq)^{j-k}S_q(j,k)\sum_{i=j}^{d-2}\binom{n-j-1}{i-j}m^{n-i-1}[r]_p^{i-j}\\
&\qquad\qquad=\sum_{j=k}^{n-1}\binom{n-1}{j}(mq)^{j-k}S_q(j,k)\sum_{i=0}^{n-j-1}\binom{n-j-1}{i}m^{n-j-1-i}[r]_p^i\\
&\qquad\qquad=\sum_{j=k}^{n-1}\binom{n-1}{j}(mq)^{j-k}(m+[r]_p)^{n-j-1}S_q(j,k)\\
&\qquad\qquad=W_{p,q}(n,k+1)-[r]_pW_{p,q}(n-1,k+1),
\end{align*}
by the binomial theorem and Lemma \ref{s2l1}, which completes the proof.
\end{proof}

\begin{theorem}\label{s2t1}
If $n,k \geq 0$ and $d \geq 1$, then
\begin{align}
&W_{p,q}(n+d,k+1)-[r]_pW(n+d-1,k+1)\notag\\
&\qquad=\frac{m^{n+d-k-1}}{q^k}\sum_{\ell=0}^{d-1}\sum_{i=0}^n\sum_{j=0}^{i+\ell}\binom{d-1}{\ell}\binom{n}{i}\binom{i+\ell}{j}m^{-j}q^{i+\ell-j}[r]_p^jS_q(i+\ell-j,k).\label{s2t1e1}
\end{align}
\end{theorem}
\begin{proof}
We first assume $d>k+1$.  Then by \eqref{s2e1}, we have
\begin{align}
&\sum_{n\geq0}(W_{p,q}(n+d,k+1)-[r]_pW_{p,q}(n+d-1,k+1))x^{n+d}\notag\\
&\qquad=\frac{x^{k+1}}{\prod_{i=1}^{k+1}(1-([r]_p+m[i]_q)x)}-\sum_{n=k+1}^{d-1}(W_{p,q}(n,k+1)-[r]_pW_{p,q}(n-1,k+1))x^n.\label{s2t1e2}
\end{align}
We now compute the generating function of the quantity on the right-hand side of \eqref{s2t1e1}.  Consider replacing $j$ by $i+\ell-j$ in the innermost sum.  Furthermore, note that if $\ell<k$, then the innermost sum is empty unless $i \geq k-\ell$ (since $j \geq k$ is required), whereas if $\ell \geq k$, then this sum is non-empty for all $i \geq 0$.  We rearrange the terms in the sum as follows:
\begin{align*}
&\sum_{\ell=0}^{d-1}\sum_{i=0}^n\sum_{j=k}^{i+\ell}=\sum_{\ell=0}^{k-1}\sum_{i=0}^n\sum_{j=k}^{i+\ell}+\sum_{\ell=k}^{d-1}\sum_{i=0}^n\sum_{j=k}^{i+\ell}=\sum_{\ell=0}^{k-1}\sum_{j=k}^{\ell+n}\sum_{i=j-\ell}^{n}+\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell+n}\sum_{i=j-\ell}^{n}-\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell-1}\sum_{i=j-\ell}^{-1}\\
&\qquad =\sum_{\ell=0}^{d-1}\sum_{j=k}^{\ell+n}\sum_{i=j-\ell}^{n}-\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell-1}\sum_{i=j-\ell}^{-1}:=S_1-S_2.
\end{align*}

If $i<0$, then let $\binom{n}{i}=(-1)^{n-i}\binom{-i-1}{-n-1}$ if $i \leq n <0$, with $\binom{n}{i}=0$ otherwise.  Note that with this definition that \eqref{s2e3} continues to hold for $k<0$.  While $S_1$ contains terms where $i<0$ in the $\binom{n}{i}$ factor, the sum sought contains no such terms of this form; hence, these terms are subtracted in $S_2$.  We compute 
the generating function for $S_1$ and $S_2$ separately, first considering $S_1$:
\begin{align*}
&\frac{1}{m^{k+1}q^k}\sum_{n \geq -d}(mx)^{n+d}\sum_{\ell=0}^{d-1}\sum_{j=k}^{\ell+n}\sum_{i=j-\ell}^{n}\binom{d-1}{\ell}\binom{n}{i}\binom{i+\ell}{j}m^{j-i-\ell}q^{j}[r]_p^{i+\ell-j}S_q(j,k)\\
&\quad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=0}^{d-1}\sum_{j \geq k}\sum_{i \geq j-\ell}\binom{d-1}{\ell}\binom{i+\ell}{j}m^{j-i-\ell}q^{j}[r]_p^{i+\ell-j}S_q(j,k) \frac{m^ix^{i+d}}{(1-mx)^{i+1}}\\
&\quad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=0}^{d-1}\sum_{j \geq k}\binom{d-1}{\ell}m^{j-\ell}q^j[r]_p^{\ell-j}S_q(j,k)\sum_{i \geq j-\ell}\binom{i+\ell}{j}\frac{[r]_p^ix^{i+d}}{(1-mx)^{i+1}}\\
\end{align*}
\begin{align*}
&\quad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=0}^{d-1}\sum_{j \geq k}\binom{d-1}{\ell}m^{j-\ell}q^j[r]_p^{\ell-j}S_q(j,k)x^{d-\ell}\left(\frac{[r]_p}{1-mx}\right)^{-\ell}\frac{([r]_px)^j}{(1-(m+[r]_p)x)^{j+1}}\\
&\quad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=0}^{d-1}\binom{d-1}{\ell}x^{d-\ell}\left(\frac{1-mx}{m}\right)^\ell \sum_{j\geq k}S_q(j,k)\frac{(mqx)^j}{(1-(m+[r]_p)x)^{j+1}}\\
&\quad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=0}^{d-1}\binom{d-1}{\ell}x^{d-\ell}\left(\frac{1-mx}{m}\right)^\ell\frac{(mqx)^k}{(1-(m+[r]_p)x)^{k+1}\prod_{i=1}^k \left(1-\frac{mq[i]_qx}{1-(m+[r]_p)x}\right)}\\
&\quad=\frac{m^{d-1}x^k}{\prod_{i=1}^{k+1}(1-([r]_p+m[i]_q)x)}\sum_{\ell=0}^{d-1}\binom{d-1}{\ell}x^{d-\ell}\left(\frac{1-mx}{m}\right)^\ell\\
&\quad=\frac{x^{k+1}}{\prod_{i=1}^{k+1}(1-([r]_p+m[i]_q)x)},
\end{align*}
which is the first term on the right-hand side of \eqref{s2t1e2}.

The generating function for $S_2$ is given by
\begin{align*}
&\frac{1}{m^{k+1}q^k}\sum_{n \geq -d}(mx)^{n+d}\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell-1}\sum_{i=j-\ell}^{-1}\binom{d-1}{\ell}\binom{n}{i}\binom{i+\ell}{j}m^{j-i-\ell}q^{j}[r]_p^{i+\ell-j}S_q(j,k)\\
&\qquad=\frac{m^{d-k-1}}{q^k}\sum_{\ell=k}^{d-1}\sum_{j=k}^{\ell-1}\sum_{i=j}^{\ell-1}\binom{d-1}{\ell}\binom{i}{j}m^{j-\ell}q^j[r]_p^{i-j}S_q(j,k)x^{i+d-\ell}(1-mx)^{\ell-i-1},
\end{align*}
upon replacing $i$ by $i-\ell$ in the innermost sum.  By Lemma \ref{s2l2}, this last expression equals
$$\sum_{n=k+1}^{d-1}(W_{p,q}(n,k+1)-[r]_pW_{p,q}(n-1,k+1))x^n,$$
which by \eqref{s2t1e2} shows that the right side of \eqref{s2t1e1} has the same generating function as the left.  This implies \eqref{s2t1e1} in the case when $d>k+1$. If $d\leq k+1$, then a similar argument may be given where both $S_2$ and the sum on the right side of \eqref{s2t1e2} are empty, which completes the proof.
\end{proof}

We note some special cases of the prior result.

\begin{corollary}\label{s2c1}
If $n,k \geq 0$ and $d\geq 1$, then
\begin{equation}\label{s2c1e1}
W(n+d,k+1)-rW(n+d-1,k+1)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n \binom{d-1}{\ell}\binom{n}{i}m^{n+d-i-\ell-1}W(i+\ell,k)
\end{equation}
and
\begin{equation}\label{s2c1e2}
D(n+d)-rD(n+d-1)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n \binom{d-1}{\ell}\binom{n}{i}m^{n+d-i-\ell-1}D(i+\ell).
\end{equation}
\end{corollary}
\begin{proof}
Formula \eqref{s2c1e1} follows from substituting $p=q=1$ in \eqref{s2t1e1} and using the fact $$W(i+\ell,k)=\sum_{j=0}^{i+\ell}\binom{i+\ell}{j}m^{i+\ell-j-k}r^jS(i+\ell-j,k),$$
see \cite[Section 3]{Ch}.  Summing \eqref{s2c1e1} over $k \geq 0$, and noting that $W(n+d,0)=rW(n+d-1,0)$, gives formula \eqref{s2c1e2}.
\end{proof}

Taking $r=0$ and $m=1$ in \eqref{s2t1e1} gives the following recurrence for $S_q(n,k)$.

\begin{corollary}\label{s2c2}
If $n,k \geq 0$ and $d\geq 1$, then
\begin{equation}\label{s2c2e1}
S_q(n+d,k+1)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n\binom{d-1}{\ell}\binom{n}{i}q^{i+\ell-k}S_q(i+\ell,k).
\end{equation}
\end{corollary}

Taking $q=1$ in \eqref{s2c2e1} gives the following formula for $S(n,k)$:
\begin{equation}\label{s2c2e2}
S(n+d,k+1)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n\binom{d-1}{\ell}\binom{n}{i}S(i+\ell,k), \qquad d \geq 1.
\end{equation}
Summing \eqref{s2c2e2} over $k \geq 0$ yields the following Bell number formula:
\begin{equation}\label{s2c2e3}
B(n+d)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n\binom{d-1}{\ell}\binom{n}{i}B(i+\ell), \qquad d \geq 1.
\end{equation}

\begin{remark} The $d=1$ cases of \eqref{s2c2e2} and \eqref{s2c2e3} correspond to the well-known recurrences for the Stirling and Bell numbers, respectively.  The $d=2$ cases of \eqref{s2c2e2} and \eqref{s2c2e3} may be written as
\begin{equation}\label{s2c2e4}
S(n+2,k+1)=S(n+1,k+1)+S(n+1,k)+\sum_{i=1}^n \binom{n}{i-1}S(i,k), \qquad n,k \geq 0,
\end{equation}
and
\begin{equation}\label{s2c2e5}
B(n+2)=2B(n+1)+\sum_{i=1}^n \binom{n}{i-1}B(i), \qquad n \geq 0,
\end{equation}
the latter of which is previously known \cite{SS}.
\end{remark}

We conclude this section by giving bijective proofs of the last four identities.
\bigskip

\noindent \textbf{Combinatorial proof of formulas \eqref{s2c2e2}--\eqref{s2c2e5}.}
\bigskip

Let $\mathcal{P}_{n,k}$ denote the set of all partitions of $[n]=\{1,2,\ldots,n\}$ containing exactly $k$ blocks and let $\mathcal{P}_n=\cup_{k=0}^n\mathcal{P}_{n,k}$.  To show \eqref{s2c2e2}, suppose that the number of elements of $[2,d]=\{2,3,\ldots,d\}$ lying in the block containing $1$ of $\pi \in \mathcal{P}_{n+d,k+1}$ is $d-\ell-1$, while the number of elements of $[d+1,d+n]$ lying in this block is $n-i$, where $0 \leq \ell \leq d-1$ and $0 \leq i \leq n$.  Then there are $\binom{d-1}{d-1-\ell}\binom{n}{n-i}$ choices regarding the block of $\pi$ containing $1$, with the remaining $i+\ell$ elements of $[n+d]$ to be partitioned in any one of $S(i+\ell,k)$ ways.  Summing over all possible $i$ and $\ell$ gives \eqref{s2c2e2}.  A similar proof applies to \eqref{s2c2e3}, upon allowing partitions to contain any number of blocks.

To show \eqref{s2c2e4}, first note that there are $S(n+1,k+1)$ members of $\mathcal{P}_{n+2,k+1}$ in which the elements $1$ and $2$ belong to the same block and $S(n+1,k)$ members in which $1$ belongs to its own block.  Next observe that there are $\binom{n}{n-i+1}S(i,k)=\binom{n}{i-1}S(i,k)$ members of $\mathcal{P}_{n+2,k+1}$ for $1 \leq i \leq n$ in which there are exactly $n-i+1$ elements of $[3,n+2]$ belonging to the block containing $1$, with $1$ and $2$ belonging to different blocks (note that the remaining $n-(n-i+1)=i-1$ elements of $[3,n+2]$, together with $2$, would constitute a partition having $k$ blocks).  Summing over $i$ yields all members of $\mathcal{P}_{n+2,k+1}$ in which $1$ and $2$ belong to different blocks, with $1$ not forming its own block.  Combining this with the previous cases gives \eqref{s2c2e4}.  Similar reasoning applies to \eqref{s2c2e5}.  Note that there are $2B(n+1)$ members of $\mathcal{P}_{n+2}$ in which $1$ either belongs to its own block or to the same block as $2$ and that there are $\binom{n}{n-i+1}B(i)$ members of $\mathcal{P}_{n+2}$ for $1 \leq i \leq n$ in which $1$ and $2$ belong to different blocks with the cardinality of the block containing $1$ equal $n-i+2$.  \hfill \qed


\section{A further formula for $r$-Whitney numbers}

In this section, we prove a further identity satisfied by the $r$-Whitney numbers of the second kind.

\begin{theorem}\label{s3t1}
If $n \geq 1$ and $k \geq 2$, then
\begin{equation}\label{s3t1e1}
W(n+1,k)-rW(n,k)=\sum_{j=0}^{n-1}\left(\binom{n}{j}+\frac{r}{m}-1\right)m^{n-j}W(j,k-1)+\sum_{j=1}^n\binom{n}{j}m^{n-j}W(j-1,k-2)
\end{equation}
and
\begin{equation}\label{s3t1e2}
D(n+1)-rD(n)=m^n+\sum_{j=0}^{n-1}\left(\binom{n}{j}+\frac{r}{m}-1\right)m^{n-j}D(j)+\sum_{j=1}^n\binom{n}{j}m^{n-j}D(j-1).
\end{equation}
\end{theorem}
\begin{proof}
By \eqref{s2e1} when $p=q=1$, we have
$$\sum_{n\geq 1}(W(n+1,k)-rW(n,k))x^n=\frac{x^{k-1}}{\prod_{i=1}^k(1-(r+mi)x)}.$$
Computing the generating function of the right-hand side of \eqref{s3t1e1} gives
\begin{align*}
&\sum_{n\geq1}x^n\sum_{j=0}^{n-1}\left(\binom{n}{j}+\frac{r}{m}-1\right)m^{n-j}W(j,k-1)+\sum_{n\geq1}x^n\sum_{j=1}^n\binom{n}{j}m^{n-j}W(j-1,k-2)\\
&\qquad\quad\quad=\sum_{j\geq0}W(j,k-1)m^{-j}\sum_{n\geq j+1}\left(\binom{n}{j}+\frac{r}{m}-1\right)(mx)^n\\
&\qquad\quad\quad\quad+\sum_{j\geq 1}W(j-1,k-2)m^{-j}\sum_{n\geq j}\binom{n}{j}(mx)^n\\
&\qquad\quad\quad=\sum_{j\geq0}W(j,k-1)m^{-j}\left(\frac{(mx)^j}{(1-mx)^{j+1}}-(mx)^j+\frac{\left(\frac{r}{m}-1\right)(mx)^{j+1}}{1-mx}\right)\\
&\qquad\quad\quad\quad+\sum_{j\geq1}W(j-1,k-2)m^{-j}\frac{(mx)^j}{(1-mx)^{j+1}}\\
&\quad=\sum_{j\geq0}W(j,k-1)\frac{x^j}{(1-mx)^{j+1}}-\frac{1-rx}{1-mx}\sum_{j\geq0}W(j,k-1)x^j\\
&\quad\quad+\sum_{j\geq1}W(j-1,k-2)\frac{x^j}{(1-mx)^{j+1}}\\
&\quad=\frac{x^{k-1}}{(1-mx)^k\prod_{i=0}^{k-1}\left(1-\frac{(r+mi)x}{1-mx}\right)}-\frac{x^{k-1}(1-rx)}{(1-mx)\prod_{i=0}^{k-1}(1-(r+mi)x)}\\
&\quad\quad+\frac{x^{k-1}}{(1-mx)^k\prod_{i=0}^{k-2}\left(1-\frac{(r+mi)x}{1-mx}\right)}\\
&\quad=\frac{x^{k-1}(1-mx)-x^{k-1}(1-(r+mk)x)+x^{k-1}(1-(r+mk)x)}{(1-mx)\prod_{i=1}^k(1-(r+mi)x)}\\
&\quad=\frac{x^{k-1}}{\prod_{i=1}^k(1-(r+mi)x)},
\end{align*}
as before, which implies \eqref{s3t1e1}.

Summing both sides of \eqref{s3t1e1} over $k \geq 2$, and noting $W(n+1,0)=rW(n,0)$, implies
\begin{align*}
D(n+1)-rD(n)&=W(n+1,1)-rW(n,1)+\sum_{j=0}^{n-1}\left(\binom{n}{j}+\frac{r}{m}-1\right)m^{n-j}D(j)\\
&\quad+\sum_{j=1}^n\binom{n}{j}m^{n-j}D(j-1)-\sum_{j=0}^{n-1}\left(\binom{n}{j}+\frac{r}{m}-1\right)m^{n-j}W(j,0).
\end{align*}
From this, we see that identity \eqref{s3t1e2} holds if and only if
$$W(n+1,1)-rW(n,1)=m^n+\sum_{j=0}^{n-1}\left(\binom{n}{j}+\frac{r}{m}-1\right)m^{n-j}r^j.$$
This last equality follows from the fact that $W(n+1,1)-rW(n,1)=(m+r)^n$ (which can be obtained by taking $p=q=1$ and $k=0$ in \eqref{s2l1e1}).  This gives \eqref{s3t1e2} and completes the proof.
\end{proof}

We have as special cases of the prior result the following recurrence formulas for the Stirling and Bell numbers which we did not find in the literature.

\begin{corollary}\label{s3c1}
If $n \geq 1$ and $k \geq 2$, then
\begin{equation}\label{s3c1e1}
S(n+1,k)=\sum_{j=1}^n\left(\binom{n}{j}-1\right)S(j,k-1)+\sum_{j=1}^n \binom{n}{j}S(j-1,k-2)
\end{equation}
and
\begin{equation}\label{s3c1e2}
B(n+1)=1+\sum_{j=1}^{n}\left(\binom{n+1}{j}-1\right)B(j-1).
\end{equation}
\end{corollary}
\begin{proof}
Taking $m=1$ and $r=0$ in \eqref{s3t1e1} gives \eqref{s3c1e1}.  Taking $m=1$ and $r=0$ in \eqref{s3t1e2} implies
\begin{align*}
B(n+1)-1&=\sum_{j=0}^{n-1}\left(\binom{n}{j}-1\right)B(j)+\sum_{j=0}^{n-1}\binom{n}{j+1}B(j)\\
&=\sum_{j=0}^n\left(\binom{n}{j}+\binom{n}{j+1}-1\right)B(j)=\sum_{j=0}^n\left(\binom{n+1}{j+1}-1\right)B(j)\\
&=\sum_{j=1}^n\left(\binom{n+1}{j}-1\right)B(j-1),
\end{align*}
which gives \eqref{s3c1e2}.
\end{proof}

Using \eqref{s2e2} and \eqref{s2e3}, it is possible to obtain a $q$-generalization of formula \eqref{s3c1e1}.

\begin{theorem}\label{s3t2}
If $n \geq 1$ and $k \geq 2$, then
\begin{align}
S_q(n+1,k)&=\sum_{j=1}^n\left(\binom{n}{j}-1\right)q^{j-k+1}S_q(j,k-1)\notag\\
&\quad+\sum_{j=1}^n\sum_{i=1}^{n-j+1}\binom{n-i}{j-1}q^{n+j-i-2k+3}S_q(j-1,k-2).\label{s3t2e1}
\end{align}
\end{theorem}

One can also give a combinatorial proof of formulas \eqref{s3c1e1} and \eqref{s3c1e2}.
\bigskip

\noindent\textbf{Combinatorial proof of Corollary \ref{s3c1}.}
\bigskip

We first show \eqref{s3c1e1}.  To do so, we count members of $\mathcal{P}_{n+1,k}$ according to the contents of the block $B$ containing the element $1$.  First suppose that it is not the case that $B$ equals $[i]$ for some $i$.  Then $k \geq 2$ implies $|B|=n-j+1$ where $1 \leq j \leq n-1$.  Thus, members of $\mathcal{P}_{n+1,k}$ may be formed in this case by picking some subset $S$ of $[2,n+1]$ of cardinality $n-j$ where $S \not=[2,n-j+1]$, adding the element $1$ to $S$ to obtain $B$, and then partitioning the $j$ members of $[n+1]-B$ into $k-1$ blocks.  Summing over all possible $i$, it follows that there are $\sum_{j=1}^{n-1}\left(\binom{n}{n-j}-1\right)S(j,k-1)$ members of $\mathcal{P}_{n+1,k}$ in which $B$ does not equal $[i]$ for any $i$.

On the other hand, members of $\mathcal{P}_{n+1,k}$ in which $B=[i]$ for some $i$ where $i \geq 1$ may be formed as follows.  First select a subset $T$ of $[n+1]$ of size $n-j+1$ that contains the element $1$, where $1 \leq j \leq n$.  Note that there are $\binom{n}{j}$ choices for $T$ and that $j \geq 1$ implies $T$ is a proper subset of $[n+1]$.  Let $\ell$ denote the smallest element of $[n+1]-T$.  Form a member of $\mathcal{P}_{n+1,k}$ by letting $[\ell-1]$ be one block and $\{\ell\}\cup(T\cap[\ell+1,n+1])$ be another, with the members of $[n+1]-(T\cup\{\ell\})$ arranged according to a partition containing $k-2$ blocks (of which there are $S(j-1,k-2)$ possibilities).  Considering all possible $j$, it follows that there are $\sum_{j=1}^n\binom{n}{j}S(j-1,k-2)$ members of $\mathcal{P}_{n+1,k}$ in which $B=[i]$ for some $i$.  Combining this case with the prior one gives \eqref{s3c1e1}.

Reasoning as in the previous two paragraphs, one may define a one-to-one correspondence between the members of $\mathcal{P}_{n+1}$ containing at least two blocks and the set of all ordered pairs $(S,P)$, where $S$ is a subset of $[n+1]$ of cardinality $n-j+1$ for some $1 \leq j \leq n$ with $S \not=[2,n-j+2]$ and $P$ is a member of $\mathcal{P}_{j-1}$.  Considering the cardinality of the set of all such ordered pairs implies \eqref{s3c1e2}.  \hfill \qed


\section{Related results}

We can give analogues of some of the prior results involving related sequences.  Given $0 \leq k \leq n$, let $c(n,k)$ denote the (signless) Stirling number of the first kind and $L(n,k)$ be the (signless) Lah number; see, e.g., sequences \seqnum{A008275} and \seqnum{A008297} in OEIS \cite{Slo}.  Recall that $c(n,k)$ counts the number of permutations of $[n]$ containing $k$ cycles and that $L(n,k)$ counts partitions of $[n]$ into $k$ blocks in which the elements within each block are ordered (see, e.g., \cite{LMSh}).  Extending the combinatorial arguments presented above for identity \eqref{s2c2e2} above to allow for ordering within blocks yields the following result.

\begin{theorem}\label{s4t1}
If $n,k \geq 0$ and $d \geq 1$, then
\begin{equation}\label{s4t1e1}
c(n+d,k+1)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n\binom{d-1}{\ell}\binom{n}{i}(n+d-i-\ell-1)!c(i+\ell,k)
\end{equation}
and
\begin{equation}\label{s4t1e2}
L(n+d,k+1)=\sum_{\ell=0}^{d-1}\sum_{i=0}^n\binom{d-1}{\ell}\binom{n}{i}(n+d-i-\ell)!L(i+\ell,k).
\end{equation}
\end{theorem}

\begin{remark} Summing \eqref{s4t1e1} and \eqref{s4t1e2} over $k$ gives comparable formulas involving the $n!$ and $L(n)$ sequences, respectively, where $L(n)=\sum_{k=0}^nL(n,k)$ (see \seqnum{A000262} in \cite{Slo}).\end{remark}

We also have the following analogues of identity \eqref{s3c1e1}.

\begin{theorem}\label{s4t2}
If $n \geq 1$ and $k \geq 2$, then
\begin{equation}\label{s4t2e1}
c(n+1,k)=\sum_{j=1}^n\left(\binom{n}{j}-1\right)(n-j)!c(j,k-1)+\sum_{j=1}^n\sum_{i=0}^{n-j}\binom{n-i-1}{j-1}i!(n-i-j)!c(j-1,k-2)
\end{equation}
and
\begin{equation}\label{s4t2e2}
L(n+1,k)=\sum_{j=1}^n\left(\binom{n}{j}-1\right)(n-j+1)!L(j,k-1)+\sum_{j=0}^{n-1}\sum_{i=1}^{n-j}\binom{n-i}{j}i!(n-i-j+1)!L(j,k-2).
\end{equation}
\end{theorem}
\begin{proof}
We show only \eqref{s4t2e1}, as a similar proof will apply to \eqref{s4t2e2}.  We proceed as in the combinatorial proof of formula \eqref{s3c1e1} above.  Let $\mathcal{S}_{n+1,k}$ be the set of permutations of $[n+1]$ containing $k$ cycles and let $B$ denote the cycle containing $1$ within a member of $\mathcal{S}_{n+1,k}$.  Then the first term on the right-hand side of \eqref{s4t2e1} is seen to count all members of $\mathcal{S}_{n+1,k}$ in which $B$ does not comprise the elements of $[i]$ for any $i$ and has cardinality $n-j+1$ for some $1 \leq j \leq n$.  Note that the $(n-j)!$ factor accounts for the ordering of the elements within $B$.

Now consider members of $\mathcal{S}_{n+1,k}$ such that $B$ comprises the elements of $[i+1]$ for some $0 \leq i \leq n-1$.  Suppose further that the cycle containing the element $i+2$ has cardinality $n-i-j+1$ where $1 \leq j \leq n-i$.  Then there are $\binom{n-i-1}{n-i-j}=\binom{n-i-1}{j-1}$ choices for the elements of this cycle and $i!(n-i-j)!$ ways in which to order the elements of the first two cycles.  The remaining $n+1-(i+1)-(n-i-j+1)=j-1$ elements of $[n+1]$ are then arranged within cycles in $c(j-1,k-2)$ ways.  Summing over all possible $i$ and $j$ gives the second term on the right side of \eqref{s4t2e1} and completes the proof.
\end{proof}

Summing \eqref{s4t2e1} and \eqref{s4t2e2} over $k \geq 2$ yields analogues of identity \eqref{s3t1e2} involving $n!$ and $L(n)$.  These formulas may also be given a combinatorial proof by extending the argument above for \eqref{s3c1e2}.


\begin{thebibliography}{99}

\bibitem{Be1}
M. Benoumhani, On Whitney numbers of Dowling lattices, \emph{Discrete Math.} {\bf 159} (1996), 13--33.

\bibitem{Be2}
M. Benoumhani, On some numbers related to Whitney numbers of Dowling lattices, \emph{Adv. in Appl. Math.} {\bf 19} (1997), 106--116.

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

\bibitem{Car}
L. Carlitz, $q$-Bernoulli numbers and polynomials, \emph{Duke Math. J.} {\bf 15} (1948), 987--1000.

\bibitem{Ch}
G.-S. Cheon and J.-H. Jung, $r$-Whitney numbers of Dowling lattices, \emph{Discrete Math.} {\bf 312} (2012), 2337--2348.

\bibitem{LMSh}
J. Lindsay, T. Mansour, and M. Shattuck, A new combinatorial interpretation of a $q$-analogue of the Lah numbers, \emph{J. Comb.} {\bf2} (2010), 245--264.

\bibitem{MK}
M. M. Mangontarum and J. Katriel, On $q$-boson operators and
$q$-analogues of the $r$-Whitney and $r$-Dowling numbers, \emph{J.
Integer Sequences} {\bf 18} (2015), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Mangontarum/mango2.html}{Article 15.9.8}.

\bibitem{MRS}
T. Mansour, J. L. Ram\'{\i}rez, and M. Shattuck, A generalization of the $r$-Whitney numbers of the second kind, \emph{J. Comb.} {\bf 8} (2017), 29--55.

\bibitem{MSc}
T. Mansour and M. Schork, \emph{Commutation Relations, Normal Ordering, and Stirling Numbers}, Chapman \& Hall/CRC, 2015.

\bibitem{Me}
I. Mez\H{o}, The $r$-Bell numbers, \emph{J. Integer Sequences}
\textbf{14} (2011), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL14/Mezo/mezo9.html}{Article 11.1.1}.

\bibitem{MeR}
I. Mez\H{o} and J. L. Ram\'{\i}rez, Some identities of the $r$-Whitney numbers, \emph{Aequationes Math.} \textbf{90} (2016), 393--406.

\bibitem{Ra} M. Rahmani, Some results on Whitney numbers of Dowling
lattices, \emph{Arab J. Math. Sci.} {\bf20} (2014), 11--27.

\bibitem{SS} P. K. Saikia and D. Subedi, Bell numbers, determinants and
series, \emph{Proc. Indian Acad. Sci. (Math. Sci.)} {\bf123} (2013),
151--166.

\bibitem{Slo} N. J. A. Sloane, \emph{The On-Line Encyclopedia of
Integer Sequences}, \url{http://oeis.org}.

\bibitem{St}
R. P. Stanley, \emph{Enumerative Combinatorics}, Vol.~I, Cambridge University Press, 1997.

\bibitem{Wag}
C. G. Wagner, Generalized Stirling and Lah numbers, \emph{Discrete Math.} {\bf 160} (1996), 199--218.


\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent {\it Keywords}:  $r$-Whitney number, Stirling number, $q$-analogue, combinatorial identity.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 18 2017;
revised version received  September 27 2017.
Published in {\it Journal of Integer Sequences}, October 29 2017.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                



.
