Advanced Combinatorics | Derangements, Bell, Catalan & Stirling Numbers
Compute advanced counting numbers in one place: derangements D(n), Bell numbers B(n), Catalan numbers C(n), Stirling numbers of the second kind S(n,k), multinomial coefficients, and stars-and-bars distributions. Each result includes the definition, step-by-step working, and a real-world application.
Number of permutations of n elements where no element appears in its original position.
What Is the Advanced Combinatorics | Derangements, Bell, Catalan & Stirling Numbers?
Advanced combinatorics counts structured arrangements and partitions. Derangements count permutations where nothing is in its original position — the probability converges to 1/e as n grows. Bell numbers count the total number of ways to partition a set. Catalan numbers count Dyck paths, valid bracket sequences, polygon triangulations, and hundreds of other combinatorial structures. Stirling numbers of the second kind count set partitions into exactly k non-empty unlabeled subsets. Stars-and-bars distributes identical objects into distinct bins.
Formula
Derangements: D(n) = n! · Σ (−1)ᵏ / k!
Bell: B(n) = Σₖ S(n,k) (via Bell triangle)
Catalan: C(n) = (2n)! / ((n+1)! · n!)
Stirling-2: S(n,k) = k·S(n−1,k) + S(n−1,k−1)
Stars & Bars: C(n+k−1, k−1) or C(n−1, k−1)
How to Use
- 1
Click a mode button: Derangements D(n), Bell B(n), Catalan C(n), Stirling S(n,k), Multinomial, or Stars & Bars
- 2
Enter n (all modes) and k (Stirling, Stars & Bars)
- 3
For Multinomial: enter n and the k-values that sum to n (e.g. "2 2 1" for n=5)
- 4
For Stars & Bars: toggle the "each bin non-empty" option
- 5
Click Compute
- 6
View the result and step-by-step working; Bell mode shows the full triangle
Select a mode from the six buttons: Derangements, Bell, Catalan, Stirling, Multinomial, or Stars & Bars. Enter the required parameters n (and k for Stirling/Stars, or k-values for Multinomial). Click Compute. The result appears with step-by-step derivation and Bell's triangle for the Bell number mode.
Example Calculation
Example: Derangements D(4)
D(4) = 4! · (1/0! − 1/1! + 1/2! − 1/3! + 1/4!)
= 24 · (1 − 1 + 0.5 − 0.1667 + 0.0417)
= 24 · 0.375 = 9
9 out of 24 permutations of 4 items have no fixed points.
Frequently Asked Questions
What is the real-world use of derangements?
The hat-check problem: n people check their hats; all hats are returned at random. D(n) is the number of arrangements where no one gets their own hat. As n→∞, the probability D(n)/n! → 1/e ≈ 36.79%. The same formula applies to the problème des ménages and other "no fixed point" scenarios.
What do Catalan numbers count?
The nth Catalan number counts: (1) valid sequences of n pairs of brackets; (2) the number of ways to fully parenthesize n+1 factors; (3) triangulations of a convex (n+2)-gon; (4) Dyck paths (non-crossing lattice paths); and over 200 other combinatorial structures. C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14.
What is the difference between Bell numbers and Stirling numbers?
Stirling numbers of the second kind S(n,k) count the ways to partition an n-element set into exactly k non-empty subsets. Bell numbers B(n) sum over all k: B(n) = S(n,1) + S(n,2) + … + S(n,n). They count the total number of ways to partition the set, regardless of how many subsets are formed.
When do you use Stars and Bars?
Stars and Bars counts the number of ways to distribute n identical objects into k distinct bins. With empty bins allowed: C(n+k−1, k−1). If each bin must have at least 1 item: C(n−1, k−1). Common applications: rolling k dice with sum n, distributing identical candies to k children, integer compositions.
You Might Also Like
Explore 360+ Free Calculators
From math and science to finance and everyday life — all free, no account needed.