Wie viele nicht reflexive Relationen gibt es in [10] x [10]?

Question

und zwar grübel ich da grade etwas länger dran.

Mein Gedankengang: Es gibt 2¹⁰*2⁹⁰=2¹⁰⁰ Relationen. 2¹⁰ für die Paare (a, a) und 2^10*9 für die Paare (a, b) mit a≠b

Das bedeutet es gibt 2⁹⁰ reflexive Relationen. Daraus folgt dann es gibt 2¹⁰⁰-2⁹⁰ nicht reflexive Relationen. Das sind dann 2⁹⁹ und ein paar zerquetschte.

Von der anderen Seit angefangen sieht das so aus: Ich habe 2⁹⁰ Relationen, bei denen kein Paar (a, a) dabei ist. Bei einer nicht reflexiven Relation muss aber nur mindestens ein Paar (a, a) nicht dabei sein. Das bedeutet ja dann, dass ich da dann nochmal 2⁹ Möglichkeiten für die Paare habe, sodass min. eines nicht dabei ist. Multipliziert mit den 2⁹⁰ anderen Relationen kommt man dann auf 2⁹⁹ verschiedene nicht reflexive Relationen.

Das Problem ist: Die paar zerquetschten gehen mir bei der zweiten Herangehensweise ab. Irgendwo muss also ein Fehler sein, nur leider finde ich den nicht. Wäre sehr nett, wenn den jemand sieht :)

Answer 1

Mein Gedankengang: Es gibt 2¹⁰*2⁹⁰=2¹⁰⁰ Relationen. 2¹⁰ für die Paare (a, a) und 2^10*9 für die Paare (a, b) mit a≠b

Präzision: 

Reflexiv: Auf der Hauptdiagonalen gibt es nur Einsen. D.h. 1 Möglichkeit. Daneben gibt es noch 2^90 Möglichkeiten.

Insgesamt gibt es 2^100 Möglichkeiten. 

Nicht reflexiv: 2^100 - 2^{90} = 2^10 * 2^90 - 2^90 = (2^10 - 1)*2^90 

Das bedeutet es gibt 2⁹⁰ reflexive Relationen. Daraus folgt dann es gibt 2¹⁰⁰-2⁹⁰ nicht reflexive Relationen. Das sind dann 2⁹⁹ und ein paar zerquetschte.

Von der anderen Seit angefangen sieht das so aus: Ich habe 2⁹⁰ Relationen, bei denen kein Paar (a, a) dabei ist. Bei einer nicht reflexiven Relation muss aber nur mindestens ein Paar (a, a) nicht dabei sein. Das bedeutet ja dann, dass ich da dann nochmal 2⁹ Möglichkeiten für die Paare habe, sodass min. eines nicht dabei ist. Multipliziert mit den 2⁹⁰ anderen Relationen kommt man dann auf 2⁹⁹ verschiedene nicht reflexive Relationen.

Im roten Satz steckt ein Fehler: 2^10 - 1 ≠ 2^9