r-Stirling numbers

DefinitionUnsigned r-Stirling numbers of the first kind#✓fully proved

For natural numbers \(n\), \(m\) and \(r\), the unsigned \(r\)-Stirling number of the first kind \([n, m]_r\) is the coefficient of \(x^m\) in the polynomial with natural-number coefficients

\[x^r \prod_{r \le k < n} (x + k).\]

For \(n \ge r\) this is Broder's characterization \(\sum_m [n, m]_r \, x^m = x^r (x+r)(x+r+1) \cdots (x+n-1)\). For \(n < r\) the product is empty, so the polynomial is \(x^r\).

noncomputable def rStirlingFirst (n m r : ℕ) : ℕ :=
  Polynomial.coeff
    ((Polynomial.X : Polynomial ℕ) ^ r *
      Finset.prod (Finset.Ico r n)
        (fun k => (Polynomial.X : Polynomial ℕ) + Polynomial.C k)) m
Sources
  • A. Z. Broder, "The r-Stirling numbers", Stanford Computer Science Report STAN-CS-82-949 (December 1982), PDF page 12 / printed page 9, Equation (24); journal version: Discrete Mathematics 49 (1984), 241-259, DOI 10.1016/0012-365X(84)90161-4.
Used by 6
Used byDistribution of the canonical mesh-pattern statistic · Counting permutations by mesh-pattern matches · Broder's alternating expansion of the r-Stirling numbers of the first kind · Initial row of the r-Stirling numbers of the first kind · Recurrence for the r-Stirling numbers of the first kind · Vanishing of the r-Stirling numbers of the first kind with second index zero

TheoremInitial row of the r-Stirling numbers of the first kind#✓fully proved

For all natural numbers \(m\) and \(r\), the unsigned \(r\)-Stirling number of the first kind \([r, m]_r\) equals \(1\) if \(m = r\) and \(0\) otherwise: when the first index equals \(r\), the product in the definition is empty, so the polynomial is \(x^r\).

theorem rStirlingFirst_self (m r : ℕ) :
    rStirlingFirst r m r = if m = r then 1 else 0
Uses 1 · Used by 1
Statement usesUnsigned r-Stirling numbers of the first kind
Used byBroder's alternating expansion of the r-Stirling numbers of the first kind

TheoremVanishing of the r-Stirling numbers of the first kind with second index zero#✓fully proved

For all natural numbers \(N\) and \(r\) with \(r \ge 1\), the unsigned \(r\)-Stirling number of the first kind \([N, 0]_r\) is \(0\): the defining polynomial is divisible by \(x\), so its constant coefficient vanishes.

theorem rStirlingFirst_zero_of_pos (N r : ℕ) (hr : 1 ≤ r) :
    rStirlingFirst N 0 r = 0
Uses 1 · Used by 2
Statement usesUnsigned r-Stirling numbers of the first kind
Used byBroder's alternating expansion of the r-Stirling numbers of the first kind · Recurrence for the r-Stirling numbers of the first kind

TheoremRecurrence for the r-Stirling numbers of the first kind#✓fully proved

For natural numbers \(n\), \(m\) and \(r\) with \(1 \le r \le n\), the unsigned \(r\)-Stirling numbers of the first kind \([n, m]_r\) satisfy \([n+1, m]_r = [n, m-1]_r + n \, [n, m]_r\), where for \(m = 0\) the term \([n, m-1]_r\) is read as \([n, 0]_r\).

theorem rStirlingFirst_succ (n m r : ℕ) (hr : 1 ≤ r) (hrn : r ≤ n) :
    rStirlingFirst (n + 1) m r =
      rStirlingFirst n (m - 1) r + n * rStirlingFirst n m r
Uses 2 · Used by 1
Statement usesUnsigned r-Stirling numbers of the first kind
Proof usesVanishing of the r-Stirling numbers of the first kind with second index zero
Used byBroder's alternating expansion of the r-Stirling numbers of the first kind

TheoremBroder's alternating expansion of the r-Stirling numbers of the first kind#✓fully proved

Let \(n\), \(m\) and \(r\) be natural numbers with \(1 \le r \le n\). Write \([n, m]_r\) for the unsigned \(r\)-Stirling number of the first kind, \([a, b]\) for the unsigned Stirling number of the first kind and \(\lbrace a, b \rbrace\) for the Stirling number of the second kind. Then, in the integers,

\[(-1)^r [n, m]_r = \sum_{k=r}^{n+r-m} [n, m+k-r] \, \lbrace k-1, r-1 \rbrace \, (-1)^k.\]

Broder's Equation (43) sums over all \(k\); every term outside the range above vanishes, since \(\lbrace k-1, r-1 \rbrace\) vanishes for \(k < r\) and \([n, m+k-r]\) vanishes for \(k > n + r - m\).

theorem rStirlingFirst_eq_alternating_sum (n m r : ℕ) (hr : 0 < r)
    (hrn : r ≤ n) :
    (-1 : Int) ^ r * (rStirlingFirst n m r : Int) =
      Finset.sum (Finset.Icc r (n + r - m)) (fun k =>
        (Nat.stirlingFirst n (m + (k - r)) : Int) *
          (Nat.stirlingSecond (k - 1) (r - 1) : Int) * (-1 : Int) ^ k)
Sources
  • A. Z. Broder, "The r-Stirling numbers", Stanford Computer Science Report STAN-CS-82-949 (December 1982), PDF page 16 / printed page 13, Equation (43); journal version: Discrete Mathematics 49 (1984), 241-259, DOI 10.1016/0012-365X(84)90161-4.
Uses 4
Statement usesUnsigned r-Stirling numbers of the first kind
Proof usesInitial row of the r-Stirling numbers of the first kind · Recurrence for the r-Stirling numbers of the first kind · Vanishing of the r-Stirling numbers of the first kind with second index zero

Definitionr-Stirling numbers of the second kind#✓fully proved

For natural numbers \(n\), \(m\) and \(r\), Broder's r-Stirling number of the second kind \({n \brace m}_r\) is \(0\) unless \(r \le m\) and \(r \le n\), and otherwise

\[{n \brace m}_r = \sum_{i=0}^{n-r} \binom{n-r}{i} {n-r-i \brace m-r} r^i,\]

where \({a \brace b}\) denotes the Stirling number of the second kind (and \(0^0 = 1\)).

def rStirlingSecond (n m r : ℕ) : ℕ :=
  if r ≤ m ∧ r ≤ n then
    ∑ i ∈ range (n - r + 1), (n - r).choose i * Nat.stirlingSecond (n - r - i) (m - r) * r ^ i
  else 0
Sources
  • A. Z. Broder, The r-Stirling numbers, Discrete Mathematics 49 (1984), 241-259; Kunle Adegoke and Robert Frontczak, Three Classes of Combinatorial Sums Involving Central Binomial Coefficients and Harmonic Numbers, INTEGERS 26 (2026), Article A109, Section 4 (exponential generating function of {m+v \brace k+v}_v).
Used by 9
Used byOdd harmonic central binomial sums via r-Stirling numbers · Stirling numbers from derivatives of powers of one minus the exponential · Central binomial sums weighted by \(1 - O_{k-1}\), in r-Stirling form · Power sums of \(\binom{t}{k}(H_t - H_{t-k})\) in r-Stirling form · Finite-sum formula for r-Stirling numbers of the second kind · r-Stirling numbers as generalized Stirling numbers · r-Stirling numbers of the second kind with exactly r blocks · Vanishing of r-Stirling numbers of the second kind · r-Stirling numbers of the second kind for r = 0

TheoremFinite-sum formula for r-Stirling numbers of the second kind#✓fully proved

For all natural numbers \(n\), \(m\) and \(r\), the r-Stirling number of the second kind \({n+r \brace m+r}_r\) satisfies

\[{n+r \brace m+r}_r = \sum_{i=0}^{n} \binom{n}{i} {n-i \brace m} r^i,\]

where \({a \brace b}\) denotes the Stirling number of the second kind (and \(0^0 = 1\)).

theorem rStirlingSecond_add_add (n m r : ℕ) :
    rStirlingSecond (n + r) (m + r) r =
      ∑ i ∈ range (n + 1), n.choose i * Nat.stirlingSecond (n - i) m * r ^ i
Sources
  • A. Z. Broder, The r-Stirling numbers, Discrete Mathematics 49 (1984), 241-259.
Uses 1 · Used by 3
Statement usesr-Stirling numbers of the second kind
Used byr-Stirling numbers as generalized Stirling numbers · r-Stirling numbers of the second kind with exactly r blocks · r-Stirling numbers of the second kind for r = 0

TheoremVanishing of r-Stirling numbers of the second kind#✓fully proved

For natural numbers \(n\), \(m\) and \(r\) with \(m < r\) or \(n < r\), the r-Stirling number of the second kind \({n \brace m}_r\) is \(0\).

theorem rStirlingSecond_eq_zero {n m r : ℕ} (h : m < r ∨ n < r) : rStirlingSecond n m r = 0
Sources
  • A. Z. Broder, The r-Stirling numbers, Discrete Mathematics 49 (1984), 241-259.
Uses 1
Statement usesr-Stirling numbers of the second kind

Theoremr-Stirling numbers of the second kind for r = 0#✓fully proved

For all natural numbers \(n\) and \(m\), the r-Stirling number of the second kind \({n \brace m}_0\) equals the Stirling number of the second kind \({n \brace m}\).

theorem rStirlingSecond_zero_right (n m : ℕ) : rStirlingSecond n m 0 = Nat.stirlingSecond n m
Sources
  • A. Z. Broder, The r-Stirling numbers, Discrete Mathematics 49 (1984), 241-259.
Uses 2
Statement usesr-Stirling numbers of the second kind
Proof usesFinite-sum formula for r-Stirling numbers of the second kind

Theoremr-Stirling numbers of the second kind with exactly r blocks#✓fully proved

For all natural numbers \(n\) and \(r\), the r-Stirling number of the second kind \({n+r \brace r}_r\) equals \(r^n\) (with \(0^0 = 1\)).

theorem rStirlingSecond_add_self (n r : ℕ) : rStirlingSecond (n + r) r r = r ^ n
Sources
  • Kunle Adegoke and Robert Frontczak, Three Classes of Combinatorial Sums Involving Central Binomial Coefficients and Harmonic Numbers, INTEGERS 26 (2026), Article A109, Section 4 (exponential generating function at k = 0).
Uses 2
Statement usesr-Stirling numbers of the second kind
Proof usesFinite-sum formula for r-Stirling numbers of the second kind

Theoremr-Stirling numbers as generalized Stirling numbers#✓fully proved

For all natural numbers \(n\), \(m\) and \(r\), the r-Stirling number of the second kind \({n+r \brace m+r}_r\), viewed as a real number, equals the generalized Stirling number of the second kind of \(n\) and \(m\) (after Carlitz and Broder) at the real parameter \(x = r\).

theorem rStirlingSecond_add_add_eq_generalizedStirlingSecond (n m r : ℕ) :
    (rStirlingSecond (n + r) (m + r) r : ℝ) = generalizedStirlingSecond n m r
Sources
  • A. Z. Broder, The r-Stirling numbers, Discrete Mathematics 49 (1984), 241-259.
Uses 3
Statement usesGeneralized Stirling numbers of the second kind · r-Stirling numbers of the second kind
Proof usesFinite-sum formula for r-Stirling numbers of the second kind
11 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.