Kombinatorische Bestimmung der Anzahl von Relationen in einer Menge M mit n Elementen, die nicht Relation über M sind, d.h. für die gilt,

Voraussetzung: Bekannt sei, daß die Anzahl aller Relationen in einer Menge M mit n Elementen gleich der Anzahl aller Teilmengen in der Menge M×M ist.  Die Menge   M×M ist die Menge aller Paare mit Elementen in M und hat n*n Elemente. Also

Weiter benutzen wir noch die Tatsache, daß eine nichtleere Relation halt nur entweder Relation über, oder nicht Relation über sein kann.

Wir benutzen einen rekursiven Ansatz. (Der induktive Beweis der Formel ist eine gute Übung (!) und dem Studenten überlassen :-). Der Anfang ist noch leicht:

Hier kommt der Rekursionsschritt. Jede Relation, die keine Relation über (ganz M) ist, ist eine Relation über genau einer echten Teilmenge von M. Wir zählen die echten Teilmengen T  von M mit 0,1,...,n-1 Elementen auf (dies geht mit der Binomialfunktion) und für jede dieser Teilmenge T wissen wir, wieviele Relationen über  T es gibt, da T eine Menge mit weniger als n Elementen ist.

Die Ausgabe in Form einer hübschen Tabelle, ist etwas mühsam zu programmieren, aber es geht: