← Back to the home page

r-Stirling numbers of the second kind

$$\left\{\begin{matrix} n \\ k \end{matrix}\right\}_{r}$$ is the number of ways of partitioning an $n$ element set into $k$ subsets such that $r$ distinguished elements are in different blocks.

Cases

• Case $r=2$: https://oeis.org/A143494
• Case $r=3$: https://oeis.org/A143495
• Case $r=4$: https://oeis.org/A143496
• Case $r=5$: https://oeis.org/A193685

Recurrence

• $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}_{r} = 0 \quad \text{for } n < r$$
• $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}_{r} = 1 \quad \text{for } n = k = r$$
• $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}_{r} = k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\} + \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\}$$
• $$\left\{\begin{matrix} n \\ k \end{matrix}\right\}_{r} = \left\{\begin{matrix} n \\ k \end{matrix}\right\}_{r-1} - (r-1)\left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}_{r-1}$$

Formulas

$$\left\{ {n \atop m} \right\}_r = \sum_k \binom{n-r}{k} \left\{ {k \atop m-r} \right\} r^{n-r-k}$$

Identities

See here

Generating Functions

Exponential Generating Function

$$\sum_k \left\{ {k+r \atop m+r} \right\}_r \frac{z^k}{k!} = \begin{cases} \frac{1}{m!} e^{rz} (e^z - 1)^m, & \text{if } m \geq 0, \\ 0, & \text{otherwise.} \end{cases}$$

Ordinary Generating Functions

$$\sum_k \left\{ {k \atop m} \right\}_r z^k = \begin{cases} \frac{z^m}{(1-rz)(1-(r+1)z)\cdots(1-mz)}, & \text{if } m \geq r \geq 0, \\ 0, & \text{otherwise.} \end{cases}$$

$$\sum_k \left\{ {n+r \atop k+r} \right\}_r x^{\underline{k}} = (x+r)^n, \quad n \geq 0.$$

Double Generating Function

$$\sum_{k,m} \left\{ {k+r \atop m+r} \right\}_r \frac{z^k}{k!} t^m = \exp(t(e^z - 1) + rz)$$

Articles

Andrei Broder: The r-Stirling numbers