Inzidenzrelation/n-elementige Menge/Relationsanzahl/Aufgabe/Kommentar

Bei einer Relation ist es wichtig, sich zuerst klar zu machen, was die beteiligten Mengen sind, und insbesondere, ob es sich um eine Relation auf einer Menge oder eine Relation auf zwei Mengen handelt, und wie dann die Paare grundsätzlich aussehen, bevor man schaut, welche davon zur Relation gehören und welche nicht. Bei der Inzidenzrelation geht es um zwei Mengen, nämlich um eine Menge ${}M$ und ihre Potenzmenge ${}{\mathfrak {P}}\,(M)$. Die Inzidenzrelation ist also eine Teilmenge von

$M\times {\mathfrak {P}}\,(M)$

(es gibt also zwar eine Beziehung zwicshen den beiden Mengen, sie sind aber nicht gleich). Es geht also um Paare der Form

$(x,T),$

wobei ${}x$ ein Element von ${}M$ und ${}T$ eine Teilmenge von ${}M$ ist. Die Definition der Inzidenzrelation ist dann sehr einfach, es geht einfach darum, ob ${}x$ zu ${}T$ gehört oder nicht. Wenn ${}M=\{a,b,c\}$ ist, so gehören beispielsweise die Paare

$(a,\{a\}),\,(a,\{a,b\}),\,(a,\{a,c\}),\,(a,\{a,b,c\}),\,(b,,\{a,b,c\}),\,...$

dazu, aber ${}(a,\{b,c\})$ nicht. Wir hatten gesagt, dass die Potenzmenge die Menge der Parties ist, die mit einer gegebenen Menge an Leuten gefeiert werden kann, wobei eine Party nur durch die teilnehmenden Leute festgelegt sei. Diese Interpretation kann man hier erweitern, indem man von Geburtstagsparties mit einem Geburtstagskind spricht. Das Element ${}x$ ist das Geburtstagskind und ${}T$ sind die Teilnehmer, wo ${}x$ dazugehört.

Wie bestimmt man nun die Anzahl der Geburtstagsparties, wenn ${}n$ Leute die Grundmenge bilden? Da gibt es zwei Möglichkeiten. Man kann zuerst das Geburtstagskind ${}x$ fixieren und sich fragen, wie viele Parties es mit diesem Geburtstagskind gibt.

Dies führt auf

$n2^{n-1},$

da die Party ja einer Teilmenge der anderen Leute entspricht.

Oder man kann zuerst die teilnehmenden Leute fixieren und dann ein Geburtstagskind davon bestimmen. Dies führt auf

$\sum _{k=1}^{n}k{\binom {n}{k}}.$

Welches stimmt?

Zur kommentierten Aufgabe