Stirling Numbers (First and Second Kind)

Problem Overview

Learning Goals

After studying this topic, you will be able to:

• Define and distinguish Stirling numbers of the first and second kind
• Compute Stirling numbers using DP recurrence relations
• Apply Stirling numbers to count permutations with k cycles
• Apply Stirling numbers to count ways to partition a set into k non-empty subsets
• Handle the sign convention for unsigned vs signed Stirling numbers of the first kind

Problem Statement

Stirling Numbers of the Second Kind: S(n, k)

Definition: S(n, k) counts the number of ways to partition a set of n distinct elements into exactly k non-empty, unordered subsets.

Example: S(4, 2) = 7 means there are 7 ways to partition {1, 2, 3, 4} into 2 non-empty subsets.

Stirling Numbers of the First Kind: s(n, k)

Intuition: How to Think About This Problem

Pattern Recognition

Key Question: How do we count structured arrangements when order partially matters?

Stirling numbers bridge the gap between simple counting and complex combinatorics:

• Second Kind S(n,k): Think of distributing n labeled balls into k identical boxes (non-empty)

• **First Kind

  s(n,k)

  :** Think of arranging n people into k circular tables

Breaking Down the Problem

1. What are we looking for? Number of ways to structure n elements into k groups
2. What information do we have? The total count n and target groups k
3. What’s the relationship? Each new element either joins an existing group or starts a new one

Analogies

Second Kind: Imagine seating n guests at k identical round tables where every table must have at least one guest. The tables are indistinguishable, but guests are distinguishable.

First Kind: Imagine n runners in a relay race forming k separate relay teams, where each team runs in a cycle (the order within each team matters cyclically).

Recurrence Relations

Stirling Numbers of the Second Kind

S(n, k) = k * S(n-1, k) + S(n-1, k-1)

Why?

• k * S(n-1, k): Element n joins one of k existing subsets (k choices)
• S(n-1, k-1): Element n forms its own singleton subset

Stirling Numbers of the First Kind (Unsigned)

|s(n, k)| = (n-1) * |s(n-1, k)| + |s(n-1, k-1)|

Why?

• (n-1) * |s(n-1, k)|: Element n is inserted after one of (n-1) existing elements in some cycle
• |s(n-1, k-1)|: Element n forms its own 1-cycle (fixed point)

Base Cases

Dry Run: Computing S(4, 2) and |s(4, 2)|

Computing S(4, 2) - Second Kind

Goal: Count partitions of {1,2,3,4} into 2 non-empty subsets.

Build the DP table bottom-up:

n\k |  0    1    2    3    4
----+------------------------
 0  |  1    0    0    0    0
 1  |  0    1    0    0    0
 2  |  0    1    1    0    0
 3  |  0    1    3    1    0
 4  |  0    1    7    6    1

Computing S(4, 2):
  S(4, 2) = 2 * S(3, 2) + S(3, 1)
          = 2 * 3 + 1
          = 7

The 7 partitions of {1,2,3,4} into 2 subsets:

1. {1}

   {2,3,4}

2. {2}

   {1,3,4}

3. {3}

   {1,2,4}

4. {4}

   {1,2,3}

5. {1,2}

   {3,4}

6. {1,3}

   {2,4}

7. {1,4}

   {2,3}

Computing |s(4, 2)| - First Kind (Unsigned)

Goal: Count permutations of {1,2,3,4} with exactly 2 cycles.

Build the DP table bottom-up:

n\k |  0    1    2    3    4
----+------------------------
 0  |  1    0    0    0    0
 1  |  0    1    0    0    0
 2  |  0    1    1    0    0
 3  |  0    2    3    1    0
 4  |  0    6   11    6    1

Computing |s(4, 2)|:
  |s(4, 2)| = 3 * |s(3, 2)| + |s(3, 1)|
            = 3 * 3 + 2
            = 11

The 11 permutations with 2 cycles (in cycle notation):

1. (1)(234) - 1 fixed, 2->3->4->2
2. (1)(243) - 1 fixed, 2->4->3->2
3. (2)(134)
4. (2)(143)
5. (3)(124)
6. (3)(142)
7. (4)(123)
8. (4)(132)
9. (12)(34)
10. (13)(24)
11. (14)(23)

Common Mistakes

Mistake 1: Confusing the Two Kinds

# WRONG: Using second kind formula for first kind
s[n][k] = k * s[n-1][k] + s[n-1][k-1]  # This is S(n,k)!

# CORRECT: First kind uses (n-1) multiplier
s[n][k] = (n-1) * s[n-1][k] + s[n-1][k-1]

Problem: The recurrences look similar but have different multipliers. Fix: Remember - Second kind: k (choices of subset), First kind: (n-1) (positions to insert).

Mistake 2: Sign Errors in First Kind

# WRONG: Ignoring sign for signed Stirling numbers
signed_s = unsigned_s  # Missing sign!

# CORRECT: Apply sign based on parity
signed_s = ((-1) ** (n - k)) * unsigned_s

Problem: The signed version alternates based on (n-k). Fix: Use (-1)^(n-k) factor when signed version is needed.

Mistake 3: Wrong Base Cases

# WRONG: Forgetting S(n,1) for first kind
s[n][1] = 1  # This is for second kind!

# CORRECT: First kind single cycle
s[n][1] = factorial(n - 1)  # (n-1)! circular arrangements

Problem: S(n,1) = 1 but |s(n,1)| = (n-1)! Fix: Remember that one cycle of n elements has (n-1)! arrangements.

Mistake 4: Integer Overflow

# WRONG: No modular arithmetic for large values
S[n][k] = k * S[n-1][k] + S[n-1][k-1]

# CORRECT: Apply modulo at each step
MOD = 10**9 + 7
S[n][k] = (k * S[n-1][k] + S[n-1][k-1]) % MOD

Edge Cases

When to Use This Pattern

Use Stirling Numbers of the Second Kind When:

• Partitioning labeled objects into unlabeled groups
• Counting surjections (onto functions) from n to k elements
• Distribution problems with identical boxes
• Computing Bell numbers (sum over all k)

Use Stirling Numbers of the First Kind When:

• Counting permutations by cycle structure
• Analyzing random permutations
• Computing rising/falling factorials
• Problems involving derangements generalized to k cycles

Pattern Recognition Checklist:

• Partitioning a set into groups? Check if order within groups matters
• Counting permutations? Check if cycle structure is relevant
• Distribution problem? Determine if containers are distinguishable
• Polynomial expansion? Check for falling factorial connections

Solutions

Python Implementation

def stirling_second_kind(n: int, k: int, mod: int = None) -> int:
  """
  Compute S(n, k) - Stirling number of the second kind.
  Counts partitions of n elements into k non-empty subsets.

  Time: O(n * k)
  Space: O(k) with space optimization
  """
  if k > n or k < 0:
    return 0
  if k == 0:
    return 1 if n == 0 else 0

  # Space-optimized DP
  dp = [0] * (k + 1)
  dp[0] = 1

  for i in range(1, n + 1):
    # Traverse right to left to avoid overwriting
    for j in range(min(i, k), 0, -1):
      dp[j] = j * dp[j] + dp[j - 1]
      if mod:
        dp[j] %= mod

  return dp[k]


def stirling_first_kind_unsigned(n: int, k: int, mod: int = None) -> int:
  """
  Compute |s(n, k)| - Unsigned Stirling number of the first kind.
  Counts permutations of n elements with exactly k cycles.

  Time: O(n * k)
  Space: O(k) with space optimization
  """
  if k > n or k < 0:
    return 0
  if k == 0:
    return 1 if n == 0 else 0

  # Space-optimized DP
  dp = [0] * (k + 1)
  dp[0] = 1

  for i in range(1, n + 1):
    # Traverse right to left to avoid overwriting
    for j in range(min(i, k), 0, -1):
      dp[j] = (i - 1) * dp[j] + dp[j - 1]
      if mod:
        dp[j] %= mod
    dp[0] = 0  # s(i, 0) = 0 for i > 0

  return dp[k]


def stirling_second_kind_table(n: int, mod: int = None) -> list:
  """
  Build full table of S(i, j) for 0 <= i <= n, 0 <= j <= i.

  Time: O(n^2)
  Space: O(n^2)
  """
  S = [[0] * (n + 1) for _ in range(n + 1)]
  S[0][0] = 1

  for i in range(1, n + 1):
    for j in range(1, i + 1):
      S[i][j] = j * S[i-1][j] + S[i-1][j-1]
      if mod:
        S[i][j] %= mod

  return S


def stirling_first_kind_table(n: int, mod: int = None) -> list:
  """
  Build full table of |s(i, j)| for 0 <= i <= n, 0 <= j <= i.

  Time: O(n^2)
  Space: O(n^2)
  """
  s = [[0] * (n + 1) for _ in range(n + 1)]
  s[0][0] = 1

  for i in range(1, n + 1):
    for j in range(1, i + 1):
      s[i][j] = (i - 1) * s[i-1][j] + s[i-1][j-1]
      if mod:
        s[i][j] %= mod

  return s


# Example usage
if __name__ == "__main__":
  print("S(4, 2) =", stirling_second_kind(4, 2))  # Output: 7
  print("|s(4, 2)| =", stirling_first_kind_unsigned(4, 2))  # Output: 11

  # Print full tables
  print("\nStirling Second Kind Table S(n,k):")
  S = stirling_second_kind_table(5)
  for i in range(6):
    print(f"n={i}:", S[i][:i+1])

  print("\nStirling First Kind Table |s(n,k)|:")
  s = stirling_first_kind_table(5)
  for i in range(6):
    print(f"n={i}:", s[i][:i+1])

Applications and Identities

Key Identities

Sum to factorial (First Kind):

Sum over k from 0 to n of |s(n, k)| = n!

All permutations partitioned by cycle count.

Sum to Bell number (Second Kind):

B(n) = Sum over k from 0 to n of S(n, k)

Bell number counts all partitions of n elements.

Falling Factorial Expansion:

x^(n) = x(x-1)(x-2)...(x-n+1) = Sum over k of s(n,k) * x^k

Rising Factorial Expansion:

x^n = Sum over k of S(n,k) * x^(k)

where x^(k) is the falling factorial.

Surjections Count:

Number of surjections from n to k = k! * S(n, k)

Practical Applications

Related Problems

Prerequisites (Do These First)

Direct Applications

Harder (Do These After)

Key Takeaways

1. The Core Idea: Stirling numbers count structured partitions - either unordered subsets (Second Kind) or cyclic arrangements (First Kind).

2. Recurrence Pattern: Both follow similar DP structure: new element either extends existing structure or creates new one.

3. Sign Convention: Unsigned first kind for counting; signed first kind for polynomial identities.

4. Applications: Foundation for Bell numbers, surjection counting, and polynomial basis transformations.

Practice Checklist

Before moving on, make sure you can:

• Write both recurrences from memory
• Compute small values by hand (up to n=5)
• Explain the combinatorial meaning of each kind
• Implement space-optimized DP in under 10 minutes
• Apply to counting surjections and set partitions