[Diskrete] Fragen Sammelthread

[YtKM]

halli hallo!

ich habe eine frage in letzter sekunde zu Blatt 3 und den darauf vorhandenen kombinatorik terror:

wie wird das problem mit den 32 bit langen folgen gelöst? gefragt ist ja nach der anzahl der wörter, bei denen 2 bits hintereinander gleich sind.

ist das irgendwie über das inklusions/exkulsions prinzip zu machen? ich habe mich daran versucht, dass wurde aber so kombiliziert (und vor allem lang) das ich angefangen habe zu zweifeln.

wäre sehr cool, wenn ihr uns da helfen könntet.
greetz

Diese Aufgabe ist eigentlich die einfachste auf dem ganzen Blatt.

Man muss sich dabei garnicht so sehr an die Kombinatorik halten, sondern mal kurz überlegen, welche Fälle überhaupt eintreten können. Dann merkt man ganz schnell, dass es nur zwei Fälle gibt, bei denen nicht irgendwo 2 Bits hintereinander kommen.
1) 0101010101...
2) 1010101010...

Die Berechnung aller möglichen Bitfolgen sollte klar sein. Ziehen mit zurücklegen mit Reihenfolge aus einer 2 elementigen Menge.

2^32, nun musst du nur die anderen beiden abziehen.

2^32-2

edit: erneut zu langsam...

[dr.code]

oh yieah - manchmal sollte man sich auch mal nicht dumm anstellen

vielen dank!

[Chrizzo]

noch von Seite 4:

aber warum teilt man durch 2^6 und subtrahiert nicht wie bei anderen Aufgaben?

[Chrizzo]

[Relationen von der vorherigen Seite]

grad versucht die Anzahl von Relationen auf einer vier elementigen Menge per Stirlingzahlen zu errechnen, schein aber zu doof zu sein ^^ (siehe auch Übung 2 Aufg. 3.2)

[Miss*Sunflower]

aus 'nem anderen Thread dazu:

Hi!

m=97. Das Element 13 hat die Ordnung 96. Was ist die Ordnung von 13^14?


So, anscheinend geht das ganz einfach per Rechnung:

96/ggT(14,96) = 48

ist ein bissel einfacher so

Ich wollte wissen, wie man darauf kommt. So kann ich mir die Lösung einfacher merken.

Du suchst mit gegeben. (Hier: x = 13, y=14). Du weißt, dass 13 die Ordnung 96 hat. also suchst du das k, mit folgender Eigenschaft: bzw. allgemein "bekannte Ordnung" teilt y*k. Das kansnt du umstellen: (allgemein: kgV("gegebener Ordnung",y)). Wie das kgV berechnet wird wurde hier ja schon irgendwo erwähnt. Du stellst die Gleichung um und teilst das kgV durch y und schon haste die Ordnung raus.

Ich hoffe das ist allgemein genug?!

[LonliLokli]

Ich hoffe das ist allgemein genug?!

Dies ist mir klar, ganau aus dieser Überlegung habe ich nach der Umwandlung in ggT gefragt, denn ggT kann ich irgendwie leichter berechnen.

Jetzt eine Allgemeine Frage: Hier scheinen alle auf Kombinatorik und Mod.Arithmetik fixiert zu sein. Aber die schrftliche Aufgaben aus dem 5.Übungsblatt sind für mich viel schwierige (genauer gesagt, in der Klausur werde ich die gar nicht anfangen zu machen)

[totte]

Dies ist mir klar, ganau aus dieser Überlegung habe ich nach der Umwandlung in ggT gefragt, denn ggT kann ich irgendwie leichter berechnen.

einfach wikipedia befragen

[skip]

wenn mich nicht alles täuscht bestimmst man die anzahl der surj. abbildungen wie folgt:

da nach der menge der permutationen gefragt ist, muss man erst diese bestimmen, in unserem fall 3! = 6.
Jetzt überlegt man sich, wie man diese 6 gefunden Elemente in der Defintionsmenge auf die 2 Elemente der Wertemenge abbilden kann.
Alle möglichen Abbildungen wären 2^6. da sind aber 2 abbildungen drin die man nicht beachten darf, da vorgegeben ist, das die abbildungen surjektiv sind.
nun muss man die abbildungen die nicht surjektiv sind abziehen, das sind genau 2. nämlich die, die ausschließlich auf 1 oder auf -1 abbilden.
macht 2^6-2 zum ergebnis.

Ich berechne normalerweise die Anzahl der surjektiven Abbildungen wie folgt:
A-->B
Im folgenden Beziehe ich mich immer auf die Kardinalität der Mengen.
Wenn B>A, dann ist die Anzahl 0, da einfach nicht jedes Element getroffen werden kann.

Ist B<=A, gilt folgendes:
Für jedes Element b aus B, gibt es min. 1 Element a aus A.
D.h. man muss die Menge A in B Teilmengen partitionieren.
Um die Anzahl der verschiedenen k-Partitionen einer Menge zu berechnen haben wir die Stirlingformel 2. Art.
Nun beinhalten die Partitionen nicht die Reihenfolge der Elemente. Man muss also S_(A,B) noch mit A! multiplizieren.

Ist dieses Vorgehen richtig?

nochmal kurz ne eigene frage nachschieben: kann mir vllt mal jemand schritt für schritt erklären warum a/b = 1 eine Äquivalenzrelation ist? ich komm da nicht hinter. das die relation reflexiv ist seh ich ein, symetrisch denke ich auch, aber transitiv?

mfg barelli

Also ich meine, dass das Vorgehen mit den Stirlingzahlen richtig ist, und das mit den Permutationen falsch.
Aus der Menge {1,2,3}nach gibts * 2! = 3*2=6 Möglichkeitnen,

Nach
1 __ -1

1 + 2,3
1,2 + 3
1,3 + 2
2,3 + 1
1,2 + 3
1,3 + 2

Wir Partitionieren zuerst die Menge 1,2,3, es gibt Partitionen. Die erste partition bilden wir immer auf 1 ab, die 2te auf -1.

Danach machen wirs umgekehrt. Die erste partition bilden wir immer auf -1 ab, die 2te auf 1. Wir Permutieren also die Menge {1,-1} und bilden die Partitionen von {1,2,3]der Reihe nach ab.

Sollte mir jemand 62 surjektive Abbildungen aufzaehlen koennen so macht das bitte.

[Miss*Sunflower]

Dies ist mir klar, ganau aus dieser Überlegung habe ich nach der Umwandlung in ggT gefragt, denn ggT kann ich irgendwie leichter berechnen.

einfach wikipedia befragen

oder auch Thread lesen http://www.infostudium.de/viewtopic.php?p=30913&highlight=#30913

[skip]

damn, auf den Schmarn mit der führenden "0" bin ich garnet gekommen, ist was dran ^^ dann ergibt die Rechnung natürlich Sinn, dankö
aber warum teilt man durch 2^6 und subtrahiert nicht wie bei anderen Aufgaben?

Chrizzo stell dir vor, wir stellen die 6 Studenten mit je 2 Vortraegen als einen String dar, zB. 1123234554
Jede Ziffer x an Stelle y bedeutet dass Student x an Stelle y seinen Vortrag haelt.

Es gibt fuer Vortraege so viele Möglichkeiten, wie es solche Strings gibt.

Von diesem String gibts (6*2)! viele Permutationen.
Wenn wir aber zB die 1en vertauschen, aendert sich der String nicht. Das kommt daher, weil wir die 1en nicht unterscheiden koennen.
Darum teilen wir durch 2!*2!*2!*2!*2!*2! weil wir die 1en,2en,3en,4en,5en,6en nicht unterscheiden in diesem String.

[skip]

ok, nu aber wirklich die aller letzte Frage meinerseits xD

Wieviele Möglichkeiten gibt es, aus fünf Sorten Bier eine Kiste mit zwanzig
Flaschen zu kaufen? ((5+20-1) über 20, warum kommts hier nicht auf die Reichenfolge an?)

hier kann man wieder eine kodierung zum Verstaendniss nutzen.
Es ist wichtig hier, wieviele Flaschen wir von jeder Sorte haben, und nicht in welcher Reihenfolge.

Den Inhalt der Flasche koennen wir binaer Kodieren mit.

11 0 111 0 1 00 11

Das bedeutet:
2 Flaschen der 1 Sorte
3 Flaschen der 2 Sorte
1 Flaschen der 2 Sorte
0 Flaschen der 2 Sorte
2 Flaschen der 2 Sorte

Fuer kodierung brauchen wir 20 einsen (20 Bierflaschen)
und 4 Nullen (Trennung der 5 Partitionen, weil 5 Sorten).

Von diesem String gibts (20+4)! Permutationen,
wir unterscheiden aber die 20 Einsen und 4 Nullen nicht, deswegen teilen wir durch 20!*4!

Insgesamt 24!/20!*4! unterscheidbare Strings und Möglichkeiten die Kiste zu fuellen.

[dr.code]

eine frage habe ich noch ganz am ende:

bei aufgabe 5b blatt 7:

wie funktioniert der beweis in etwa? was sind die tricks?

z.z.:

für p prim:

(a+b)^p = a^p+b^p (mod p)

thx

[dr.code]

ah jo:

ich sehe gerade, dass ja beim aufschreiben der binomialkoeffizienten da sowas steht wie


n! / [ (n-k)! * k! ]

wobei n hier gleich einer primzahl ist

insbesondere lässt sich im bruch nicht der faktor n im zähler kürzen (weil primzahl)

multiplikation eines beliebigen elementes aus dem körper mit diesen n elementen gibt mir stets eine 0.

(im F_5 ist 1*5 = 0, 2*5 = 0, 3*5=0, 4*5 = 0, 0*0=0)

und damit machen dann alle binomialkoeffizienten ne null aus dem zu addierenden term - AUßER:

n über n = 1 (kann man kürzen)
n über 0 = 1 (kann man kürzen)

also ist dann (a+b)^p = a^p+b^p


ich hoffe das ist es