Zur Berechnung der Anzahl von Partitionen ist die folgende Rekursionsformel in der Regel besser als die folgenden expliziten Formeln.
Die
Stirling-Zahlen zweiter Art
erfüllen die Rekursionsformel
S
(
n
+
1
,
k
)
=
k
⋅
S
(
n
,
k
)
+
S
(
n
,
k
−
1
)
.
{\displaystyle {}S({n+1},{k})=k\cdot S({n},{k})+S({n},{k-1})\,.}
Es sei
M
{\displaystyle {}M}
(
n
+
1
)
{\displaystyle {}(n+1)}
m
∈
M
{\displaystyle {}m\in M}
N
:=
M
∖
{
m
}
.
{\displaystyle {}N:=M\setminus \{m\}\,.}
Wir teilen die Partitionen von
M
{\displaystyle {}M}
{
m
}
{\displaystyle {}\{m\}}
M
{\displaystyle {}M}
{
m
}
{\displaystyle {}\{m\}}
N
{\displaystyle {}N}
k
−
1
{\displaystyle {}k-1}
M
{\displaystyle {}M}
{
m
}
{\displaystyle {}\{m\}}
m
{\displaystyle {}m}
B
1
,
…
,
B
k
{\displaystyle {}B_{1},\ldots ,B_{k}}
B
1
∩
N
,
…
,
B
k
∩
N
{\displaystyle {}B_{1}\cap N,\ldots ,B_{k}\cap N}
N
{\displaystyle {}N}
k
{\displaystyle {}k}
S
(
n
,
k
)
{\displaystyle {}S({n},{k})}
k
{\displaystyle {}k}
M
{\displaystyle {}M}
m
{\displaystyle {}m}
◻
{\displaystyle \Box }
1
1
1
1
3
1
1
7
6
1
1
15
25
10
1
1
31
90
65
15
1
1
63
301
350
140
21
1
1
127
966
1701
1050
266
28
1
1
255
3025
7770
6951
2646
462
36
1
{\displaystyle {\begin{array}{c}1\\1\quad 1\\1\quad 3\quad 1\\1\quad 7\quad 6\quad 1\\1\quad 15\quad 25\quad 10\quad 1\\1\quad 31\quad 90\quad 65\quad 15\quad 1\\1\quad 63\quad 301\quad 350\quad 140\quad 21\quad 1\\1\quad 127\quad 966\quad 1701\quad 1050\quad 266\quad 28\quad 1\\1\quad 255\quad 3025\quad 7770\quad 6951\quad 2646\quad 462\quad 36\quad 1\\\end{array}}}
Für die
Stirling-Zahlen zweiter Art
gelten die folgenden Beschreibungen.
S
(
n
,
k
)
=
1
k
!
∑
(
r
1
,
…
,
r
k
)
:
r
1
+
r
2
+
⋯
+
r
k
=
n
,
r
j
≥
1
(
n
r
1
,
…
,
r
k
)
.
{\displaystyle {}S({n},{k})={\frac {1}{k!}}\sum _{(r_{1},\ldots ,r_{k}):\,r_{1}+r_{2}+\cdots +r_{k}=n,\,r_{j}\geq 1}{\binom {n}{r_{1},\dotsc ,r_{k}}}\,.}
S
(
n
,
k
)
=
∑
c
1
+
c
2
+
⋯
+
c
k
=
n
−
k
1
c
1
2
c
2
⋯
k
c
k
.
{\displaystyle {}S({n},{k})=\sum _{c_{1}+c_{2}+\cdots +c_{k}=n-k}1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}\,.}
S
(
n
,
k
)
=
∑
1
≤
i
1
≤
i
2
≤
…
≤
i
n
−
k
≤
k
i
1
i
2
⋯
i
n
−
k
.
{\displaystyle {}S({n},{k})=\sum _{1\leq i_{1}\leq i_{2}\leq \ldots \leq i_{n-k}\leq k}i_{1}i_{2}\cdots i_{n-k}\,.}
S
(
n
,
k
)
=
1
k
!
∑
j
=
0
k
(
−
1
)
k
−
j
(
k
j
)
j
n
.
{\displaystyle {}S({n},{k})={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}\,.}
Wir verwenden durchgehend
Fakt ,
das besagt, dass
k
!
S
(
n
,
k
)
{\displaystyle {}k!S({n},{k})}
n
{\displaystyle {}n}
k
{\displaystyle {}k}
Dies folgt aus
Fakt .
Nach
Fakt
ist die Anzahl der surjektiven Abbildungen einer
n
{\displaystyle {}n}
k
{\displaystyle {}k}
∑
(
a
1
,
…
,
a
k
)
:
a
1
+
a
2
+
⋯
+
a
k
=
n
,
a
j
≥
1
1
a
1
2
a
2
⋯
k
a
k
.
{\displaystyle \sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}.}
Wenn man diesen Ausdruck durch
k
!
{\displaystyle {}k!}
c
j
=
a
j
−
1
{\displaystyle {}c_{j}=a_{j}-1}
Dies ergibt sich aus Teil (2). Zu einem Tupel
(
i
1
,
…
,
i
n
−
k
)
{\displaystyle {}(i_{1},\ldots ,i_{n-k})}
c
j
:=
#
(
{
s
∣
i
s
=
j
}
)
{\displaystyle {}c_{j}:={\#\left({\left\{s\mid i_{s}=j\right\}}\right)}\,}
für
j
=
1
,
…
,
k
{\displaystyle {}j=1,\ldots ,k}
(
c
1
,
…
,
c
k
)
{\displaystyle {}(c_{1},\ldots ,c_{k})}
i
t
=
j
{\displaystyle {}i_{t}=j\,}
für
t
{\displaystyle {}t}
c
1
+
⋯
+
c
j
−
1
{\displaystyle {}c_{1}+\cdots +c_{j-1}}
c
1
+
⋯
+
c
j
−
1
+
c
j
{\displaystyle {}c_{1}+\cdots +c_{j-1}+c_{j}}
Dies folgt aus
Fakt .
◻
{\displaystyle \Box }
