Difference between revisions of "Stirling number"
m (→See Also) |
|||
| (One intermediate revision by one other user not shown) | |||
| Line 13: | Line 13: | ||
Stirling numbers of the second kind satisfy the [[recursion]] | Stirling numbers of the second kind satisfy the [[recursion]] | ||
| − | + | <cmath>S(n + 1, k) = k S(n, k) + S(n, k - 1).</cmath> | |
| − | S(n + 1, k) = k S(n, k) + S(n, k - 1). | + | |
| − | |||
(This can easily be shown by considering the cases that <math>n + 1</math> is in a part of size <math>1</math> or size larger than <math>1</math>.) They can also be calculated using the formula | (This can easily be shown by considering the cases that <math>n + 1</math> is in a part of size <math>1</math> or size larger than <math>1</math>.) They can also be calculated using the formula | ||
<cmath> S(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j{k \choose j} (k-j)^n. </cmath> | <cmath> S(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j{k \choose j} (k-j)^n. </cmath> | ||
| Line 23: | Line 22: | ||
== See Also == | == See Also == | ||
| − | [[Category:Combinatorics | + | [[Category:Combinatorics] |
Latest revision as of 23:50, 14 May 2024
There are two kinds of Stirling numbers: Stirling numbers of the first kind and Stirling numbers of the second kind. They appear in many situations in combinatorics.
Stirling Numbers of the First Kind
The Stirling number of the first kind 
is the number of permutations of an 
-element set with exactly 
cycles.
For example, 
because (writing all our permutations in cycle notation) we have the permutations 
.
Stirling Numbers of the Second Kind
The Stirling number of the second kind 
is the number of partitions of an -element set into exactly non-empty subsets.
For example, 
because we have the partitions 
.
Stirling numbers of the second kind satisfy the recursion
![\[S(n + 1, k) = k S(n, k) + S(n, k - 1).\]](http://latex.artofproblemsolving.com/0/d/f/0df8e26c54a0303c038b2e9837fcef6cba8148e0.png)
(This can easily be shown by considering the cases that 
is in a part of size 
or size larger than .) They can also be calculated using the formula
![\[S(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^j{k \choose j} (k-j)^n.\]](http://latex.artofproblemsolving.com/7/9/a/79ac7d5a1d742b3652ad55b4865ae154d44b66d4.png)
The total number of partitions of an -element set is 
and is called the th Bell number.
See Also
[[Category:Combinatorics]
