Bell numbers, Fubini numbers and Bell polynomials

Bell numbers (Dobinski, Spivey, Touchard and Turán-type identities, log-convexity), complete, partial and generalized Bell polynomials, potential polynomials, Fubini (ordered Bell) numbers and their congruences, and horse numbers.

DefinitionPartial Bell polynomial#✓fully proved

Let \(R\) be a commutative semiring, let \(n, k \in \mathbb{N}\) and let \(x_1, x_2, \dots\) be a sequence in \(R\). The partial Bell polynomial \(B_{n,k}(x)\) is the sum, over all tuples \((m_1, \dots, m_{n+1})\) of natural numbers with \(\sum_j j\, m_j = n\) and \(\sum_j m_j = k\), of

\[\frac{n!}{\prod_j m_j!\,(j!)^{m_j}} \prod_j x_j^{m_j},\]

where the quotient is a natural number, mapped into \(R\).

def partialBellPolynomial {R : Type*} [CommSemiring R]
    (n k : ℕ) (x : ℕ → R) : R :=
  ∑ m ∈ (Fintype.piFinset fun _ : Fin (n + 1) => Finset.range (n + 1)).filter
      (fun m => (∑ i, (i.val + 1) * m i = n) ∧ ∑ i, m i = k),
    (↑(n.factorial / ∏ i, (m i).factorial * (i.val + 1).factorial ^ m i) : R) *
      ∏ i, x (i.val + 1) ^ m i
Sources
  • Mihoubi, Some Congruences for the Partial Bell Polynomials, J. Integer Seq. 12 (2009), Article 09.4.1.
Used by 6
Used byHoggatt–Lind formula for colored compositions · Mansour–Sun formula for colored Dyck paths · Birmajer–Gil–Weiner formula for colored polygon partitions · Linear recurrence for INVERT convolution powers via partial Bell polynomials · Howard's formula for potential polynomials · Howard's formula for the series \(\sum_{k \ge 0} 2x^k/(k+2)!\)

TheoremDobinski's formula#✓fully proved

Let \(B_n\) denote the \(n\)-th Bell number, the number of partitions of an \(n\)-element set. For every natural number \(n\), the real series \(\sum_{k=0}^{\infty} k^n / k!\) is summable with sum \(e \cdot B_n\), so \(B_n = \frac{1}{e} \sum_{k=0}^{\infty} \frac{k^n}{k!}\). At \(n = 0\) the term \(k = 0\) is \(0^0 / 0! = 1\), matching the exponential series.

theorem dobinski_formula_hasSum (n : Nat) :
    HasSum (fun k : Nat => (k : Real) ^ n / (k.factorial : Real))
      (Real.exp 1 * (Nat.bell n : Real))
Sources

TheoremSchreyer's Fubini formula for r-horse numbers#✓fully proved

Let \(r \le n\) be natural numbers. For each \(k\), count the surjections \(f : \{0, \dots, n - 1\} \to \{0, \dots, k - 1\}\) whose values on the first \(r\) points are strictly increasing, \(f(0) < f(1) < \dots < f(r - 1)\), and let \(H\) (the \(r\)-horse number) be the sum of these counts over \(0 \le k \le n\). Then, as rational numbers,

\[ H = \frac{1}{r!} \sum_{j=0}^{r} (-1)^j \, c(r, r - j) \, F_{n-j}, \]

where \(c(r, i)\) is the unsigned Stirling number of the first kind (the number of permutations of \(r\) elements with exactly \(i\) cycles) and \(F_m\) is the \(m\)-th Fubini number.

The proof follows Schreyer's: the signed falling-factorial expansion is evaluated at integers and transported to surjection counts by image decomposition and binomial inversion, rather than by shift operators.

public theorem rHorseNumber_eq_stirlingFirst_sum_fubini
    (n r : ℕ) (hrn : r ≤ n) :
    ((∑ k ∈ Finset.range (n + 1),
        Nat.card
          { f : Fin n → Fin k //
            Function.Surjective f ∧
              ∀ i j : Fin r, i < j →
                f (Fin.castLE hrn i) < f (Fin.castLE hrn j) }) : ℚ) =
      (1 / (Nat.factorial r : ℚ)) *
        ∑ j ∈ Finset.range (r + 1),
          (-1 : ℚ) ^ j * (Nat.stirlingFirst r (r - j) : ℚ) *
            (fubiniNumber (n - j) : ℚ)
Sources
  • Benjamin Schreyer, "Rigged Horse Numbers and their Modular Periodicity," Journal of Integer Sequences 28 (2025), Article 25.4.1, Theorem, lines 211–215, https://cs.uwaterloo.ca/journals/JIS/VOL28/Schreyer/schreyer7.tex
Uses 4
Statement usesFubini numbers
Proof usesFubini numbers as sums of Stirling numbers · Signed Stirling numbers of the first kind · Orthogonality relation for Stirling numbers
3 fully proved

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.