Es gibt eine Bijektion zwischen F und W

Question

Aufgabe:

Sei n ∈ N, A eine endliche Menge mit |A| = n und Σ := {0, 1}. Sei F die Menge aller 2-Färbungen von A und W die Menge aller Wörter der Länge n über dem Alphabet Σ.
Zeigen Sie: Es gibt eine Bijektion zwischen F und W.

Problem/Ansatz

wie kann man die Bijektion hier zeigen ich habe die Idee dass beide gleich viel Elemente 2^n haben aber ich komme nicht mehr weiter.

Answer 1

Sei A = { a1,a2,a3,...,an} . Dann wird durch eine Zweifärbung Z von A zerlegt in zwei

Teilmengen B und C mit B∩C=∅ und B∪C = A.

Und ist w∈W, dann ist w eine Zeichenkette der Länge n, die

aus den Zeichen c_i ∈{0;1}, i∈{1,...,n} besteht, wobei der Index i die

Position des Zeichens in der Kette angibt.

Nennen wir dann w = (c_i) _{i∈{1,...,n}}

Dann ist eine Bijektion die Abbildung

f : F ---->  W

    Z --------->  w= (c_i) _{i∈{1,...,n}} mit c_i=0 für a_i∈B und c_i=1 sonst.

Comments

  Z --------->  w= (ci) i∈{1,...,n} mit ci=0 für ai∈B und ci=1 sonst

könnten Sie mir bitte erklären,was Sie hier meinen und was ist Z überhaupt.

glauben Sie dass so die Lösung vollstängig ist und kann ich die Lösung so abgeben oder muss ich noch was genauer erklären?

ich bedanke mich im Voraus für Ihre Mühe

---

Steht oben:

Dann wird durch eine Zweifärbung Z von A …….

Das Z ist also eine Zweifärbung, d.h. eine

Einteilung der Menge A in zwei Teilmengen,

die den beiden Farben entsprechen.

Also sagen wir mal bei 6 Elementen

B={a1;a4} und C={a2;a3;a5;a6} würde

bedeuten a1;a4 sind rot und a2;a3;a5;a6

sind blau gefärbt. Dann wird dieser Färbung zugeordnet

das Wort  011011.

---

vielen vielen lieben dank für die vorherige Antwort

könnte ich Sie bitte eine Andere Frage stellen,wenn Sie es beantworten würden,wäre ich Ihnen mega mega dankbar.Ich bin ziemlich sicher dass die Begründung mit Induktion zu lösen ist aber ich komme nicht weiter damit.also in dieser Aufgabe geht um chromatische Zahl.

ich wünsche mir dass Sie mir damit helfen könnten.

---

@mathef

Z --------->  w= ( c_i) was meinst du bitte mit dieser Gleichung

und reicht es zu zeigen dass Z------>w bijektiv ist,um zu zeigen dass f:F----->W ist auch bijektiv?

---

... was meinst du bitte mit dieser Gleichung ?

wie gesagt: Es geht um eine Zuordnung.

Jeder Zweifärbung wird eine Zeichenkette zugeordnet.

Z ist also eine Einteilung der Menge A in zwei Teilmengen,

die den beiden Farben entsprechen.

Also sagen wir mal bei 6 Elementen

B={a1;a4} und C={a2;a3;a5;a6} würde

bedeuten a1;a4 sind rot und a2;a3;a5;a6

sind blau gefärbt. Dann wird dieser Färbung zugeordnet

das Wort  011011.

Und wenn man die Menge aller Zweifärbungen Z und

die Menge aller Zeichenketten der Länge n betrachtet wird

daraus eine Bijektion.