Fachrat Informatik - Forum

Quoted from "hamena314"

3d) Da hier nur nach ungeraden Zahlen gesucht wird, ist die Spalte überflüssig. Dafür fehlt imho die Spalte mit

Quoted from "vogelj"

Die Spalte a (p=2) kann man sich eigentlich sparen weil sie bei "i ungleich 0" dazu führt das m gerade wird. Aus dem Grund wird i dort immer 0 sein.

Das meinte ich damit. Aber du hast es besser ausgedrückt.

Die Spalte mit 41 habe ich auch direkt weggelassen da ich ja bereits vorher m = 41 nenne (Weil phi(p) = p - 1).
Somit ist phi(41) bereits 40 (andere spalten Ungenutzt) und sobald irgendeine andere Spalte genutzt wird, wäre das Produkt wieder über 40. - Also kann man die Spalte auch direkt weglassen.

Hier meine Lösung zu WS08 3c:


Edit: Habe gerade gesehen dass das gar nicht der Satz von Fermat ist, sondern nur eine Folgerung von diesem und eigentlich der Satz von Euler ist

648 dürfte falsch sein, denn es ist leicht, sich zu überlegen, dass nicht jeder isomorphietyp die gleiche anzahl von möglichen markierungen hat:
Zum Beispiel sind bei Bäumen vom Typ C jeweils 2 Markierungen gleich, da die linken Knoten vertauschbar sind, während bei Typ A sowohl die beiden Knoten in der mitte tauschen können als auch jeweils die beiden Knoten, die zusammen an einem der inneren hängen.

Komme gerade nicht drauf, wie man es berechnet, aber dachte eigentlich, dass wir schon eine Lösung hatten. Ich denke nochmal drüber nach

edit:
Habe jetzt eine Lösung, aber die ist WIRKLICH nicht schön.

Man nehme die Anzahl der markierten Bäume mit 6 Vertizes insgesamt und ziehe die Anzahl der Möglichkeiten für die nicht erwünschten Isomorphietypen ab.
Für jeden Isomorphietyp erhält man 6!/(Anzahl doppelt gezählter Verteiluingen)
Für den Baum, der nur eine Kette ist erhält man hier also 6!/2 , denn man kann die Kette genau spiegeln und hat immer noch die gleiche Belegung.
Für den Baum, der einen Vertex mit Grad 5 enthält erhält man 6!/5! , denn man kann die 5 Vertizes beliebig utnereinander vertauschen (letztlich ggf. auch direkt einfach 6 Möglichkeiten, da schlicht der eine Vertex mit Grad 5 gewählt werden muss udn der Rest beliebig ist.

Für den Baum, der einen Vertex mit Grad 4 hat erhält man 6!/3! , denn die 3 Blätter, die direkt am Vertex mit Grad 4 hängen sind beliebig vertauschbar.

Man erhält also 6^4 - 6!/2 - 6 - 6!/3! = 810



Habe meien Vorgehensweise auch auf Richtigkeit geprüft:

Für die drei Isomorphietypen, die auf dem Blatt gegeben sind erhält man bei
A: 6!/(2*2*2) (erst in der Mitte spiegeln, dann links und rechts jeweils den oberen mit dem utneren vertauschen, beliebige Kombinationen)
B: 6!/2 (oben und unten vertauschen)
C: 6!/2 (oben und utnen vertauschen)

Summiert man alle diese Anzahlen erhält man 6^4=1296.

Ich denke eigentlich, dass es auch noch eine schönere Lösung geben sollte, aber funktionieren tut die hier schonmal


edit 2:


Noch eine Variante:
Ich unterteile in:
1 Vertex mit Grad 3
und
2 Vertizes mit Grad 3

für ersteres ergibt sich:
6* (4 über 2) * 5 * 4.
Denn ich habe 6 Möglichkeiten, mir einen Vertex als denjenigen mit Grad 3 auszuwählen und dann (4 über 2) Möglichkeiten, ihn in meinem Prüfercode zweimal unterzubringen.
Dann "entferne" ich diese Stellen und habe für die erste der übrigen noch 5 Möglichkeiten und für die zweite 4 (da mein Knoten vom Grad 3 nicht mehr vorkommen darf und kein anderer doppelt vorkommen soll).

für zweiteres ergibt sich:
(6 über 2)*(4 über 2)
Denn ich wähle zuerst die beiden Vertizes aus, die Grad 3 haben sollen und wähle dann die beiden Positionen aus, an denen der erste von ihnen stehen soll. Die Positionen des zweiten ergeben sich automatisch.

Diese beiden Terme addiert ergebn ebenfalls 810.



Mit freundlichen Grüßen,
Anselm

Ich denke für Aufgabe 2c der SoSe-Klausur sieht der Rechenweg wie folgt aus:

Für Zykeltyp (2,2,2):
Für Zykeltyp (2,2,1,1):
Für Zykeltyp (2,1,1,1,1):
Für Zykeltyp (1,1,1,1,1,1): ...=1

oder habe ich was falsches berechnet?

Vorweg wieder: DS ist bei mir etwas her & von nem anderen Prof., aber zu dieser Aufgabe kann ich euch hoffentlich helfen:

Quoted from "Bastian"

c)
Wenn man nun b) bewiesen hat, weiß man, dass nur folgende Zykeltypen in Frage kommen: (2, 2, 2), (2, 2, 1, 1), (2, 1, 1, 1, 1) sowie (1, 1, 1, 1, 1, 1).

Für (2, 2, 2) gibt es (6 über 2) * (4 über 2) * (2 über 2) = 15 * 6 * 1 = 90 mögliche Permutationen.
Für (2, 2, 1, 1) gibt es (6 über 2) * (4 über 2) = 15 * 6 = 90 mögliche Permutationen.
Für (2, 1, 1, 1, 1) gibt es (6 über 2) = 15 mögliche Permutationen.
Für (1, 1, 1, 1, 1, 1) gibt es (6 über 6) = 1 mögliche Permutation.

In der Summe ergeben sich 196 mögliche Permutationen.

Quoted from "'SIMPSON"

Ich denke für Aufgabe 2c der SoSe-Klausur sieht der Rechenweg wie folgt aus:

Für Zykeltyp (2,2,2):
Für Zykeltyp (2,2,1,1):
Für Zykeltyp (2,1,1,1,1):
Für Zykeltyp (1,1,1,1,1,1): ...=1

oder habe ich was falsches berechnet?

Aus meiner Sicht sind die Ergebnisse von SIMPSON richtig. Bastian hat nur eine Kleinigkeit bei der Berechnung vergessen, um auf die gleichen Ergebnisse zu kommen.

Quoted

Für (2, 2, 2) gibt es (6 über 2) * (4 über 2) * (2 über 2) = 15 * 6 * 1 = 90 mögliche Permutationen.

Hier gibt es den (Sonder)Fall, dass du Zykel gleicher Größe hast, und zwar 3 Stück. Dieser Sachverhallt muss in die Berechnung mit einfließen und zwar in Form von . , also gleiches Ergebnis wie SIMPSON.

Quoted

Für (2, 2, 1, 1) gibt es (6 über 2) * (4 über 2) = 15 * 6 = 90 mögliche Permutationen.

Hier genau das gleiche. Zur Berechnung hast du die beiden 2er Zykel benutzt, also wieder 2 gleich große Zykel. Dementsprechend kommt in das Produkt noch . , ebenfalls identisch zu SIMPSONS Ergebnis.

Hoffe ich konnte helfen.

Edit: Warum das so ist: die Zykel kann man als Menge betrachten, also ohne Reihenfolge. Ohne das Teilen würde man allerdings "Doppelte" wie z.B. Zykel1=(1,2), Zykel2=(3,4) und Zykel1=(3,4) und Zykel2=(1,2) mitzählen.