Surjektive Tupel und die Einschluss-Ausschluss-Formel

Der Leser wird sich sich vielleicht gefragt haben, warum wir injektive, aber keine surjektiven Tupel betrachtet haben. In der Tat ist die Frage sehr natürlich, da zum Beispiel die Wahrscheinlichkeit, dass bei einem zehnfachen Wurf mit einem fairen Würfel alle Augen 1, …, 6 mindestens einmal fallen, die Zählung von surjektiven Tupeln erfordert. Wir entwickeln hierzu ein nützliches allgemeines kombinatorisches Zählprinzip. Für endliche Mengen gilt:

|A₁ ∪ A₂| = |A₁| + |A₂| − |A₁ ∩ A₂|,

\|A₁ ∪ A₂ ∪ A₃\| =	+ \|A₁\| + \|A₂\| + \|A₃\|
	− \|A₁ ∩ A₂\| − \|A₂ ∩ A₃\| − \|A₁ ∩ A₃\|
	+ \|A₁ ∩ A₂ ∩ A₃\|.

Die erste Formel können wir so begründen: Addieren wir die Mächtigkeiten von A₁ und A₂, so werden die Elemente im Schnitt doppelt gezählt, sodass wir ihre Anzahl abziehen müssen. Die zweite Formel für drei Mengen lässt sich ähnlich einsehen, indem wir die doppelt bzw. dreifach gezählten Elemente betrachten:

In A ∪ B ∪ C gibt es einfache, zweifache und dreifache Überdeckungen

Eine allgemeine Formel für n Mengen ist:

Satz (Einschluss-Ausschluss-Formel)

Seien A₁, …, A_n endliche Mengen, und sei A = A₁ ∪ … ∪ A_n. Wir setzen

S(I) = ⋂_{m  ∈  I} A_m	für alle nichtleeren I ⊆ { 1, …, n },
s(I) = \|S(I)\|	für alle nichtleeren I ⊆ { 1, …, n },
J_i = ℘_i({ 1, …, n })	für alle 1 ≤ i ≤ n.

Dann gilt:

\|A\|	= ∑_{I  ∈  J₁} s(I) − ∑_{I  ∈  J₂} s(I) + ∑_{I  ∈  J₃} s(I) − … + (−1)^n − 1 ∑_{I  ∈  J_n} s(I)
	= ∑_{1 ≤ i ≤ n} (−1)^i − 1 ∑_{I  ∈  J_i} s(I)
	= ∑_{I ⊆ { 1, …, n }, I ≠ ∅} (−1)^\|I\| − 1 s(I).

Das System J₁ besteht aus den einelementigen Mengen { 1 }, …, { n }, sodass die Summe zur Berechnung der Mächtigkeit von A mit

s({ 1 }) + … + s({ n }) = |A₁| + … + |A_n|

beginnt. Wegen J_n = { { 1, …, n } } endet sie mit

s({ 1, …, n }) = |A₁ ∩ … ∩ A_n|.

Die Vorzeichen sind alternierend und zudem durch die Größe der betrachteten Teilmenge I von { 1, …, n } bestimmt.

Ein Beweis der Einschluss-Ausschluss-Formel durch Induktion ist möglich, aber etwas mühsam. Eine Alternative ist ein direktes Argument, bei dem wir nachweisen, dass jedes Element a von A genau 1 zur Summe beiträgt. Hierzu verwenden wir eine geistreiche kombinatorische Summen-Darstellung der 1. Für alle r ≥ 1 gilt nach dem binomischen Lehrsatz

0 = (1 − 1)^r = $( \binom{r}{0} )$ − $( \binom{r}{1} )$ + … + (−1)^r $( \binom{r}{r} )$ .

Der erste Summand auf der rechten Seite ist gleich 1. Durch Umstellung erhalten wir also:

(+) 1 = $( \binom{r}{1} )$ − … + (−1)^r − 1 $( \binom{r}{r} )$ = ∑_{1 ≤ i ≤ r} (−1)^i − 1 $( \binom{r}{i} )$ .

Damit können wir nun die Einschluss-Ausschluss-Formel in einer sehr kompakten Form beweisen.

Beweis

Für alle a  ∈  A sei

r(a) = |{ 1 ≤ m ≤ n | a  ∈  A_m }|

die Anzahl der an der Vereinigung beteiligten Mengen, die a als Element enthalten. Für alle a  ∈  A und i  ∈  { 1, …, n } gibt es genau „i aus r_a“ Teilmengen I von { 1, …, n } der Größe i mit a  ∈  S(I). Damit gilt nach (+)

\|A\|	= ∑_{a  ∈  A} 1
	= ∑_{a  ∈  A} ∑_{1 ≤ i ≤ n} (−1)^i − 1 $( \binom{r_{a}}{i} )$
	= ∑_{a  ∈  A} ∑_{1 ≤ i ≤ n} (−1)^i − 1 ∑_{I  ∈  J_i, a  ∈  S(I)} 1
	= ∑_{1 ≤ i ≤ n} (−1)^i − 1 ∑_{a  ∈  A} ∑_{I  ∈  J_i, a  ∈  S(I)} 1
	= ∑_{1 ≤ i ≤ n} (−1)^i − 1 ∑_{I  ∈  J_i} s(I).

Mit Hilfe der Formel können wir nun surjektive Tupel zählen. Wir definieren hierzu:

Definition (die Tupelmenge T₅)

Seien n, k  ∈  ℕ. Wir setzen:

T₅ = T₅(n, k) = { (a₁, …, a_k)  ∈  T₁ | { a₁, …, a_k } = { 1, …, n } }.

Die Mächtigkeit von T₅ entspricht der Mächtigkeit der Menge aller Surjektionen f : { 1, …, k } → { 1, …, n }. Im Fall n > k ist T₅ leer. Weiter ist T₅(0, 0) = { () } und T₅(0, k) = ∅ für alle k > 0. Ist n = k, so besteht T₅ aus allen Permutationen von { 1, …, n }, sodass |T₅| = n! Allgemein gilt:

Satz (Mächtigkeit der surjektiven Tupel)

Für alle n, k  ∈  ℕ gilt:

|T₅| = ∑_{0 ≤ i ≤ n} (−1)ⁱ $( \binom{n}{i} )$ (n − i)^k.

Der erste Summand der Formel ist n^k. Für k > 0 ist der letzte Summand 0, sodass wir die Summe in diesem Fall verkürzen können.

Beweis

Für alle m = 1, …, n sei

A_m = { (a₁, …, a_k)  ∈  T₁ | m  ∉  { a₁, …, a_k } }

die Menge aller Tupel in T₁, die keinen Eintrag m besitzen. Dann ist

A₁ ∪ … ∪ A_n = T₁ − T₅

die Menge aller nicht surjektiven Tupel. Denn ein Tupel ist genau dann nicht surjektiv, wenn es ein m  ∈  { 1, …, n } gibt, das nicht im Tupel vorkommt. Nach der Einschluss-Ausschluss-Formel gilt mit den dortigen Bezeichnungen

\|T₅\|	= \|T₁\| − \|A₁ ∪ … ∪ A_n\|
	= n^k − ∑_{1 ≤ i ≤ n} (−1)^i − 1 ∑_{I ∈ J_i} s(I)
	= n^k + ∑_{1 ≤ i ≤ n} (−1)ⁱ ∑_{I ∈ J_i} s(I)
	=* n^k + ∑_{1 ≤ i ≤ n} (−1)ⁱ ∑_{I ∈ J_i} (n − i)^k
	= n^k + ∑_{1 ≤ i ≤ n} (−1)ⁱ $( \binom{n}{i} )$ (n − i)^k
	= ∑_{0 ≤ i ≤ n} (−1)ⁱ $( \binom{n}{i} )$ (n − i)^k.

Dabei haben an der Stelle * verwendet, dass

S(I) = ⋂_{m  ∈  I} A_m

die Menge aller k-Tupel in der Menge { 1, …, n } − I ist (kein Element von I kommt im Tupel vor). Für |I| = i ist die Mächtigkeit dieser Menge gleich

s(I) = |T₁(n − i, k)| = (n − i)^k.

Wegen |T₅(n, n)| = n! erhalten wir als Korollar die Formel

n! = ∑_{0 ≤ i ≤ n} (−1)ⁱ $( \binom{n}{i} )$ (n − i)ⁿ für alle n ≥ 0.

Beispiel

Wir wollen uns anhand des Falls k = 10 und n = 6 die Formel für |T₅| noch einmal veranschaulichen. Ein nicht surjektives Tupel (a₁, …, a₁₀) in der Menge { 1, …, 6 } lässt eine der Zahlen 1, …, 6 aus. Es gibt 5¹⁰ Tupel, die die 1 auslassen, …, 5¹⁰ Tupel die die 6 auslassen. Damit ist

6¹⁰ − 6 · 5¹⁰ = 6¹⁰ − $( \binom{6}{1} )$ 5¹⁰

eine erste Approximation an die gesuchte Größe. Wir haben aber zuviel abgezogen, denn es gibt Tupel, die zwei Zahlen auslassen. Da es „2 aus 6“ Möglichkeiten gibt, zwei Zahlen auszulassen, und entsprechende Folgen der Länge 10 an jeder Stelle nur noch 4 statt 6 mögliche Einträge aufweisen, korrigieren wir unsere Approximation zu

6¹⁰ − $( \binom{6}{1} )$ 5¹⁰ + $( \binom{6}{2} )$ 4¹⁰.

Nun haben wir aber zuviel addiert, denn es gibt Tupel, die drei Zahlen auslassen. Damit lautet unsere nächste Approximation

6¹⁰ − $( \binom{6}{1} )$ · 5¹⁰ + $( \binom{6}{2} )$ 4¹⁰ − $( \binom{6}{3} )$ 3¹⁰.

So fortfahrend erhalten wir schließlich die korrekte Anzahl

6¹⁰ − $( \binom{6}{1} )$ · 5¹⁰ + $( \binom{6}{2} )$ 4¹⁰ − $( \binom{6}{3} )$ 3¹⁰ + $( \binom{6}{4} )$ 2¹⁰ − $( \binom{6}{5} )$ 1.

Diese Anzahl berechnet sich zu 16435440. Damit ist zum Beispiel die Wahrscheinlichkeit, bei einem zehnfachen Wurf mit einem fairen Würfel alle Augen 1, …, 6 mindestens einmal zu erhalten, gleich

^|T₅|_6¹⁰ = ^16435440_60466176 ∼ 0,27.

\|A₁ ∪ A₂ ∪ A₃\| =	+ \|A₁\| + \|A₂\| + \|A₃\|
	− \|A₁ ∩ A₂\| − \|A₂ ∩ A₃\| − \|A₁ ∩ A₃\|
	+ \|A₁ ∩ A₂ ∩ A₃\|.

Satz (Einschluss-Ausschluss-Formel)

Beweis

Definition (die Tupelmenge T5)

Satz (Mächtigkeit der surjektiven Tupel)

Beweis

Beispiel

Definition (die Tupelmenge T₅)