Stirling Numbers: Algorithm Implementation and Proof

1. Introduction and Core Concepts

Stirling numbers are a fundamental class of combinatorial numbers that arise when counting ways to partition or permute sets. Named after the Scottish mathematician James Stirling, who introduced them in the 18th century, these numbers appear in two distinct forms: Stirling numbers of the first kind and Stirling numbers of the second kind. Despite sharing a name, they count very different combinatorial objects and satisfy different recurrences, yet both are deeply connected to factorials, Bell numbers, and the structure of discrete mathematics.

Stirling numbers of the second kind, denoted as S(n, k) or {n \brace k}, count the number of ways to partition a set of n labeled objects into k non-empty, unlabeled subsets. For example, S(4, 2) = 7 means there are seven ways to divide four distinct elements into two non-empty groups where the order of the groups does not matter. This interpretation makes them essential for any problem involving clustering, grouping, or equivalence relations. In contrast, Stirling numbers of the first kind, denoted as s(n, k) or c(n, k) for the unsigned version, count the number of permutations of n elements with exactly k disjoint cycles. The signed and unsigned variants differ only by a factor of (-1)^(n-k).

Understanding stirling numbers matters because they form a bridge between powers and falling factorials, between combinatorial enumeration and algebraic expansions. They appear in the formula for converting x^n into a sum of falling factorials, in the moments of probability distributions, in the analysis of hash collisions, and in the complexity of recursive algorithms. For software engineers and computer scientists, stirling numbers provide a precise tool for counting states in distributed systems, analyzing database sharding strategies, and understanding the combinatorics behind caching and load balancing. Mastery of their properties and efficient implementation is therefore both theoretically rewarding and practically valuable.

Two Kinds, One Family

The two kinds of stirling numbers are often confused but can be distinguished by a simple mnemonic: the second kind partitions sets into subsets, while the first kind partitions permutations into cycles. The second kind is more frequently encountered in programming interviews and system design because its partition interpretation maps directly to real-world grouping problems. The first kind is crucial for analyzing permutation algorithms, sorting networks, and random permutation generation.

Both kinds satisfy triangular recurrences that make them ideal for dynamic programming. They are also related through orthogonality relations and matrix inversion: the matrices formed by s(n,k) and S(n,k) are inverses of each other. This duality underscores their importance in combinatorial mathematics and provides powerful proof techniques for algorithmic analysis.

2. How It Works

The mechanism behind stirling numbers is best understood through their recurrence relations, which describe how larger instances are built from smaller ones. For Stirling numbers of the second kind, the recurrence is S(n, k) = k * S(n-1, k) + S(n-1, k-1), with base cases S(0,0) = 1, S(n,0) = 0 for n > 0, and S(0,k) = 0 for k > 0. The intuition is elegant: consider the nth element in a partition of n elements into k subsets. Either it forms a singleton subset by itself, leaving n-1 elements to be partitioned into k-1 subsets, or it is inserted into one of the k existing subsets formed by the first n-1 elements. There are k choices for the latter, hence the multiplicative factor.

For unsigned Stirling numbers of the first kind, denoted c(n, k), the recurrence is c(n, k) = (n-1) * c(n-1, k) + c(n-1, k-1). Here the logic is based on permutations: when inserting the nth element into a permutation of n-1 elements with k cycles, it can either form a new cycle of length one, or be inserted after any of the n-1 existing elements within the k cycles. The signed version s(n, k) follows s(n, k) = s(n-1, k-1) - (n-1) * s(n-1, k), introducing alternating signs that reflect inclusion-exclusion in the cycle structure.

Beyond recurrences, stirling numbers possess explicit closed-form formulas. For the second kind, the inclusion-exclusion principle yields S(n, k) = (1/k!) * sum_{i=0}^{k} (-1)^{k-i} * C(k, i) * i^n, where C(k, i) is the binomial coefficient. This formula is theoretically important and useful for small k, but it requires O(k) arithmetic operations with large integers and factorials. There is also a connection to falling factorials: x^n = sum_{k=0}^{n} S(n, k) * (x)_k, where (x)_k = x*(x-1)*...*(x-k+1) is the falling factorial. Conversely, (x)_n = sum_{k=0}^{n} s(n, k) * x^k. These identities are the basis for many proofs and for converting between polynomial bases.

The Combinatorial Proof Technique

Proofs involving stirling numbers typically use double counting, induction, or generating functions. A classic proof of the recurrence for S(n,k) uses a combinatorial argument as described above, partitioning based on the fate of the nth element. An inductive proof then shows the recurrence uniquely defines the numbers. Generating functions provide another powerful lens: the exponential generating function for S(n,k) with fixed k is (e^x - 1)^k / k!, while for c(n,k) it is related to the rising factorial. These generating functions are not just theoretical curiosities; they lead to efficient algorithms for computing entire rows of the Stirling triangle at once.

The orthogonality property, sum_{k} s(n,k) * S(k,m) = delta_{n,m}, where delta is the Kronecker delta, proves that the two kinds of stirling numbers are matrix inverses. This can be proven by composing the two polynomial basis conversions. Such proofs are common in advanced algorithm analysis where one needs to invert combinatorial transforms.

3. Implementation

Implementing stirling numbers efficiently requires careful handling of recursion, memoization, and integer overflow. The naive recursive implementation directly follows the recurrence but has exponential time complexity due to repeated subproblems. Adding memoization reduces it to polynomial time, while bottom-up dynamic programming eliminates recursion overhead and is preferred for production code. For large n and k, modular arithmetic is often required to prevent integer explosion, as S(100, 50) has over 150 digits.

The following implementations demonstrate the core techniques in Python. All code examples escape comparison operators for HTML safety and include detailed comments to clarify the combinatorial logic.

def stirling_second_recursive(n, k, memo=None):
    """
    Compute S(n,k) using recursion + memoization.
    Recurrence: S(n,k) = k * S(n-1,k) + S(n-1,k-1)
    Base: S(0,0)=1, S(n,0)=0 for n>0, S(0,k)=0 for k>0
    """
    if memo is None:
        memo = {}
    # Base cases
    if n == 0 and k == 0:
        return 1
    if n == 0 or k == 0:
        return 0
    if k > n:
        return 0
    if (n, k) in memo:
        return memo[(n, k)]
    # Recursive step with memoization
    result = k * stirling_second_recursive(n-1, k, memo) + stirling_second_recursive(n-1, k-1, memo)
    memo[(n, k)] = result
    return result

# Example: S(5,3) = 25
print(stirling_second_recursive(5, 3))

def stirling_second_dp(n, k):
    """
    Bottom-up DP for S(n,k). O(n*k) time, O(n*k) space.
    Builds the Stirling triangle row by row.
    dp[i][j] stores S(i,j) for 0 <= i <= n, 0 <= j <= k
    """
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        # j cannot exceed i, as you cannot partition i elements into more than i subsets
        for j in range(1, min(i, k)+1):
            # S(i,j) = j * S(i-1,j) + S(i-1,j-1)
            dp[i][j] = j * dp[i-1][j] + dp[i-1][j-1]
    return dp[n][k]

# Build full triangle up to n=6
for i in range(7):
    row = [stirling_second_dp(i, j) for j in range(i+1)]
    print(f"n={i}: {row}")

def stirling_first_unsigned(n, k):
    """
    Compute unsigned Stirling numbers of the first kind c(n,k).
    c(n,k) counts permutations of n elements with exactly k cycles.
    Recurrence: c(n,k) = (n-1) * c(n-1,k) + c(n-1,k-1)
    """
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(1, min(i, k)+1):
            dp[i][j] = (i-1) * dp[i-1][j] + dp[i-1][j-1]
    return dp[n][k]

def stirling_first_signed(n, k):
    """Signed version s(n,k) = (-1)^(n-k) * c(n,k)"""
    c = stirling_first_unsigned(n, k)
    if (n - k) % 2 == 1:
        return -c
    return c

# Example: c(4,2) = 11, s(4,2) = 11 because n-k is even
print(f"c(4,2)={stirling_first_unsigned(4,2)}, s(4,2)={stirling_first_signed(4,2)}")
# c(5,2)=50, s(5,2)=-50
print(f"c(5,2)={stirling_first_unsigned(5,2)}, s(5,2)={stirling_first_signed(5,2)}")

import math

def stirling_second_explicit(n, k):
    """
    Explicit inclusion-exclusion formula:
    S(n,k) = 1/k! * sum_{i=0}^{k} (-1)^{k-i} * C(k,i) * i^n
    Efficient when k is small, n is large. O(k) time.
    """
    total = 0
    for i in range(k+1):
        comb = math.comb(k, i)
        term = comb * pow(i, n)
        if (k - i) % 2 == 1:
            total -= term
        else:
            total += term
    return total // math.factorial(k)

def stirling_second_optimized(n, k, mod=None):
    """
    Space-optimized DP: O(n*k) time, O(k) space.
    Only keeps previous row. Supports modulo for large numbers.
    Ideal for competitive programming with mod = 10**9+7.
    """
    prev = [0] * (k+1)
    prev[0] = 1
    for i in range(1, n+1):
        curr = [0] * (k+1)
        # j ranges 1..min(i,k)
        for j in range(1, min(i, k)+1):
            val = j * prev[j] + prev[j-1]
            if mod is not None:
                val %= mod
            curr[j] = val
        prev = curr
    return prev[k]

# Example with modulo for large values
print(stirling_second_explicit(10, 3))  # 9330
print(stirling_second_optimized(100, 5, mod=10**9+7))

These four patterns cover the majority of use cases. The recursive version is excellent for understanding and for sparse queries, the full DP table is best when you need many values, the explicit formula shines for small k, and the space-optimized version is essential for memory-constrained environments or when n is large, such as n=5000 and k=100.

4. Step-by-Step Example

To solidify understanding, let us walk through the computation of S(5, 3) = 25 using the recurrence. This example demonstrates both the combinatorial meaning and the DP table construction. We want to count partitions of the set {1,2,3,4,5} into exactly 3 non-empty unlabeled subsets.

We build a DP table where rows represent n from 0 to 5 and columns represent k from 0 to 3. Initialize dp[0][0] = 1. For n=1: S(1,1) = 1*S(0,1) + S(0,0) = 0 + 1 = 1. For n=2: S(2,1) = 1*S(1,1) + S(1,0) = 1*1 + 0 = 1, and S(2,2) = 2*S(1,2) + S(1,1) = 0 + 1 = 1. For n=3: S(3,1) = 1*S(2,1) + S(2,0) = 1, S(3,2) = 2*S(2,2) + S(2,1) = 2*1 + 1 = 3, S(3,3) = 3*S(2,3) + S(2,2) = 1. This matches intuition: three elements can be partitioned into two subsets in three ways.

Continuing to n=4: S(4,1)=1, S(4,2)=2*S(3,2)+S(3,1)=2*3+1=7, S(4,3)=3*S(3,3)+S(3,2)=3*1+3=6. Finally for n=5: S(5,1)=1, S(5,2)=2*S(4,2)+S(4,1)=2*7+1=15, S(5,3)=3*S(4,3)+S(4,2)=3*6+7=25. The table below shows the complete triangle up to n=5.

Combinatorially, why is S(5,3)=25? We can enumerate by integer partitions of 5 into 3 parts: the possible block size patterns are 3+1+1 and 2+2+1. For pattern 3+1+1, choose 3 elements for the triple: C(5,3)=10 ways, but the two singletons are unlabeled, so no further division. For pattern 2+2+1, choose 1 element for the singleton: C(5,1)=5 ways, then partition remaining 4 into two pairs: C(4,2)/2=3 ways (divide by 2 because the two pairs are unlabeled), giving 5*3=15. Total 10+15=25, confirming the recurrence result. This double-counting verification is a typical proof technique for stirling numbers.

Tracing the First Kind Example

For contrast, consider c(4,2)=11, the number of permutations of 4 elements with exactly 2 cycles. Using the recurrence c(4,2)=(4-1)*c(3,2)+c(3,1)=3*3+2=11. The permutations can be listed: cycle type (3,1) gives 8 permutations (choose 3 elements for the 3-cycle: C(4,3)=4, and there are 2 distinct 3-cycles on 3 labeled elements), and type (2,2) gives 3 permutations (pairings). Total 11. This step-by-step expansion shows how the factor (n-1) accounts for inserting the new element into existing cycles.

5. Complexity Analysis

The computational complexity of stirling numbers depends heavily on the chosen algorithm and whether you need a single value S(n,k) or the entire triangle up to n. The naive recursion without memoization has exponential complexity because it recomputes the same subproblems many times, with a branching factor of approximately 2. Memoization or DP reduces this to polynomial time by ensuring each state is computed once.

For bottom-up DP that computes a single S(n,k), the time complexity is O(n*k) because we fill a table of size (n+1)*(k+1) but only up to min(i,k) per row. Space is O(n*k) for the full table, or O(k) with optimization. The explicit inclusion-exclusion formula runs in O(k log n) time due to exponentiation and O(k) space, but it involves large integer arithmetic and division by k!, making it slower in practice for large k due to big integer costs. When computing all S(n,k) for fixed n and all k, the DP approach is optimal.

Best, average, and worst cases are often identical for DP because the table size is deterministic, but recursive memoization can have best case O(k) if many queries hit the memo cache. For modular arithmetic with mod prime, operations are O(1), but for exact big integers, multiplication cost grows with the number of digits, roughly O(M(d)) where d is digits, so worst-case time can be higher than theoretical O(n*k).

* Best case for memoized recursion assumes cache hits; first computation is still O(n*k).

For Stirling numbers of the first kind, complexities are identical because the recurrence structure is the same, only the coefficient changes from k to (n-1). When n and k are up to 5000, O(n*k) = 25e6 operations is feasible in Python with PyPy and optimization, but for n=10000, you need either NumPy or modular arithmetic with iterative loops in pure Python may be borderline. In such cases, using the explicit formula for small k (e.g., k < 20) is dramatically faster.

Big Integer Considerations

Stirling numbers grow super-exponentially. S(n, n/2) is asymptotically large, and S(100, 50) has 152 digits. Python's arbitrary-precision integers handle this but multiplication of large ints is not O(1). For n > 200, exact values may exceed memory if you store the full triangle. In practice, most applications use modulo 10^9+7 or modulo 2^64, which keeps numbers bounded and operations O(1). Always clarify whether the problem requires exact or modular results before choosing an implementation.

6. Variations and Optimizations

Several important variations extend the basic stirling numbers. Bell numbers B(n) = sum_{k=0}^{n} S(n,k) count all partitions of an n-element set without fixing k. They satisfy B(n+1) = sum_{k=0}^{n} C(n,k) * B(k) and can be computed efficiently using the Bell triangle (Aitken's array). Lah numbers L(n,k) = C(n-1, k-1) * n! / k! count partitions into ordered subsets. Associated Stirling numbers and restricted Stirling numbers impose constraints like minimum block size.

A key optimization for computing stirling numbers modulo a prime p is to use NTT (Number Theoretic Transform) or convolution via the explicit formula. Since S(n,k) = 1/k! * sum_{i} (-1)^{k-i} C(k,i) i^n, the sum is a convolution of sequences a_i = (-1)^{k-i}/(k-i)! and b_i = i^n / i!. This can be computed in O(k log k) using polynomial multiplication, which is a massive improvement when k is large (e.g., k=10^5) and n is also large. This technique is standard in competitive programming for problems requiring many Stirling values.

Another optimization is precomputing factorials and inverse factorials for the explicit formula, reducing each query to O(k). For DP, using Python's array('object') or list of ints with local variable binding can speed up inner loops by 30-40%. For very large n with small k, the formula S(n,k) ≈ k^n / k! for large n provides an approximation, useful in probabilistic analysis. Caching the entire triangle up to max_n across multiple queries amortizes cost: after O(N^2) preprocessing, each S(n,k) query becomes O(1).

Choosing the Right Variant

If your problem involves unlabeled groups where order within groups does not matter, use S(n,k). If order matters within groups, consider Lah numbers. If groups are labeled (e.g., k distinct servers), the count is k! * S(n,k) or k^n with inclusion-exclusion for onto functions. For permutations and cycle analysis, use c(n,k). Understanding these distinctions prevents off-by-factorial errors, a common pitfall. The unsigned first kind c(n,k) is always positive, while the signed version alternates, which matters for polynomial expansions.

For memory optimization, the 1D DP array trick works because computing row i only needs row i-1. The update must be done carefully to avoid overwriting needed values: iterate j from k down to 1 when using a single array in-place, or use two arrays as shown in the optimized code. When computing Bell numbers iteratively, the Bell triangle method uses O(n) space and O(n^2) time with simple additions, avoiding multiplications altogether.

7. Real-World Applications

Despite their abstract combinatorial definition, stirling numbers appear in surprisingly concrete engineering systems. In web servers and load balancers, S(n,k) counts the number of ways to distribute n distinct requests among k identical backend instances where each instance must handle at least one request and instances are indistinguishable for counting distinct load distributions. When instances are distinguishable, the count becomes k! * S(n,k), which is the number of onto functions, directly informing capacity planning and collision analysis for consistent hashing.

In databases, stirling numbers model sharding and partitioning strategies. Partitioning n distinct rows into k shards where shard identity does not matter for enumeration (e.g., counting distinct sharding schemes up to permutation) uses S(n,k). They also appear in the analysis of the birthday paradox and hash collisions: the probability that n keys hash into exactly k distinct buckets among m possible buckets involves Stirling numbers. Query optimizer cardinality estimation for GROUP BY operations with k groups from n rows can be bounded using S(n,k).

In networks and distributed systems, clustering algorithms that group n nodes into k clusters for hierarchical routing or leader election have S(n,k) possible configurations. The complexity of enumerating all possible clusterings, or sampling uniformly from them, depends on Stirling numbers. In cryptography, the analysis of S-boxes and the distribution of outputs involves Stirling numbers of the second kind when counting surjective mappings.

Beyond systems, stirling numbers are used in machine learning for non-parametric Bayesian methods like the Chinese Restaurant Process, where customers (data points) are assigned to tables (clusters) with probability proportional to Stirling numbers. In statistical physics, they count microstates of bosons. In software testing, they help estimate the number of equivalence partitions for n inputs into k classes, guiding test case generation.

From Theory to Practice

Consider a microservice architecture with n=20 distinct API endpoints to be grouped into k=5 service boundaries. The number of possible groupings is S(20,5) = 749,206,090,500, a huge search space that justifies heuristic rather than exhaustive search for optimal decomposition. Knowing this magnitude prevents naive brute-force design tools from attempting enumeration and instead motivates clustering algorithms or genetic search.

8. Comparison with Alternatives

Stirling numbers are often confused with other combinatorial numbers, but each counts a distinct structure. Choosing the wrong one leads to over- or under-counting by factorial factors. The table below provides a direct feature comparison to guide selection.

The most common alternative to S(n,k) when counting distributions is to use k^n (all functions) or C(n,k) (choose subsets). However, k^n counts assignments to labeled boxes where empty boxes are allowed, while S(n,k) counts assignments to unlabeled boxes where no box is empty. The relationship is k^n = sum_{k} S(n,k) * (k)! * C(m,k) for m labeled boxes, and the number of onto functions from an n-set to a k-set is k! * S(n,k). Eulerian numbers A(n,k) are similar in that they also form a triangle and sum to n!, but they count descents rather than cycles or subsets, so they are not interchangeable.

Bell numbers are not an alternative but an aggregation of Stirling numbers of the second kind. If you need the total number of partitions without fixing k, use Bell numbers directly via Dobinski's formula or the Bell triangle, which is more efficient than summing S(n,k) individually. Partition numbers p(n,k) are for unlabeled objects (integer partitions), so they are much smaller than S(n,k) and should be used when objects are identical, such as distributing n identical tasks among k identical machines.

For performance-critical code, if you only need S(n,k) modulo a prime and k is up to 10^5, the convolution-based O(k log k) method beats O(n*k) DP. If n and k are both up to 5000 and you need many queries, precomputing the full DP table once is optimal. Always profile with realistic n and k before optimizing.

9. Common Mistakes and Best Practices

One of the most frequent mistakes is confusing labeled versus unlabeled structures. S(n,k) assumes subsets are unlabeled; if your servers, shards, or buckets are distinguishable, you must multiply by k! to get k! * S(n,k). Forgetting this factor undercounts by a huge margin—for n=10, k=3, S(10,3)=9330 but k!*S=55980. Conversely, using S(n,k) when objects are identical (e.g., partitioning integer n) overcounts; there you need integer partition numbers p(n,k). Always ask: are objects distinct? Are groups distinct? Is empty allowed?

Another pitfall is off-by-one errors in base cases. S(0,0)=1 is essential for recurrences to work, but many implementations incorrectly return 0. Similarly, S(n,0)=0 for n>0 and S(n,k)=0 for k>n must be handled explicitly to avoid index errors. When implementing DP, ensure loops run to min(i,k) to avoid accessing dp[i-1][j] where j>i-1. For the first kind, mixing signed and unsigned versions causes sign errors; document which variant your function returns.

Integer overflow and performance issues are common in Python when not using modulo. S(100,50) is enormous and will slow down big integer arithmetic. If the problem statement says "return answer modulo 10^9+7", apply modulo at each addition and multiplication inside the DP loop, not just at the end. Also, recursion depth can exceed Python's default 1000 for n>1000; prefer iterative DP to avoid RecursionError. Use sys.setrecursionlimit only as a last resort.

Best Practices Checklist

• Validate inputs: return 0 if k > n or k < 0 or n < 0, handle n=0,k=0 as 1.
• Choose algorithm by constraints: DP for n,k < 2000, explicit formula for small k, convolution for large k modulo prime.
• Use space optimization: O(k) array for single queries, O(n*k) table only if you need random access to many values.
• Precompute factorials and inv factorials when using explicit formula repeatedly.
• Write tests with known values: S(4,2)=7, S(5,3)=25, S(6,3)=90, c(4,2)=11, B(5)=52.
• Document whether you return signed or unsigned first kind, and whether result is modulo or exact.
• For interview settings, start with memoized recursion to show understanding, then optimize to bottom-up DP and discuss trade-offs.

Finally, avoid recomputing the triangle for each query. If you have multiple queries up to max_n, precompute once. Use lru_cache for recursive implementations to make repeated calls O(1). Profile memory: a 5001x5001 int table in Python uses over 200MB due to Python object overhead; use array('l') or numpy for large tables, or the O(k) method.

10. Interview Questions

Stirling numbers appear in algorithm interviews, especially for combinatorial reasoning and DP. Below are common questions with solution sketches to help you prepare.

Q1: How many ways can n distinct balls be placed into k identical boxes with no empty box?

This is the definition of S(n,k). Expected answer: S(n,k) = k*S(n-1,k)+S(n-1,k-1) with base S(0,0)=1. Follow-up: what if boxes are distinct? Answer: k! * S(n,k), the number of onto functions. Follow-up: what if empty boxes allowed? Answer: sum_{i=0}^{k} S(n,i) * C(k,i) * i! or Bell-like sum, or use inclusion-exclusion. Interviewers test whether you distinguish labeled vs unlabeled.

Q2: Implement a function to compute S(n,k) modulo 10^9+7 for n up to 10^9 and k up to 10^5.

Here O(n*k) DP is impossible. You must use the explicit formula S(n,k)=1/k! * sum_{i=0}^{k} (-1)^{k-i} C(k,i) i^n with fast exponentiation O(log n) per term, total O(k log n). Precompute factorials and inv factorials up to k in O(k), then compute the sum as a convolution if needed for speed. Mention using Fermat's little theorem for modular inverses when mod is prime. This tests knowledge of optimizations beyond naive DP.

Q3: What is the relationship between Stirling numbers and Bell numbers? Compute B(n).

Answer: B(n)=sum_{k=0}^{n} S(n,k). Provide O(n^2) DP using Bell triangle: start with 1, then each row is built by Bell's recurrence. Alternatively, use Dobinski's formula B(n)=1/e * sum_{k=0}^\infty k^n/k! for approximation. Implementation: use DP for S(n,k) and sum, or use Bell triangle which is more efficient: bell[0]=1, for n from 1..N: bell[n]=sum_{k=0}^{n-1} C(n-1,k) bell[k]. This shows understanding of aggregation.

Q4: Explain the difference between Stirling numbers of the first and second kind with examples.

Expected: Second kind partitions sets into subsets (e.g., S(4,2)=7 ways to split {a,b,c,d} into 2 groups). First kind (unsigned) partitions permutations into cycles (e.g., c(4,2)=11 permutations of 4 with 2 cycles). Provide recurrences and note orthogonality. Bonus: mention signed version s(n,k)=(-1)^{n-k}c(n,k) and its role in falling factorial expansion. This tests conceptual clarity.

Q5: Prove that S(n,2) = 2^{n-1} -1.

Proof sketch: Number of ways to partition n labeled elements into 2 non-empty unlabeled subsets equals (2^n -2)/2 =2^{n-1}-1. Reason: each element chooses one of 2 subsets (2^n assignments), subtract 2 assignments where all elements in one subset, divide by 2 because subsets are unlabeled (swap). Alternatively, prove by induction using recurrence S(n,2)=2*S(n-1,2)+1 with base S(2,2)=1. This tests ability to derive closed forms and use combinatorial double counting.

Preparing these questions with code and proofs demonstrates both theoretical depth and practical implementation skill, which is exactly what interviewers look for when asking about stirling numbers.