Anwendung Inklusions-Exklusionsprinzip

Neue Frage »

inkex Auf diesen Beitrag antworten »
Anwendung Inklusions-Exklusionsprinzip
Kurzfassung: Wie wende ich hier das Inklusions-Exklusionsprinzip an bzw. wie definiere ich mir am besten die Mengen aus dem setting des Inklusions-Exklusionsprinzips?

Langfassung:
Angenommen es gibt 21 Möglichkeiten ein Objekt mit dem Farbvorrat bestehend aus den Farben Rot, Grün und Blau einzufärben (mit "Farbvorrat" ist gemeint, dass nicht alle 3 Farben verwendet werden müssen, sondern auch nur 1 oder 2 der 3 Farben verwendet werden können). Und angenommen es gibt 6 Möglichkeiten für jeden der Farbvorräte Rot+Grün bzw. Rot+Blau bzw. Grün+Blau).

Ich möchte Folgendes bestimmen:
(a) Anzahl der Möglichkeiten, sodass alle 3 Farben verwenden werden
(b) Anzahl der Möglichkeiten, sodass mindestens 2 Farben verwendet werden

Die richtigen Ergebnisse sind 6 bei (a) und 18 bei (b). Also die Lösung ist mir bekannt, mir geht's wirklich nur um den Weg dorthin.

Ich hatte mir definiert
A... Menge aller Färbungen wo der Farbvorrat nur aus Rot besteht
B... Menge aller Färbungen wo der Farbvorrat nur aus Grün besteht
C... Menge aller Färbungen wo der Farbvorrat nur aus Blau besteht

=>


(hier ist mir klar, dass irgendetwas mit meiner Definition der Mengen nicht so ganz passt, weil und somit kann nicht mehr Elemente als enthalten


und dann mit dem Inklusions-Exklusionsprinzips: Also das Ergebnis würde wenigstens passen, aber meine Mengen sind "falsch". Wie macht man es richtig?

Hier das Setting des Satzes:

[attach]54232[/attach]
klauss Auf diesen Beitrag antworten »
RE: Anwendung Inklusions-Exklusionsprinzip
Ich fände es hilfreich zu wissen, wie jenes Objekt aussieht und wie es gefärbt wird, damit man sich überhaupt etwas darunter vorstellen kann.
inkex Auf diesen Beitrag antworten »

[attach]54235[/attach]

Die Lösung dieser Aufgabe ist 21. Und wenn der Farbvorrat aus nur 2 Farben besteht, dann ist die Lösung jeweils 6. (6 für rot+grün, 6 für rot+blau und 6 für grün+blau)

(a) und (b) sind jetzt "Zusatzaufgaben" die allein mit dem Inklusions-Exklusionsprinzip lösbar sein sollten wobei für (a) 6 herauskommen sollte und für (b) sollte 18 herauskommen
klauss Auf diesen Beitrag antworten »
RE: Anwendung Inklusions-Exklusionsprinzip
Danke, diese Informationen sind natürlich schon wesentlich, da die von Dir eingangs genannten Zahlen nur verständlich werden, wenn man weiß, dass es sich um 4 Felder handelt und bestimmte Belegungen ausgeschlossen werden.
Ist jetzt eigentlich ursprünglich ein etwas spezielleres Problem (mit Satz von Pòlya hatte ich bisher nicht zu tun), aber die Zusatzaufgabe ist hoffentlich dennoch machbar.
Nach meinem Verständnis setzen die möglichen Färbungen sich so zusammen:

[attach]54237[/attach]

(Das Bild bestätigt auch die Lösungen, wenn der Farbvorrat nur aus 2 Farben besteht)

Die Gesamtanzahl

soll gemäß Siebformel resultieren aus

Dann scheinen mir Deine Mengen tatsächlich falsch zu sein, denn z. B. ist nicht die Anzahl der Färbungen, in denen nur Rot vorkommt, sondern die Anzahl der Färbungen, in denen Rot vorkommt, also 1 für einfarbig Rot, je 4 zusammen mit Grün oder Blau und 6 zusammen mit Grün und Blau.
Dadurch erhalte ich


Ich habe es auch noch ohne das Verbot von Drehungen/Spiegelungen allgemeiner durchgerechnet mit

[attach]54238[/attach]

Müßten dann insgesamt 81 Möglichkeiten sein.
HAL 9000 Auf diesen Beitrag antworten »
RE: Anwendung Inklusions-Exklusionsprinzip
Ok, sagen wir Farben.

- Ohne Drehung/Spiegelung gibt es Färbungen.

- Unter den Drehungen +-90 Grad sind jeweils genau Färbungen invariant.

- Unter der Drehung 180 Grad sind genau Färbungen invariant.

- Unter zwei der Spiegelungen (Spiegelungsachse = Trenndiagonale) sind genau Färbungen invariant.

- Unter den zwei restlichen Spiegelungen (Spiegelungsachse != Trenndiagonale) sind genau Färbungen invariant.

Macht summa summarum nach Satz von Polya (hier genügt der Spezialfall Lemma von Burnside) genau Färbungen. Speziell ist und .
inkex Auf diesen Beitrag antworten »
RE: Anwendung Inklusions-Exklusionsprinzip
Zitat:
Original von HAL 9000
Ok, sagen wir Farben.

- Ohne Drehung/Spiegelung gibt es Färbungen.

- Unter den Drehungen +-90 Grad sind jeweils genau Färbungen invariant.

- Unter der Drehung 180 Grad sind genau Färbungen invariant.

- Unter zwei der Spiegelungen (Spiegelungsachse = Trenndiagonale) sind genau Färbungen invariant.

- Unter den zwei restlichen Spiegelungen (Spiegelungsachse != Trenndiagonale) sind genau Färbungen invariant.

Macht summa summarum nach Satz von Polya (hier genügt der Spezialfall Lemma von Burnside) genau Färbungen. Speziell ist und .


Das stimmt, aber das ist doch nicht das was ich in (a) und (b) ausrechnen möchte.
Der Satz von Polya sagt uns, dass es g(3)=21 Färbungen mit 1 bis 3 Farben gibt und g(2)=6 Färbungen mit 1 bis 2 Farben gibt.

Ich möchte aber die Anzahl der Färbungen mit (a) genau 3 Farben und (b) mindestens 2 Farben.

Ich habe es jetzt so:
A...Menge der Färbungen mit Farbvorrat r+g
B...Menge der Färbungen mit Farbvorrat r+b
C...Menge der Färbungen mit Farbvorrat g+b

=> und
Also mit dem Prinzip von Inklusion und Exklusion erhalte ich für (a):


Wie bestimme ich jetzt die Anzahl der Färbungen mit genau 2 Farben? ? Das sollte stimmen aber bin mir nicht sicher.

Und eine Zusatzfrage (diesmal 4 Farben): Wie würde ich die Anzahl der Färbungen mit genau 3 von 4 Farben bestimmen, wenn ich g(1), g(2), g(3), g(4) wüsste? Ich weiß nicht, welche Möglichkeiten man hier voneinander subtrahieren bzw addieren muss.

Danke!
 
 
HAL 9000 Auf diesen Beitrag antworten »

Da im Eröffnungsbeitrag nichts zu dem "Objekt" stand, welches hier eingefärbt wird, habe ich den Beitrag gleich komplett links liegen lassen und mich nur auf den Scan konzentriert. Augenzwinkern

(a) Für "genau 3" hat man nun Anzahl

(b) Für "mindestes 2" hat man nun Anzahl .
inkex Auf diesen Beitrag antworten »

Und zu meiner Zusatzfrage aus meinem vorigen Beitrag, wenn wir 4 Farben hätten und an "genau 4" interessiert wären?
Ich hätte folgendes, aber ich glaube beim Term subtrahiere ich manche Möglichkeiten doppelt und daher stimmt das nicht ganz oder?

Für "genau 4 von 4" hat man
HAL 9000 Auf diesen Beitrag antworten »

Gehen wir mal besser zum Inklusions-Exklusions-Prinzip zurück:

Sei die Menge aller Färbungen mit Farben und A_ die Teilmenge der Färbungen ohne Farbe . Dann ist die Menge aller Färbungen, wo alle Farben auch tatsächlich vertreten sind (also "genau n" Farben in der Färbung), und die Anzahl ist dann




Bei wäre das

Bei kommt man dann auf

Da fragt man sich natürlich: Geht das nicht auch einfacher? Allerdings:

Wir haben vier Farben auf vier Feldern, da muss jede der vier Farben genau einmal vertreten sein!

1.Fall: 2 ist benachbart zu 1, da gibt es dann noch die zwei Varianten 34 und 43 für die zwei Restfelder.
2.Fall: 2 liegt 1 gegenüber, da gibt es nur noch eine Zuordnungsmöglichkeit (der Spiegelung wegen).

Macht in der Tat 2+1=3 Möglichkeiten.


P.S.: Konsequenterweise bekommt man übrigens für n=5 die Rechnung . smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »