Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Stirling number"

(→‎Stirling Numbers of the Second Kind)
m (→‎See Also)
 
(7 intermediate revisions by 4 users not shown)
Line 3: Line 3:
  
 
== Stirling Numbers of the First Kind ==
 
== Stirling Numbers of the First Kind ==
−
The Stirling number of the first kind, <math>S_1(n, k)</math>, is the number of [[permutation]]s of an <math>n</math>-[[element]] [[set]] with exactly <math>k</math> [[cycle of a permutation | cycles]].   
+
The '''Stirling number of the first kind''' <math>c(n, k)</math> is the number of [[permutation]]s of an <math>n</math>-[[element]] [[set]] with exactly <math>k</math> [[cycle of a permutation | cycles]].   
  
−
For example, <math>S_1(4, 2) = 11</math> because (writing all our permutations in [[cycle notation]]) we have the permutations <math>\{(1)(234), (1)(243), (134)(2),(143)(2),(124)(3),(142)(3),(123)(4),(132)(4), (12)(34), (13)(24), (14)(23)\}</math>.
+
For example, <math>c(4, 2) = 11</math> because (writing all our permutations in [[cycle notation]]) we have the permutations <math>\{(1)(234), (1)(243), (134)(2),(143)(2),(124)(3),(142)(3),(123)(4),(132)(4), (12)(34), (13)(24), (14)(23)\}</math>.
  
 
== Stirling Numbers of the Second Kind ==
 
== Stirling Numbers of the Second Kind ==
−
The Stirling number of the second kind, <math>S_2(n, k)</math>, is the number of [[partition]]s of an <math>n</math>-element set into exactly <math>k</math> [[subset]]s.
+
The '''Stirling number of the second kind''' <math>S(n, k)</math> is the number of [[partition]]s of an <math>n</math>-element set into exactly <math>k</math> non-[[empty set |empty]] [[subset]]s.
  
−
For example, <math>S_2(4, 2) = 7</math> because we have the partitions <math>\{1 | 234, 2|134, 3|124, 4|123, 12|34, 13|24, 14|23\}</math>.
+
For example, <math>S(4, 2) = 7</math> because we have the partitions <math>\{1 | 234, 2|134, 3|124, 4|123, 12|34, 13|24, 14|23\}</math>.
  
 +
Stirling numbers of the second kind satisfy the [[recursion]]
 +
<cmath>S(n + 1, k) = k S(n, k) + S(n, k - 1).</cmath>
  
−
They can be calculated using the following 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>
  
 +
The total number of partitions of an <math>n</math>-element set is <math>B_n = \sum_{k = 1}^n S(n, k)</math> and is called the <math>n</math>th [[Bell number]].
  
−
[[Category:Combinatorics]]
+
== See Also ==
 +
 
 +
[[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 $c(n, k)$ is the number of permutations of an $n$-element set with exactly $k$ cycles.

For example, $c(4, 2) = 11$ because (writing all our permutations in cycle notation) we have the permutations $\{(1)(234), (1)(243), (134)(2),(143)(2),(124)(3),(142)(3),(123)(4),(132)(4), (12)(34), (13)(24), (14)(23)\}$.

Stirling Numbers of the Second Kind

The Stirling number of the second kind $S(n, k)$ is the number of partitions of an $n$-element set into exactly $k$ non-empty subsets.

For example, $S(4, 2) = 7$ because we have the partitions $\{1 | 234, 2|134, 3|124, 4|123, 12|34, 13|24, 14|23\}$.

Stirling numbers of the second kind satisfy the recursion \[S(n + 1, k) = k S(n, k) + S(n, k - 1).\]

(This can easily be shown by considering the cases that $n + 1$ is in a part of size $1$ or size larger than $1$.) 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.\]

The total number of partitions of an $n$-element set is $B_n = \sum_{k = 1}^n S(n, k)$ and is called the $n$th Bell number.

See Also

[[Category:Combinatorics]

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Stirling_number&oldid=219341"