\documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{latexsym} %%\usepackage{amsmath} \usepackage{amssymb} \def\s{\atopwithdelims[]} \newcommand{\binom}[2]{{{#1} \choose {#2}}} \newcommand{\ignore}[1]{} \newcommand{\qed}{\hfill$\square$\\} \newtheorem{Theo}{Theorem} \newtheorem{Lem}{Lemma} \newtheorem{Def}{Definition} \newtheorem{Ident}{Identity} \begin{document} \begin{center} {\bf A COMBINATORIAL APPROACH TO HYPERHARMONIC NUMBERS} \vskip 20pt {\bf Arthur T. Benjamin }\\ {\smallit Department of Mathematics, Harvey Mudd College, Claremont, CA, USA}\\ {\tt benjamin@math.hmc.edu}\\ \vskip 10pt {\bf David Gaebler }\\ {\smallit Department of Mathematics, Harvey Mudd College, Claremont, CA, USA}\\ {\tt dgaebler@hmc.edu}\\ \vskip 10pt {\bf Robert Gaebler }\\ {\smallit Department of Mathematics, Harvey Mudd College, Claremont, CA, USA}\\ {\tt rgaebler@hmc.edu}\\ \end{center} \vskip 20pt \centerline{\smallit Received: 3/26/03, Accepted: 10/21/03, Published: 10/23/03} \vskip 20pt \centerline{\bf Abstract} \noindent Hyperharmonic numbers arise by taking repeated partial sums of harmonic numbers. These numbers can be expressed in terms of $r$-Stirling numbers, leading to combinatorial interpretations of many interesting identities. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 3 (2003), \#A15\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 20pt \section*{\normalsize 1. Introduction} The harmonic numbers, defined by $H_n = \sum_{k=1}^{n}\frac{1}{k}$ arise frequently in the solution to combinatorial problems and in the analysis of algorithms. It is well known \cite{GKP} that \begin{equation} H_n = \frac{{n+1 \s 2}}{n!} \label{stir} \end{equation} where ${n \s k}$ denotes the (unsigned) Stirling number of the first kind, counting the permutations of $n$ elements that are the product of $k$ disjoint cycles. This allows harmonic number identities to be viewed combinatorially, as in \cite{Preston}. The quantity $H_n$ can be generalized many ways (see, for instance, \cite{Santmyer}). The generalization we pursue, called {\em hyperharmonic numbers} by Conway and Guy \cite{bookonumbers}, are obtained by taking repeated partial sums of the Harmonic numbers. Formally, we define $H_n^r$, the hyperharmonic number of order $r$ as follows. \begin{Def} Let $H_n^r = 0$ for $r < 0$ or $n \leq 0$, $H_n^0 = \frac{1}{n}$ for $n \geq 1$, and for $r, n \geq 1$, let \begin{equation} \label{recurdef} H_n^r = \sum_{i = 1}^{n} H_i^{r - 1}. \end{equation} \end{Def} Note that $H_n^1$ is equal to the ordinary harmonic number $H_n$. In \cite{bookonumbers}, Conway and Guy express the hyperharmonic numbers in terms of ordinary harmonic numbers. \begin{equation} \label{conway} H_n^r = \binom{n + r - 1}{r - 1} (H_{n + r - 1} - H_{r - 1}). \end{equation} The presence of the binomial coefficient suggests that a deeper combinatorial relationship exists. As we shall see, the hyperharmonic numbers satisfy several interesting identities like the ones below. \begin{eqnarray} n H_n^r &=& \binom{n + r - 1}{r} + r H_{n - 1}^{r + 1} \label{corolrecur3}\\ \nonumber \\ \binom{m-1}{r-1} H_{n}^{m} &=& \binom{n + m - r}{n} H_{n + m - r}^{r} - \binom{n + m - 1}{n} H_{m - r}^{r} \quad \textrm{for } 1 \leq r \leq m \label{gencon}\\ \nonumber \\ \sum_{t=1}^r H_n^t &=& H_{n+1}^r - \frac{1}{n+1} \label{sumorders}\\ \nonumber \\ H_n^r &=& \sum_{t=1}^n \binom{n+r-m-t-1}{r-m-1} H_t^{m} \qquad \qquad \qquad \ \, \textrm{for } 0 \leq m \leq r-1 \label{uplevel}\\ \nonumber \\ H_n^r &=& \sum_{t=0}^m \binom{m}{t} H_{n+t-m}^{r-t} \qquad \qquad \qquad \qquad \qquad \qquad \ \ \textrm{for } 0 \leq m \leq r \label{diag}\\ \nonumber \\ H_n^r &=& \sum_{s=m}^n \binom{n+r-l-s}{r-l} H_{s}^{l-1} + \sum_{t=l}^r \binom{n+r-m-t}{n-m} H_{m-1}^{t} \label{rowcol}\\ \nonumber \\ &&\textrm{for $1 \leq l \leq r$ and $1 \leq m \leq n$}.\nonumber \end{eqnarray} A generating function for the hyperharmonic numbers is $$\frac{- \ln (1 - x)}{(1 - x)^r} = \sum_{i = 1}^{\infty} H_i^r x^i$$ since $- \ln(1-x) = \sum \frac{x^n}{n}$, and multiplying by $\frac{1}{(1-x)^r}$ has the effect of taking partial sums $r$ times. This generating function is equivalent by (\ref{conway}) to an identity in \cite{Greene}. Although many of the identities in this paper can be proved using algebraic methods, we shall prove all of these by simple combinatorial arguments. \vskip 30pt \section*{\normalsize 2. Basic properties of hyperharmonic numbers} There are two different ways to approach the hyperharmonic numbers combinatorially. One is to investigate the numerator of the unreduced fraction, i.e., $n! H_n^r$. This approach will be followed in the next section. The other is to write $H_n^r$ as the sum of fractions $\frac{1}{t}$, where $t$ ranges from 1 to $n$, and ask how many times each fraction appears in this sum. The answer is given by the following theorem. \begin{Theo} \label{fractioncount} $$H_{n}^r = \sum_{t = 1}^n \binom{n + r - t - 1}{r - 1} \frac{1}{t}. \label{fracs}$$ \end{Theo} \noindent {\it Proof.} Given a particular $t$, where $1\leq t\leq n$, we claim that the fraction $\frac{1}{t}$ is counted exactly $\binom{n+r-t-1}{r-1}$ times. To see this, consider the weighted directed graph with vertex set $V=\{(x,y)| x\geq 1, y\geq 0\}$ and the arcs leaving $(x,y)$ enter vertices $(x',y+1)$, where $x'\geq x$. We give each vertex $(x,y)$ a weight of $H_x^y$. Hence for all $t\geq 1$, $(t,0)$ has weight $\frac{1}{t}$ and for $x,y\geq 1$, $(x,y)$ has weight $\sum_{x'\leq x}H_{x'}^{y-1}$, which is the sum of the weights of the vertices that point to $(x,y)$. Thus the fraction $\frac{1}{t}$ appears in $H_n^r$ for every path from $(t,0)$ to $(n,r)$, i.e., for every sequence $t\leq x_1\leq\cdots\leq x_{r-1}\leq n$. This is the same as the number of size $r-1$ multisubsets of $\{t,\ldots,n\}$, which equals $$\left(\binom{n - t + 1}{r - 1}\right) = \binom{n + r - t - 1}{r - 1}$$ as desired, where $\left(\binom{n}{k}\right) = \binom{n+k-1}{k}$ is the number of size $k$ multisubsets of an $n$-element set.$\hfill \Box$ More generally, for $0\leq m\leq r-1$, by counting all paths from $(t,m)$ to $(n,r)$, we see that for $1\leq t\leq n$, $H_t^m$ is contributed $\left(\binom{n - t + 1}{r - 1 -m}\right) = \binom{n + r - t - m - 1}{r - m - 1}$ times, and Identity (\ref{uplevel}) follows. Similar path counting arguments can also be used to establish equations (\ref{sumorders}), (\ref{diag}) and (\ref{rowcol}), but we shall provide other combinatorial proofs of these in Section 4. We now begin our discussion of the combinatorial nature of the numerator of $H_{n, r}$. We can write $H_n^r$ as a (typically non-reduced) fraction of the form \begin{equation} \label{numer} H_n^r = \frac{a_{n, r}}{n!}. \end{equation} Thus $a_{0,r} = 0$ and for $n \geq 1$, $a_{n, 0} = (n-1)!$ . For $n,r \geq 1$, \begin{eqnarray} \label{recurharm} & &H_n^r = \sum_{i = 1}^{n} H_i^{r - 1} = H_{n-1}^r + H_n^{r - 1} \nonumber\\ &\Longrightarrow& \frac{a_{n, r}}{n!} = \frac{a_{n - 1, r}}{(n - 1)!} + \frac{a_{n, r - 1}}{n!} \nonumber\\ &\Longrightarrow& a_{n, r} = n \, a_{n - 1, r} +a_{n, r-1} \end{eqnarray} We shall use this recurrence and initial condition to prove a generalization of equation (\ref{stir}). \vskip 30pt \section*{\normalsize 3. r-Stirling numbers} The $r$-Stirling numbers, which are similar to the weighted Stirling numbers of Carlitz \cite{Carlitz} and are a special case of the generalized Stirling numbers of Hsu and Shiue \cite{Hsu}, can be defined combinatorially in terms of restricted permutations. Broder \cite{Broder} gives the following combinatorial definition, which we will use throughout this paper: \begin{Def} ${n \s k}_r$ is the number of permutations of the set $\{1, 2, \ldots, n\}$ having $k$ disjoint, non-empty cycles, in which the elements 1 through $r$ are restricted to appear in different cycles. \end{Def} Note that ${n \s k}_0$ and ${n \s k}_1$ are both equal to the ordinary Stirling number ${n \s k}$. For convenience, we let $T_{n, k, r}$ denote the set of permutations of $\{1, 2, \ldots, n\}$ into $k$ cycles, in which the elements 1 through $r$ appear in different cycles. Thus ${n \s k}_r$ is the number of permutations in $T_{n, k, r}$. We can think of ${n \s k}_r$ as counting the number of permutations with $r$ ``restricted'' and $n-r$ ``free'' elements. If a cycle contains a restricted element, we call it a {\it restricted cycle}; otherwise we call it a {\it free cycle.} We shall adopt the standard permutation notation of writing the smallest element in a cycle at the beginning of that cycle, and listing the cycles in ascending order according to their smallest elements. For example, (1 5 3 7)(2)(4 9 8)(6) is in standard permutation notation, while \mbox{(1 5 3 7)(2)(6)(4 9 8)} and \mbox{(1 5 3 7)(2)(9 8 4)(6)} are not. Generating functions for the $r$-Stirling numbers are presented in \cite{Broder}: \begin{eqnarray*} \sum_{k = r}^{n} {n \s k}_r x^k &=& x^r \prod_{i=r}^{n-1} (x+i).\\ \sum_{n=k}^\infty {n+r \s k+r}_r \frac{x^n}{n!} &=& \frac{1}{k!} \left ( \frac{1}{1-x} \right)^r \left[ \ln \left(\frac{1}{1-x} \right) \right]^k.\\ \sum_{0 \leq k \leq n} {n+r \s k+r}_r \frac{x^n}{n!} t^k &=& \left(\frac{1}{1-x} \right)^{r+t}.\\ \end{eqnarray*} By definition, we have ${0\s 0}_r = 1$ and for $n>0$, ${n\s k}_r = 0$ for $kn$. Notice that for $1\leq r\leq n$ \begin{equation} \label{pie} {n \s r}_r = \frac{(n-1)!}{(r-1)!} \end{equation} since we are counting permutations of the form $(1\cdots)(2\cdots)\cdots(r\cdots)$. The elements $r+1$ through $n$ may be entered one at a time. Each element $r+1\leq i\leq n$ can be placed to the right of any of the $i-1$ elements already in place, so there are $r(r+1)\cdots(n-1)=\frac{(n-1)!}{(r-1)!}$ such permutations. Notice that $r$-Stirling numbers also satisfy the traditional Stirling recurrence: for $0 \leq r \leq k \leq n$, \begin{equation} \label{basicrecur} {n+1 \s k}_r = {n \s k-1}_r + n {n \s k}_r \end{equation} which may be proved by conditioning on whether or not element $n+1$ is alone in its cycle. Another useful identity we shall rely on is: \begin{Ident} \label{recur1} For $r \geq 1$, $${n + r \s k}_r = n {n + r - 1 \s k}_r + {n + r - 1 \s k - 1}_{r - 1}.$$ \end{Ident} This may be proved by conditioning on whether there are any free elements in the first cycle. If so, then choose one of the $n$ free elements to appear immediately after $1$; the other elements can be arranged ${n + r - 1 \s k}_r$ ways. Otherwise, element $1$ is alone, and elements $2$ through $n+r$ can be arranged ${n+r-1\s k-1}_{r-1}$ ways. This brings us to the following theorem. \begin{Theo} \label{equ} $$H_n^r = \frac{{n+r\s r+1}_r}{n!}.$$ \end{Theo} \noindent {\it Proof 1.} Let $A_{n, r} = {n+r \s r+1}_r$. Hence $A_{0, r} = {r \s r+1}_{r} = 0 = a_{0, r}$ and for $n\geq 1$, $A_{n, 0} = {n \s 1}_0 = (n-1)! = a_{0,r}$. For $n,r\geq 1$, Identity \ref{recur1} implies $A_{n, r} = n A_{n-1, r} + A_{n, r-1}$ just like in equation (\ref{recurharm}). Since $A_{n,r}$ and $a_{n,r}$ satisfy the same initial conditions and the same recurrence, then by equation (\ref{numer}) we have ${n + r \s r + 1}_r = A_{n, r} = a_{n, r} = n! H_n^r,$ as desired. $\hfill \Box$ It is also possible to combinatorially prove Theorem \ref{equ} without relying on a recurrence. We first prove the following general identity, similar to one proved in \cite{Broder}. \begin{Ident} \label{useful} For $0 \leq m \leq r \leq n$ and $0 \leq l \leq k-r$, $$\binom{k-r}{l} {n+r \s k}_r = \sum_{t=k-r-l}^{n-l} \binom{n}{t} {t+r-m \s k-m-l}_{r-m} {n+m-t \s m+l}_{m}$$ \end{Ident} \noindent {\it Proof.} The left side counts permutations of $T_{n+r,k,r}$ where the first $m$ cycles and $l$ free cycles are colored red, and the other cycles colored green. On the right, we condition on the number $t$ of free elements in green cycles. There are $\binom{n}{t}$ ways to choose the free elements, ${t+r-m \s k-m-l}_{r-m}$ ways to arrange them in $k-(m+l)$ green cycles, then ${n+m-t \s l+m}_m$ ways to arrange the other $(n+r)-(r-m+t)$ elements among the $m+l$ red cycles. $\hfill \Box$ \noindent {\it Proof 2 of Theorem \ref{equ}.} As a special case of Identity \ref{useful} with $l=0$, $m=r$, and $k=r+1$, we have $${n + r \s r + 1}_r = \sum_{t = 1}^{n} \frac{n!}{t!(n-t)!} \cdot (t-1)! \cdot \frac{(n+r-t-1)!}{(r-1)!} = \sum_{t = 1}^{n} \binom{n + r - t - 1}{r - 1} \frac{n!}{t} = n! H_n^r$$ by Theorem \ref{fractioncount}. $\hfill \Box$ \vskip 20pt \section*{\normalsize 4. r-Stirling identities} Theorem \ref{equ} expresses $H_n^r$ in terms of $r$-Stirling numbers. This allows us to give combinatorial proofs of hyperharmonic identities by proving the equivalent $r$-Stirling identities. This will be the focus of the rest of our paper. We make use of the following lemma: \begin{Lem} For $r + 1 \leq t \leq n + r$, the number of permutations in $T_{n+r,r+1,r}$ with $t$ as the smallest element in the right cycle is $\frac{(n + r - 1)!}{(r - 1)! (t - 1)}.$ \end{Lem} \noindent {\it Proof 1.} First place elements 1 through $t-1$ in the restricted cycles. There are ${t-1 \s r}_r = \frac{(t-2)!}{(r-1)!}$ ways to do this. Next, place element $t$ at the beginning of the right cycle. Finally, place each of the elements $t + 1$ through $n + r$ one at a time. Each element can be placed to the right of any element already placed, so there are $t \cdot (t + 1) \cdot (t + 2) \cdots (n + r - 1) = \frac{(n + r - 1)!}{(t - 1)!}$ ways to place them. Altogether, then, the number of permutations is $$\frac{(t - 2)!}{(r - 1)!} \cdot \frac{(n + r - 1)!}{(t - 1)!} = \frac{(n + r - 1)!}{(r - 1)! (t - 1)}.$$ $\hfill \Box$ \noindent {\it Proof 2.} Alternatively, we could \emph{list} the numbers 1 through $n + r$ in any order with the provision that 1 is first and the numbers 1 through $r$ must be in increasing order. There are $\binom{n + r - 1}{r - 1}$ ways to place the elements 1 through $r$ in our list, then $n!$ ways to order the numbers $r + 1$ through $n + r$ in the remaining positions. We then convert our list to a restricted permutation by starting a new cycle at each of $1,2,\ldots,r,t.$ Element $t$ has equal probability of having any position among elements $2,3,\ldots,t$, so its probability of being last among them is $\frac{1}{t-1}$. Thus the probability that we have a valid permutation is $\frac{1}{t - 1}$. The number of permutations in $T_{n+r,r+1,r}$ with $t$ as the smallest element in the right cycle, then, is $$\binom{n + r - 1}{r - 1} n! \frac{1}{t - 1} = \frac{(n + r - 1)!}{(r - 1)! (t - 1)}.$$ $\hfill \Box$ Now we are ready to prove equation (\ref{conway}). \noindent {\it Proof 1.} Since every permutation in $T_{n+r,r+1,r}$ must have some smallest element $t$ in its right cycle, with $r + 1 \leq t \leq n + r$, then by Theorem \ref{equ} we have $$H_n^r = \frac{1}{n!} {n + r \s r + 1}_r = \frac{1}{n!} \sum_{t = r + 1}^{n + r} \frac{(n + r - 1)!}{(r - 1)! (t - 1)} = \binom{n + r - 1}{r - 1} (H_{n + r - 1} - H_{r - 1}).$$ $\hfill \Box$ \noindent {\it Proof 2.} By Theorem \ref{equ}, (\ref{conway}) is transformed into the following $r$-Stirling identity: $${n + r \s 2} = (r - 1)! {n + r \s r + 1}_r + \frac{(n + r - 1)!}{(r - 1)!} { r \s 2 },$$ which is just a special case of the following identity with $r=1$ and $k=2$. $\hfill \Box$ \begin{Ident} \label{howmany} For $0 \leq r \leq m \leq n$, $${n \s k}_r = \sum_{t=r}^k {m \s t}_r {n \s k+m-t}_{m}.$$ \end{Ident} \noindent {\it Proof.} The left side counts the permutations in $T_{n, k, r}$. On the right, we condition on the number $t$ of cycles that contain the elements 1 through $m$, where $r\leq t\leq k$. We can build such a permutation in two steps. First we arrange elements $1$ through $n$ into $k+m-t$ cycles so that elements $1$ through $m$ are all in separate cycles. Next, we reduce this to $k$ cycles by converting the first $m$ cycles into $t$ cycles by treating the $m$ cycles as elements, where the first $r$ cycles are restricted to stay separate from each other. For example, if $r=3$ and $m=5$, then to create the permutation (1 5 8)(2)(3 7 4 6), we would first create the permutation (1)(2)(3 7)(4 6)(5 8), and then arrange and combine the first 5 cycles, keeping 1 through 3 in separate cycles. There are ${n \s k+m-t}_m$ ways to accomplish the first step and ${m \s t}_r$ for the second. Thus, for a given $t$ there are ${m \s t}_r {n \s k+m-t}_m$ permutations. Summing over $t$, we have the desired result. $\hfill \Box$ We note that hyperharmonic identities (\ref{conway}) and (\ref{corolrecur3}) are special cases of equation (\ref{gencon}), which by Theorem \ref{equ}, is equivalent to \begin{Ident} \label{gencontheo} For $0 \leq r \leq m \leq n$, $${n \s r+1}_r = {n \s m+1}_m {m \s r}_r + {m \s r+1}_r {n \s m}_m.$$ \end{Ident} \noindent {\it Proof.} This is a special case of Identity \ref{howmany}, with $k = r+1$. We just condition on whether elements 1 through $m$ are in restricted cycles. $\hfill \Box$ Next we prove equation (\ref{sumorders}), which is equivalent to the following identity when $k\!=\!r+1$.\\ \begin{Ident} $${n+r \s k}_r = {n \s k-r} + n \sum_{t=1}^{r} {n + r - t \s k-t+1}_{r-t+1}.$$ \end{Ident} \noindent {\it Proof.} The left side counts the permutations in $T_{n+r,k,r}$. On the right, we condition on whether there are any free elements in restricted cycles. There are ${n \s k-r}$ permutations with no free elements in restricted cycles. Otherwise, condition on the number $t$ of the first cycle with a free element. There are $n$ ways to choose the free element $m$ to immediately follow restricted element $t$. Next, there are ${n+r-t \s k-t+1}_{r-t+1}$ ways to place elements 1 through $t-1$ in their own cycles, and the other elements except $m$ into all the cycles except the first $t-1$. Finally, we insert element $m$ immediately to the right of $t$. $\hfill \Box$ Using Theorem \ref{equ}, equation (\ref{uplevel}) becomes the following $r$-Stirling identity: \begin{Ident} \label{upleveltheo} For $0 \leq m \leq r$, $${n+r \s k}_r = \sum_{s=k-r}^n \binom{n}{s} {s+r-m \s k-m}_{r-m} {n+m-s \s m}_m.$$ \end{Ident} \noindent {\it Proof.} This is just a special case of Identity \ref{useful} with $l=0$. We condition on the number $s$ of free elements that do not appear in cycles $1$ through $m$, where $0 \leq m \leq r$. $\hfill \Box$ Equation (\ref{diag}) is equivalent to the following $r$-Stirling identity when $k=r+1$: \begin{Ident} \label{diagtheo} For $0 \leq m \leq r$, $${n+r \s k}_r = \sum_{t=0}^m \binom{m}{t} \frac{n!}{(n+t-m)!} {n+r-m \s k-t}_{r-t}.$$ \end{Ident} \noindent {\it Proof.} We color the first $m$ cycles blue, and condition on the number $t$ of blue cycles that have only one element. There are $\binom{m}{t}$ ways to choose these cycles and place the restricted elements in them. Next we choose but do not place the leftmost free element to go in each of the other blue cycles; this can be done in $\binom{n}{m-t}$ ways. Now we can arrange the remaining $n+r-m$ elements in the $k-t$ allowed cycles in ${n+r-m \s k-t}_{r-t}$ ways. Finally, there are $(m-t)!$ ways to place the $m-t$ chosen free elements, each to the right of a restricted element. $\hfill \Box$ Finally, equation (\ref{rowcol}), is equivalent to the following $r$-Stirling identity. \begin{Ident} \label{rowcoltheo} For $1 \leq d \leq r$ and $1 \leq c \leq n$, $${n+r \s k}_r = \sum_{i=0}^{d-1} c \binom{n}{c} {c+i \s i+1}_{i+1} {n+r-c-i \s k-i}_{r-i} + \sum_{j=0}^{c-1} \binom{n}{j} {d+j \s d}_d {n+r-d-j \s k-d}_{r-d}.$$ \end{Ident} \noindent {\it Proof.} The left side counts the permutations in $T_{n+r, k, r}$. The right side conditions on whether there are at least $c$ free elements in the first $d$ restricted cycles. If there are, then condition on $i$, the last restricted cycle with fewer than $c$ free elements before or in it (if there are at least $c$ free elements in the first cycle, then $i = 0$). There are $\binom{n}{c}$ ways to choose which $c$ free elements are listed first in the permutation. Since at least one free element is in cycle $i+1$, there are $c$ ways to choose which is the first free element of that cycle. Then there are ${c+i \s i+1}_{i+1}$ ways to place the other $c-1$ of the $c$ first free elements. Finally, we can place the remaining $n-c$ free elements, but not in the first $i$ cycles and not in cycle $i+1$ before any elements already placed. There are ${n+r-c-i \s k-i}_{r-i}$ ways to place them. If instead there are fewer than $c$ free elements in the first $d$ cycles, then condition on the number $j$ of free elements in the first $d$ cycles. There are $\binom{n}{j}$ ways to choose these $j$ elements, ${d+j \s d}_d$ ways to place them, and ${n+r-d-j \s k-d}_{r-d}$ ways to place the remaining free elements in the other $k-d$ cycles. $\hfill \Box$ \begin{thebibliography}{20} \footnotesize \bibitem{Aigner} M. Aigner, Combinatorial Theory, Ch. 3 (Springer, New York, 1979) 98--99. \bibitem{Preston} A.T. Benjamin, G.O. Preston, and J.J. Quinn, A Stirling En{\bf count}er with Harmonic Numbers, Math. Mag. 75 (2002), 95--103. \bibitem{Broder} A.Z. Broder, The $r$-Stirling Numbers, Disc. Math. 49 (1984) 241--259. \bibitem{Carlitz} L. Carlitz, Weighted Stirling Numbers of the First and Second Kind--1, Fib. Quart. 18 (1980) 147--162. \bibitem{bookonumbers} J.H. Conway and R.K. Guy, The Book of Numbers, Copernicus, 1996. \bibitem{GKP} Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison Wesley, 1993. \bibitem{Greene} D.H. Greene and D.E. Knuth, Mathematics for the Analysis of Algorithms, Birkhauser, Boston, 1981. \bibitem{Hsu} L. Hsu and P. Shiue, A Unified Approach to Generalized Stirling Numbers, Adv. Appl. Math. 20 (1998) 366--384. \bibitem{Santmyer} J.M. Santmyer, A Stirling Like Sequence of Rational Numbers, Disc. Math. 171 (1997) 229--235. \end{thebibliography} \end{document} -------------------------------------------------- Arthur Benjamin benjamin@hmc.edu Math Department 909-621-8688 Harvey Mudd College Claremont, CA 91711