Äquivalenzklassen und Kombinatorik. Repräsentantensystem usw Anzahl bestimmen

Question

Aufgabe:

Äquivalenzrelationen und Kombinatorik

(a) Sei \( M=\{1,2,3,4,5,6\} \) und \( X=\left(\begin{array}{c}{M} \\ {3}\end{array}\right) \) die Menge aller 3 -elementigen Teilmengen von \( M . \) Die Aquivalenzrelation \( \sim \subseteq X \times X \) ist wie folgt definiert:
$$ \left\{a_{1}, a_{2}, a_{3}\right\} \sim\left\{b_{1}, b_{2}, b_{3}\right\} \quad \Longleftrightarrow \quad a_{1}+a_{2}+a_{3}=b_{1}+b_{2}+b_{3} $$

Wieviele Äquivalenzklassen hat die Relation \( \sim ? \) Geben Sie ein Repräsentantensystem der Relation an und bestimmen Sie die Äquivalenzklassen \( [\{1,2,5\}]_{\sim} \) und \( [\{1,3,6\}]_{\sim} \)

Hinweis: Überlegen Sie welche Summen sich über 3-elementigen Teilmengen von \( M \) ergeben können.

(b) Wieviele Äquivalenzklassen hat die Relation \( \sim \), wenn man die Menge \( M \) durch die Menge aller Zahlen von 1 bis n ersetzt? Begründen Sie, dass es in diesem Fall mindestens eine Äquivalenzklasse geben muss, in der mindestens \( \left\lceil\frac{n(n-1)}{18}\right\rceil \) Teilmengen von \( X \) liegen.

Answer 1

 

(a) Sei M = {1; 2; 3; 4; 5; 6} und X = (M über 3) die Menge aller 3-elementigen Teilmengen von M. Die Äquivalenzrelation ~ ⊆  X X ist wie folgt definiert: {a1; a2; a3} ~ {b1; b2; b3} ⇔ a1 + a2 + a3 = b1 + b2 + b3

Wieviele Äquivalenzklassen hat die Relation?

Es kommen als Summe alle natürlichen Zahlen von 1+2+3=6       bis 4+5+6=15 vor.

Somit gibt's 10 Äquivalenzklassen

Aufzählung legt dies nahe und ist gleich ein Repräsentantensystem für diese Klassen

1 2 3 Summe 6

1 2 4 Summe 7

1 2 5 Summe 8

1 2 6 Summe 9

1 3 6 Summe 10

1 4 6 Summe 11

1 5 6 Summe 12

2+5+6 Summe 13

3+5+6 Summe 14

4+5+6 Summe 15

Die beiden gesuchten Äquivalenzklassen:   Bitte Klammern… selbst ergänzen und eventuell vergessene Summen von 3 verschiedenen Summanden die die angebene Summe ergeben. Die Folgenden sind alle, die mit einfallen:

Klasse 1:            1 2 5 hat Summe 8 geht auch mit 1 3 4

Klasse 2:             1 3 6 hat Summe 10 geht auch mit 1 4 5,  2 3 5

Geben Sie ein Repräsentanten- system der Relation an und bestimmen Sie die Aquivalenzklassen [  f1; 2; 5g]und [f1; 3; 6g]Hinweis: Uberlegen Sie welche Summen sich  uber 3-elementigen Teilmengen von M ergeben konnen.

(b) Wieviele Aquivalenzklassen hat die Relation  , wenn man die Menge M durchdie Menge aller Zahlen von 1 bis n ersetzt? Begrunden Sie, dass es in diesem Fall mindestens eine Aquivalenzklasse geben muss, in der mindestens n(n-1)/18 Teilmengen von X liegen.

Die Summen können von 1+2+3 = 6 bis (n-2) + (n-1) +n = 3n-3 variieren.

Deshalb gibt es (3n-3) - 6 + 1 = 3n - 8 Äquivalenzklassen.

Probe: Oben war n=6. 3*6 - 8 = 10. ok.

Es gibt n! / (3! (n-3)!) = n(n-1)(n-2)/6    dreielementige Teilmengen von einer Menge mit n Elementen.

Nun teile ich mal diese Zahl durch die Zahl der Äquivalenzklassen  (Schubfachprinzip in mindestens einer von s Schubladen müssen sich x/s der  x Gegenstände befinden)

n(n-1)* (n-2)/(6*(3n -8))

= n(n-1)     * (n-2)/(18n-48) > n(n-1)/18        Ungleichung gilt für n> 8/3 und n muss ja minsdestens 3 sein, da es sich um Mengen nit 3 Elementen handelt.

Beweis der Ungleichung

(n-2)/(18n-48) > 1/18              |*Hauptnenner    n≥ 3

18(n-2) > 18n - 48

18n - 36 > 18n -48

-36 > -48 ok.