0 Daumen
1,7k Aufrufe

Aufgabe:

Sei A eine nicht leere, endliche Menge. Eine Abbildung f heißt 2-Färbung von A, wenn sie jedem Element von A eine von zwei Farben zuweist.
Zeigen Sie mittels vollständiger Induktion, dass es \( 2^{|A| } \) verschiedene 2-Färbungen von A gibt


Problem/Ansatz:

könnte mir jemand mit dem Bewis helfen?

danke im Voraus für eure Hilfe.

Avatar von

Eine 2-Färbung von A mit |A|=n liegt vor, nachdem k aus n ausgewählt wurden und eine Farbe erhalten haben.(Die restlichen Elemente haben dann automatisch die zweite Farbe). Es geht also  um die Summe aller \( \begin{pmatrix} n\\k \end{pmatrix} \) mit k von 0 bis n. Dass diese Summe 2n ist, wurde schon so oft bewiesen, dass man sich fragt, was hier noch zu beweisen sei.

2 Antworten

+1 Daumen
 
Beste Antwort

Für |A|=1 ist es wohl klar. Dem einzigen Element wird entweder die eine oder

die eine ( z.B. rot) oder die andere (z.B. blau) Farbe zugeordnet.

Es ginbt also zwei = 2^0 Abbildungen

f1: A → {rot, blau}  ; f1(a) = rot

und

f2: A → {rot, blau}  ; f2(a) = blau.

Gilt nun die Aussage für alle Mengen X mit |X|=n    #

und sei nun A eine n+1 elementige Menge.

Dann ist A nicht leer und enthält also ein Element a.

Und A \ {a} ist eine n-elementige Menge.

Sei nun f eine 2-Färbung von A, dann ist die Einschränkung

von f auf  A \ {a}  eine 2-Färbung von  A \ {a} .

Es gibt also gemäß # genau 2^n verschiedene

Einschränkungen von f auf  A \ {a}.

Und f entsteht aus einer solchen Einschränkung entweder

durch f(a) = rot oder durch f(a)=blau.

Also ist die Anzahl der Möglichkeiten für f

  2^n * 2 = 2^(n+1) .   Also gilt die Aussage auch

für (n+1) - elementige Mengen.   q.e.d.

Avatar von 287 k 🚀

Könntest du bitte nur zeigen wo IA IV IS sind bzw. wo sollen geschrieben werden oder wenn es einfacher wäre, füge bitte dein Klmmentar hier hinzu und schreib die an der richtige Stellen wenn es möglich wäre.danke schön

IA: 

Für |A|=1 ist es wohl klar. Dem einzigen Element wird entweder die eine oder

die eine ( z.B. rot) oder die andere (z.B. blau) Farbe zugeordnet.

Es ginbt also zwei = 20 Abbildungen

f1: A → {rot, blau}  ; f1(a) = rot

und

f2: A → {rot, blau}  ; f2(a) = blau.

 IV :  Gilt nun die Aussage für alle Mengen X mit |X|=n    #

IS : Rest!

Die Methode der vollst. Ind. musst du aber wohl noch was üben !

+1 Daumen

Ind.Anf.: Eine Menge mit einem Element kann in jeder der beiden Farben gefärbt werden, also auf 21 verschiedene Arten.

Ind.Vorr.: Eine Menge mit n Elementen kann auf 2n verschiedene Arten gefärbt werden.

Ind.Bew.: Ein neu hinzukommendes Element kann jede der beiden Farben haben. Die Anzahl der Färbungen verdoppelt sich also.

Avatar von 123 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community