Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Abzählungen in Diskreter Mathematik

Abzählungen in Diskreter Mathematik

Universität / Fachhochschule

Binomialkoeffizienten

Differenzengleichungen

Inklusion-Exklusion

Tags: Binomialkoeffizient, Differenzengleichung, Inklusion-Exklusion, Stirling zahlen

anonymous

17:55 Uhr, 01.08.2019

Hallo miteinander :-)

ich hoffe ihr könnt mir bei meinen Aufgaben etwas weiter helfen.

Aufgabe 1: Wie viele Wörter der Länge 7 aus {A;B;C;D;E} gibt es, die keinen der Buchstaben genau 5 mal enthalten?

Lösungsansatz: ich schreibe alle Wörter der Länge 7 auf, auch die mit genau 5 mal (Variation mit wdh). Um die mit genau 5 zu finden, genügt es das für einen Buchstaben zu lösen und dann mal 5 weil 5 Buchstaben. Jetzt klappt aber meine Idee nicht. Ich dachte am Anfang: (Auswahl: ja), (Reihenfolge: unwichtig), (Wiederholung: mit) da die Buchstaben ja öfter dran kommen und es ist ja egal wo welcher Buchstabe steht. Das wäre Kombination mit Wdh.

Zur Rechnung:

n^{k} = 5^{7}

und

(\binom{5 + 7 - 1}{7}) = (\binom{11}{7}) = 330

, 5 = 1650 also wäre mein ergebnis

5^{7} - 1650

Das Ergebnis lautet aber

5^{7} - 1680

, da es 336 und nicht 330 Fälle sind. Wo liegt mein Denkfehler? Anscheinend ist es nicht Kombination mit Wdh. Eine Variation kann es definitiv nicht sein, bleibt also nur Kombination ohne Wdh. aber warum? zB bei dem Buchstaben A, der kommt doch mehrmals vor.

Aufgabe 2: Wie viele natürliche Zahlen von 1 bis 279 sind durch 8 oder durch 12 oder durch 15 teilbar?

Lösungsansatz: Das versuche ich mit Inklusion und Exklusion zu lösen, wie die letze Olympiaaufgabe die ich hier reingestellt hatte. Aber ich hab den dreh irgnwie noch nicht raus.

Aufgabe 3: Geben Sie eine explizite Formel für die durch die Rekursionsgleichung

a_{0} = \frac{1}{3};

a_{1} = 1;

a_{2} = 2;

a_{n} = 3 a_{n - 1} - 3 a_{n - 2} + a_{n - 3}

für n

\leq

3 definierte Folge an.

Lösungsansatz: Ich habe gesehen, dass man zwischen homogenen und inhomogenen Rekursionen unterscheidet und dass man das mit Hilfe der Charakterisierenden Gleichung versucht algorithmisch zu lösen. Ebenfalls sehe ich dann wo anders, dass einfach einige Folgeglieder gebildet werden und dann mittels Differenz an das Problem ran gegangen wird. Ich habe mich and er Aufgabe versucht, habe die NST raus bekommen. Aber es gibt nur die 1. Heißt das, dass es inhimogen ist? Und wie löse ich das? Das habe ich nicht ganz verstanden, oder geht das auch leichter? Die Herangehensweise mit den Folgegliedern (Differenzen) liefert, dass es immer Ein-Drittel weiter "abgezogen" werden. Aber dafür habe ich ja noch keinen geshclossenen Ausdruck.

hilfe :/

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Kombinatorik: Ziehen ohne Reihenfolge und ohne Zurücklegen

ermanus aktiv_icon

18:34 Uhr, 01.08.2019

Hallo,
ich habe das Pech, dass ich mir immer nicht merken kann, was Variationen,
Kombinationen etc. sind (wahrscheinlich bin ich zu bequem dafür).
Betrachten wir die Wörter, die z.B. genau 5-mal A enthalten, also an zwei Stellen
kein A, sondern einen der anderen vier Buchstaben stehen haben.
Für die Verteilung der A's gibt es

(\binom{7}{2}) = 21

Möglichkeiten. Für die beiden
nicht-A-Stellen

4^{2} = 16

Möglichkeiten, also

21 \cdot 16 = 336

, usw. ...
Gruß ermanua

anonymous

18:57 Uhr, 01.08.2019

ok. dh mit n^k bestimme ich alles. dann überlege ich mir was raus muss. alle mit genau 5 gleichen buchstaben. diese bestehen aus 5xA + 2 Restbuchstaben. es gibt dann 2 stellen die nicht A sind: dort gibt es ja dann wieder eine auswahl mit anordnung und wiederholung, deswegen n^k = 4^2. und dann muss ich noch überlegen dass ich die anderen 5 nicht anordne, ok. das hab ich verstanden. danke dir :-)

ermanus aktiv_icon

19:25 Uhr, 01.08.2019

Zur Aufgabe 3:
da die

a_{n}

sich aus ihren Vorgängern als Linearkombination berechnen,
können wir ja die lästigen Nenner zunächst mal loswerden,
indem wir die Folge

{\tilde{a}}_{n} := 3 \cdot a_{n}

betrachten.
Wenn du von dieser Folge die ersten 5 Glieder hinschreibst,
solltest du ein Bildungsgesetz erkennen und dieses dann beweisen ...

anonymous

20:24 Uhr, 01.08.2019

Sei

{\tilde{a}}_{n} := 3 a_{n}

. Dann bekomme ich die Werte wie vorhin, halt ohne den bruch wie du schon sagtest.

\begin{array}{ccccc} n = o & : & 3 a_{0} = 1 \\ n = 1 & : & 3 a_{1} = 3 \\ n = 2 & : & 3 a_{2} = 6 \\ n = 3 & : & 3 a_{3} = 10 \\ n = 4 & : & 3 a_{4} = 15 \end{array}

Man sieht halt direkt was passiert, guter Tipp von dir, danke. Aber den geschlossenen Ausdruck zu finden bereitet mir immer noch etwas Kopfzerbrechen. zB: für n=4 ist 10 = 6 + (3 + 1). wie ich versuche michz ran zu denken:
n=4, das ergebnis 10 ist schon mal kein natürliches vielfaches. also muss irgendwas addiert werden -> (n+1). klar, das ist nicht die lösung, aber durch einsetzen erkennt man hier, dass die Summe von dem Element davor und die erhöhung um 1 fehlt. was muss also noch dazu. addieren geht schon mal nicht mehr, weil das den klammerausdruck verändern würde. also geht nur noch multiplikation. (n+1)(n+1) ist es auch nicht, und wie du siehst wird es eher ein "ratespiel" für mich, anstatt es mit Logik anzugehen und die Lösung zu finden. Wie gehe ich nun am besten vor?

und warum nicht die Algorithmen verwenden? Ist das zu aufwendig?

EDIT: www.sara-adams.de/files/german/rekursion.pdf das hatte ich gefunden. Schau mal (Seite4) 2.1.2 und (Seite 5)2.1.4
wenn ich diese rekursion zu einem polynom umschreibe und die NST anschaue lautet es: (x-1)(x-1)(x-1). und habe da weiter versucht, aber verstanden habe ich noch nicht wie ich auf die Koeffizieten komme.

LG

ermanus aktiv_icon

20:32 Uhr, 01.08.2019

Oh, ich will dich nicht daran hindern, irgendwelche Algorithmen zu verwenden.
Ich habe halt das Problem, dass ich keine diesbezüglichen Algorithmen kenne.
Das liegt daran, dass ich mich eher dürftig mit diskreter Mathematik auskenne :(

Die Folge

1
1+2
1+2+3
1+2+3+4
1+2+3+4+5

sollte dir eigentlich bekannt sein. Die gehört zum Allgemeingut,
vor allem auch die geschlossene Summenformel !!!

anonymous

20:53 Uhr, 01.08.2019

oh man, jetzt wo ich das so sehe, ohne den restlichen kram ... das tut weh :-D) ja das ist natürlich pflichtwissen. oh man. ich sollte mir wohl noch paar Folgen anschauen, und pauken und einprägen.

\sum_{k = 1}^{n} k = 1 + 2 + 3 + 4 + 5 + . . . + n = \frac{n (n + 1)}{2}

und da diese Folge für uns mit

{\tilde{a}}_{n} := 3 a_{n}

, definiert ist, muss ich noch durch 3 teilen und erhalte

\frac{n (n + 1)}{6}

aber wir haben ja auch noch die Null. Hier ist ja erst ab 1, also bezogen auf die Aufgabe. kann da ja nicht die null einsetzen, sonst wird der ausdruck null. dh es muss irgendwas mit (n+1)(n+?) sein, richtig?

ermanus aktiv_icon

21:00 Uhr, 01.08.2019

Der Index fängt ja mit

0

an, daher muss sein

{\tilde{a}}_{n} = \frac{(n + 1) (n + 2)}{2} (*)

und wie du dann richtig schließt,
muss infolgedessen gelten:

a_{n} = \frac{(n + 1) (n + 2)}{6}

Jetzt musst du diese nur nur noch beweisen. Ich würde das
für die Folge

{\tilde{a}}_{n}

machen, also

(*)

beweisen.

HAL9000

21:09 Uhr, 01.08.2019

Zu Aufgabe 2: Inklusion/Exklusion klingt doch gut. Wenn man dann noch beachtet

1) Unter den Zahlen

1 \dots n

sind genau

⌊ \frac{n}{t} ⌋

durch die positive ganze Zahl

t

teilbar, und

2) Eine Zahl ist genau dann durch jede der positive ganzen Zahlen

t_{1}, \dots, t_{m}

teilbar, wenn sie durch

kgV (t_{1}, \dots, t_{m})

teilbar ist,

dann steht der Lösung nichts mehr im Wege.

Und auch noch eine Anmerkung zur "Theorie" von Aufgabe 3:

a_{n} - 3 a_{n - 1} + 3 a_{n - 2} - a_{n - 3} = 0

ist eine homogene lineare Differenzengleichung, aus deren charakteristischer Gleichung

0 = λ^{3} - 3 λ^{2} + 3 λ - 1 = (λ - 1)^{3}

(d.h. Lösung 1 in algebraischer Vielfachheit 3) kann man die allgemeine Lösung

a_{n} = (A n^{2} + B n + C) \cdot 1^{n} = A n^{2} + B n + C

folgern. Die drei Parameter

A, B, C

bekommt man natürlich über die drei gegebenen Startwerte heraus.

> ich habe das Pech, dass ich mir immer nicht merken kann, was Variationen, Kombinationen etc. sind

Vielleicht liegt es daran, dass z.B. im Englischen kein adäquater Begriff zu "Variationen" vorhanden ist ("variations" verwendet kaum einer dafür), stattdessen behilft man sich mit der Benennung "k-permutations of n" für Variationen ohne Wiederholung.

ermanus aktiv_icon

23:13 Uhr, 01.08.2019

@HAL9000: vielen Dank für den "Theorie-Beitrag" :-)
Gruß ermanus

anonymous

23:14 Uhr, 01.08.2019

dh damit wird die Aufgabe ja richtig "leicht" sag ich mal ganz naiv.

∣ A_{8} \cup A_{12} \cup A_{15} ∣ = ∣ A_{8} ∣ + ∣ A_{12} ∣ + ∣ A_{15} ∣ - ∣ A_{8} \cap A_{12} ∣ - ∣ A_{8} \cap A_{15} ∣ - ∣ A_{12} \cap A_{15} ∣ + ∣ A_{8} \cap A_{12} \cap A_{15} ∣

mir war das mit der Abrundungsfunktion gar nicht "aktiv" bewusst. also ich wusste es, konnte es aber nicht ausdrücken. Und im Skript steht natürlich einmal NIX :-D) daher danke an dich HAL9000. und natürlich auch danke an dich ermanus. hab heute ja doch n bisschen was geschafft :-)

=>

∣ A_{8} \cup A_{12} \cup A_{15} ∣ = ∣ A_{8} ∣ + ∣ A_{12} ∣ + ∣ A_{15} ∣ - ∣ A_{8} \cap A_{12} ∣ - ∣ A_{8} \cap A_{15} ∣ - ∣ A_{12} \cap A_{15} ∣ + ∣ A_{8} \cap A_{12} \cap A_{15} ∣

<=>

∣ A_{8} \cup A_{12} \cup A_{15} ∣ = 34 + 23 + 18 - 11 - 2 - 4 + 2

<=>

∣ A_{8} \cup A_{12} \cup A_{15} ∣ = 60

Mit der Theorie zu 3 befasse ich mich morgen noch mal.

HAL9000

09:16 Uhr, 02.08.2019

Ja, so klappt es bei 2), und Endwert 60 ist richtig. Man hätte als Zwischenschritt (die kgV-Anmerkung betreffend) vor dem Einsetzen auch noch

∣ A_{8} \cup A_{12} \cup A_{15} ∣ = ∣ A_{8} ∣ + ∣ A_{12} ∣ + ∣ A_{15} ∣ - ∣ A_{24} ∣ - ∣ A_{120} ∣ - ∣ A_{60} ∣ + ∣ A_{120} ∣

schreiben können.

1477445

1477411

	Status: nicht eingeloggt	Noch nicht registriert?