Lee's identities for Stirling numbers

TheoremLee's expansion of shifted Stirling numbers of the first kind#●ready to prove

Write \(c(n, k)\) for the unsigned Stirling number of the first kind, the number of permutations of \(n\) elements with exactly \(k\) cycles. For natural numbers \(m \le n\), the following identity of integers holds:

\[c(n + 1, m + 1) = \sum_{k=m}^{n} (-1)^{n-k} \binom{k}{m}\, n^{k-m}\, c(n, k).\]

theorem_wanted stirlingFirst_succ_eq_sum_choose_pow {m n : ℕ} (hmn : m ≤ n) :
    (Nat.stirlingFirst (n + 1) (m + 1) : ℤ) =
      ∑ k ∈ Finset.Icc m n,
        (Nat.stirlingFirst n k : ℤ) * (Nat.choose k m : ℤ) *
          (-1 : ℤ) ^ (n - k) * (n : ℤ) ^ (k - m)

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Theorem 1.

TheoremLee's alternating expansion of Stirling numbers of the second kind#●ready to prove

Write \(S(n, k)\) for the Stirling number of the second kind, the number of partitions of an \(n\)-element set into \(k\) nonempty blocks. For natural numbers \(m \le n\), the following identity of integers holds:

\[S(n, m) = \sum_{k=m}^{n} (-1)^{k-m} \binom{n}{k}\, m^{n-k}\, S(k, m).\]

theorem_wanted stirlingSecond_eq_sum_choose_pow {m n : ℕ} (hmn : m ≤ n) :
    (Nat.stirlingSecond n m : ℤ) =
      ∑ k ∈ Finset.Icc m n,
        (Nat.choose n k : ℤ) * (Nat.stirlingSecond k m : ℤ) *
          (m : ℤ) ^ (n - k) * (-1 : ℤ) ^ (k - m)

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Theorem 2.

TheoremLee's identity for Stirling numbers of the second kind from smaller rows#●ready to prove

Write \(S(n, k)\) for the Stirling number of the second kind, the number of partitions of an \(n\)-element set into \(k\) nonempty blocks. For natural numbers \(k\) and \(n\) with \(k \ge 1\) and \(n \ge k + 1\), the following identity of integers holds:

\[(n - k)\, S(n, k) = \sum_{j=2}^{n-k+1} (-1)^j \binom{n}{j}\, S(n-j+1, k).\]

This is Lee's Theorem 4 with the denominator \(n - k\) cleared.

theorem_wanted stirlingSecond_mul_sub_eq_sum_choose_alternating
    {k n : ℕ} (hk : 1 ≤ k) (hkn : k + 1 ≤ n) :
    ((n : ℤ) - k) * (Nat.stirlingSecond n k : ℤ) =
      ∑ j ∈ Finset.Icc 2 (n - k + 1),
        (Nat.choose n j : ℤ) * (Nat.stirlingSecond (n - j + 1) k : ℤ) *
          (-1 : ℤ) ^ j

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Theorem 4.

TheoremLee's factorial-weighted alternating row sum of Stirling numbers of the second kind#●ready to prove

Write \(S(a, j)\) for the Stirling number of the second kind, the number of partitions of an \(a\)-element set into \(j\) nonempty blocks. For every natural number \(a \ge 1\), the following identity of integers holds:

\[\sum_{j=2}^{a} (-1)^j\, (j-2)!\, S(a, j) = a - 1.\]

theorem_wanted sum_stirlingSecond_factorial_alternating
    {a : ℕ} (ha : 1 ≤ a) :
    (∑ j ∈ Finset.Icc 2 a,
      (Nat.stirlingSecond a j : ℤ) * (Nat.factorial (j - 2) : ℤ) *
        (-1 : ℤ) ^ j) = (a : ℤ) - 1

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Lemma 6.

TheoremLee's identity for Stirling numbers of the second kind from higher columns#●ready to prove

Write \(S(n, k)\) for the Stirling number of the second kind, the number of partitions of an \(n\)-element set into \(k\) nonempty blocks. For natural numbers \(k\) and \(n\) with \(k \ge 1\) and \(n \ge k + 1\), the following identity of integers holds:

\[(n - k)\, S(n, k) = \sum_{j=2}^{n-k+1} (j-2)!\, (-1)^j \binom{k+j-1}{j}\, S(n, k+j-1).\]

This is Lee's Theorem 8 with the denominator \(n - k\) cleared and the generalized binomial coefficient written as \(\binom{-k}{j} = (-1)^j \binom{k+j-1}{j}\).

theorem_wanted stirlingSecond_mul_sub_eq_sum_factorial_negChoose
    {k n : ℕ} (hk : 1 ≤ k) (hkn : k + 1 ≤ n) :
    ((n : ℤ) - k) * (Nat.stirlingSecond n k : ℤ) =
      ∑ j ∈ Finset.Icc 2 (n - k + 1),
        (Nat.factorial (j - 2) : ℤ) *
          ((-1 : ℤ) ^ j * (Nat.choose (k + j - 1) j : ℤ)) *
          (Nat.stirlingSecond n (k + j - 1) : ℤ)

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Theorem 8.

TheoremLee's identity for Stirling numbers of the first kind from smaller rows#●ready to prove

Write \(c(n, k)\) for the unsigned Stirling number of the first kind, the number of permutations of \(n\) elements with exactly \(k\) cycles. For natural numbers \(k\) and \(n\) with \(k \ge 1\) and \(n \ge k + 1\), the following identity of integers holds:

\[(n - k)\, c(n, k) = \sum_{j=2}^{n-k+1} \binom{n}{j}\, (j-2)!\, c(n-j+1, k).\]

This is Lee's Theorem 11 with the denominator \(n - k\) cleared.

theorem_wanted stirlingFirst_mul_sub_eq_sum_choose_factorial
    {k n : ℕ} (hk : 1 ≤ k) (hkn : k + 1 ≤ n) :
    ((n : ℤ) - k) * (Nat.stirlingFirst n k : ℤ) =
      ∑ j ∈ Finset.Icc 2 (n - k + 1),
        (Nat.choose n j : ℤ) * (Nat.stirlingFirst (n - j + 1) k : ℤ) *
          (Nat.factorial (j - 2) : ℤ)

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Theorem 11.

TheoremLee's identity for Stirling numbers of the first kind from higher columns#●ready to prove

Write \(c(n, k)\) for the unsigned Stirling number of the first kind, the number of permutations of \(n\) elements with exactly \(k\) cycles. For natural numbers \(k\) and \(n\) with \(k \ge 1\) and \(n \ge k + 1\), the following identity of integers holds:

\[(n - k)\, c(n, k) = \sum_{j=2}^{n-k+1} \binom{k+j-1}{j}\, c(n, k+j-1).\]

This is Lee's Theorem 14 with the denominator \(n - k\) cleared.

theorem_wanted stirlingFirst_mul_sub_eq_sum_stirlingFirst_choose
    {k n : ℕ} (hk : 1 ≤ k) (hkn : k + 1 ≤ n) :
    ((n : ℤ) - k) * (Nat.stirlingFirst n k : ℤ) =
      ∑ j ∈ Finset.Icc 2 (n - k + 1),
        (Nat.stirlingFirst n (k + j - 1) : ℤ) *
          (Nat.choose (k + j - 1) j : ℤ)

Sources

• Kwankyu Lee, "Some New Identities for Stirling Numbers", Theorem 14.

7 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.