Bell number identities

TheoremGould–Quaintance double-sum formula for Bell numbers#✓fully proved

Write \(B_n\) for the \(n\)-th Bell number and \(s(p, m) = (-1)^{p-m} {p \brack m}\) for the signed Stirling number of the first kind, where \({p \brack m}\) is the number of permutations of \(p\) elements with exactly \(m\) cycles. For all natural numbers \(n\) and \(p\), with the convention \(0^0 = 1\),

\[B_n = \sum_{k=0}^{n} (-p)^{n-k} \binom{n}{k} \sum_{m=0}^{p} B_{k+m}\, s(p, m).\]

The source states the formula for \(p \ge 1\); with \(0^0 = 1\) it also holds for \(p = 0\).

theorem bell_eq_signed_stirlingFirst_convolution
    (n p : ℕ) :
    (Nat.bell n : ℤ) =
      ∑ k ∈ Finset.range (n + 1),
        (-(p : ℤ)) ^ (n - k) * (Nat.choose n k : ℤ) *
          (∑ m ∈ Finset.range (p + 1),
            (Nat.bell (k + m) : ℤ) * ((-1 : ℤ) ^ (p - m) * (Nat.stirlingFirst p m : ℤ)))
Sources
  • H. W. Gould and Jocelyn Quaintance, "Implications of Spivey's Bell Number Formula," Journal of Integer Sequences 11 (2008), Article 08.3.7, Theorem, equation (E:4), lines 177–182, https://cs.uwaterloo.ca/journals/JIS/VOL11/Gould/gould35.tex

TheoremBell numbers are row sums of Stirling numbers of the second kind#✓fully proved

For every natural number \(n\), the Bell number \(B_n\) equals \(\sum_{k=0}^{n} S(n, k)\), where \(S(n, k)\) is the Stirling number of the second kind.

theorem bell_eq_sum_stirlingSecond (n : ℕ) : n.bell = ∑ k ∈ Finset.range (n + 1),
  n.stirlingSecond k
Sources
2 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.