ZusatzStoffTUB

Aus Online Mathematik Brückenkurs 1

(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
Zeile 43: Zeile 43:
Zusätzliche Definition : <math> 0! := 1 </math>.
Zusätzliche Definition : <math> 0! := 1 </math>.
-
Beispiele:
+
 
-
(1)Möglichkeiten der Anordnung von <math> a, m, b, u </math>?
+
<div class="exempel">
-
<math> 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 </math>
+
''' Beispiel 2'''
-
(2)<math>\dfrac{5!}{3!} = \dfrac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 5 \cdot 4 </math>
+
 
-
(3)<math>\dfrac{(n+1)!}{(n-1)!} = \dfrac {(n+1) n (n-1) (n-2) \cdot ... \cdot 2 \cdot 1}{(n-1)(n-2) \cdot …. \cdot 2 \cdot 1} = (n+1) n </math>
+
<ol type="a">
-
(4)<math>2n! = 2 \cdot n \cdot (n-1) \cdot … \cdot 2 \cdot 1</math>
+
<li>Möglichkeiten der Anordnung von <math> a, m, b, u </math>?
-
<math>(2n)! = 2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot n \cdot (n-1) \cdot ... \cdot 2 \cdot 1 </math>
+
<math> 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24 </math></li>
 +
 
 +
<li><math>\dfrac{5!}{3!} = \dfrac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 5 \cdot 4 </math></li>
 +
 
 +
<li><math>\dfrac{(n+1)!}{(n-1)!} = \dfrac {(n+1) n (n-1) (n-2) \cdot ... \cdot 2 \cdot 1}{(n-1)(n-2) \cdot …. \cdot 2 \cdot 1} = (n+1) n </math></li>
 +
 
 +
<li><math>2n! = 2 \cdot n \cdot (n-1) \cdot … \cdot 2 \cdot 1</math>
 +
<math>(2n)! = 2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot n \cdot (n-1) \cdot ... \cdot 2 \cdot 1 </math></li>
 +
 
 +
</ol>
 +
</div>
Stichproben aus n- elementigen Mengen:
Stichproben aus n- elementigen Mengen:
-
Beispiel 1:
+
<div class="exempel">
 +
''' Beispiel 3'''
 +
 
Wie viele Worte mit 4 Buchstaben kann ich mit den Buchstaben A, R, T, E, N und S bilden? (mit Doppelbenutzung)
Wie viele Worte mit 4 Buchstaben kann ich mit den Buchstaben A, R, T, E, N und S bilden? (mit Doppelbenutzung)
1. Buchstabe 2. Buchstabe 3. Buchstabe 4. Buchstabe
1. Buchstabe 2. Buchstabe 3. Buchstabe 4. Buchstabe
Zeile 59: Zeile 71:
Also gibt es <math> 6 \cdot 6 \cdot 6 \cdot 6 = 6^4 </math> Möglichkeiten.
Also gibt es <math> 6 \cdot 6 \cdot 6 \cdot 6 = 6^4 </math> Möglichkeiten.
 +
 +
</div>
Allgemein:
Allgemein:
Es gibt <math> n^k </math> Möglichkeiten der Anordnung, die beim k- maligen Auswählen aus n Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge entstehen können.
Es gibt <math> n^k </math> Möglichkeiten der Anordnung, die beim k- maligen Auswählen aus n Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge entstehen können.
-
Beispiel 2:
+
<div class="exempel">
 +
''' Beispiel 4'''
 +
 
Wie vorher nur ohne Doppelbenutzung.
Wie vorher nur ohne Doppelbenutzung.
Zeile 72: Zeile 88:
insgesamt: <math> 6 \cdot 5 \cdot 4 \cdot 3 </math> Möglichkeiten.
insgesamt: <math> 6 \cdot 5 \cdot 4 \cdot 3 </math> Möglichkeiten.
<math> 6 \cdot 5 \cdot 4 \cdot 3 = \dfrac{6!}{2!} = \dfrac{6!}{(6-4)!}</math>
<math> 6 \cdot 5 \cdot 4 \cdot 3 = \dfrac{6!}{2!} = \dfrac{6!}{(6-4)!}</math>
 +
 +
</div>
Allgemein:
Allgemein:
-
Es gibt <math> n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) = \dfrac{n!}{(n-k)!} Möglichkeiten aus n Objekten k Stück unter Berücksichtigung der Reihenfolge und ohne Zurücklegen auszusuchen.
+
Es gibt <math> n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) = \dfrac{n!}{(n-k)!} </math> Möglichkeiten aus n Objekten k Stück unter Berücksichtigung der Reihenfolge und ohne Zurücklegen auszusuchen.
 +
 
 +
<div class="exempel">
 +
''' Beispiel 5'''
-
Beispiel 3:
 
„Lotto“ mit Reihenfolge
„Lotto“ mit Reihenfolge
Zeile 83: Zeile 103:
Aber: Die Reihenfolge ist bei echtem Lotto unwichtig. Für sechs feste Zahlen sind 6! Kombinationen in (*) enthalten.
Aber: Die Reihenfolge ist bei echtem Lotto unwichtig. Für sechs feste Zahlen sind 6! Kombinationen in (*) enthalten.
-
Beispiel 4:
+
</div>
 +
 
 +
<div class="exempel">
 +
''' Beispiel 6'''
 +
 
Also: „echtes“ Lotto
Also: „echtes“ Lotto
-
<math> \dfrac{49!}{(49-6)!} \cdot \dfrac{1}{6!} = \dfrac{49!}{(49-6)!6!} = (49 6) \approx 13 \cdot 10^6 </math> Möglichkeiten.
+
<math> \dfrac{49!}{(49-6)!} \cdot \dfrac{1}{6!} = \dfrac{49!}{(49-6)!6!} = \binom{49}{6} \approx 13 \cdot 10^6 </math> Möglichkeiten.
Auswahlmöglichkeiten für k aus n Elementen ohne Zurücklegen und ohne Reihenfolge:
Auswahlmöglichkeiten für k aus n Elementen ohne Zurücklegen und ohne Reihenfolge:
-
<math> (n k) = \dfrac{n!}{(n-k)!k!}</math> „Binomialkoeffizient“
+
<math> \binom{n}{k} = \dfrac{n!}{(n-k)!k!}</math>
 +
 
 +
[[Binomialkoeffizient]]
 +
 
 +
mit <math> n /in N , k /in N , n /ge k </math>
 +
 
 +
</div>
 +
 
 +
Zusammenfassung Urnenmodell:
 +
Das Urnenmodell ist ein allgemeines Beispiel für die Kombinatorik. Hier ist die Idee ein Behältnis mit n Kugeln zu haben aus dem man k mal zieht. Die Beispiele von oben lassen sich durch das Modell und die dazugehörigen Formeln alle rechnen.
 +
 
 +
{| class="wikitable" border="5"
 +
|-
 +
! x
 +
! Mit Zurücklegen
 +
! Ohne Zurücklegen
 +
|-
 +
| Reihenfolge wichtig
 +
| <math> n^k</math>
 +
(Beispiel 1)
 +
| <math> \dfrac{n!}{(n-k)!}</math>
 +
(Beispiel 2)
 +
|-
 +
| Reihenfolge unwichtig
 +
| <math> \binom{n+k-1}{k} </math>
 +
(wird selten gebraucht, hier ist
 +
es aber der Vollständigkeit halber
 +
aufgeführt)
 +
| <math> \binom{n}{k} = \dfrac{n!}{(n-k)!k!}</math>
 +
(Beispiel 4)
 +
|-
 +
|}
 +
 
 +
 
 +
<div class="exempel">
 +
''' Beispiel 7'''
 +
 
 +
Wähle 3 Personen aus 10 aus. Wie viele Möglichkeiten gibt es?
 +
 
 +
Nach Urnenmodell: Ziehe 3 aus 10, ohne Zurück legen und ohne Reihenfolge.
 +
 
 +
Es gilt <math> \binom{10}{3} = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120 </math> Möglichkeiten
 +
</div>
 +
 
 +
<div class="exempel">
 +
''' Beispiel 8'''
 +
 
 +
Wie viele Möglichkeiten gibt es beim Skat spielen 32 Karten auf 3 Spieler (10 Karten) zu und Skat (2 Karten) zu verteilen?
 +
 
 +
Kombinationen f&ume;r den 1.Spieler <math> \cdot </math> Kombinationen f&ume;r den 2. Spieler <math> \cdot </math> Kombinationen f&ume;r den 3. Spieler <math> \cdot </math> Kombinationen f&ume;r den 4. Spieler
 +
<math>= \binom{32}{10} \cdot \binom{22}{10} \cdot \binom{12}{10} \cdot \binom{2}{2} </math>
 +
<math>=\dfrac{32!}{22! \cdot 10!} \cdot \dfrac{22!}{12! \cdot 10!} \cdot \dfrac{12!}{2! \cdot 10!} \cdot \dfrac{2!}{2! \cdot 0!} </math>
 +
<math>=\dfrac{32!}{10! \cdot 10! \cdot 10! \cdot 2!}</math>.
 +
 
 +
(Bemerkung: Es gibt auch noch andere Rechnungen, die auf das gleiche Ergebnis führen.)
 +
</div>
-
mit n /in N , k /in N , n /ge k
+
Es gibt
 +
<math> \dfrac{n!}{k_1! K_2! … k_i!}</math>
 +
Möglichkeiten, n Objekte auf i Gruppen zu verteilen, wobei jede Gruppe <math> k_j</math> Elemente haben soll.
 +
(im Beispiel: n=32, j=4 Gruppen

Version vom 11:06, 30. Sep. 2009

Inhalt:

  • erster Punkt
  • zweiter Punkt
  • dritter Punkt

Lernziele

Nach diesem Abschnitt sollten Sie folgendes können:

  • erstes Ziel
  • zweites Ziel

Kombinatorik

A - Permutationen

Permutationen sind die Möglichkeiten die eine Anordnung von Gegenständen zu Vertauschen, also die Anzahl der Weisen Objekte anzuordnen.

Beispiel 1

\displaystyle \star \diamond \bigcirc
\displaystyle \star \bigcirc \diamond
\displaystyle \diamond \bigcirc \star
\displaystyle \diamond \star \bigcirc
\displaystyle \bigcirc \star \diamond
\displaystyle \bigcirc \diamond \star


Es gibt \displaystyle 3 \cdot 2 \cdot 1 = 3! = 6 (3! = „3 Fakultät“) Möglichkeiten die Objekte anzuordnen. Hierbei gilt, dass für den ersten Gegenstand drei verschiedene Möglichkeiten vorhanden sind, an der zweiten Stelle nur noch zwei und an der dritten dann nur noch eine.

Allgemein: Für eine Gruppe von n Elementen gibt es \displaystyle n! := n (n-1) (n-2) … \cdot 3 \cdot 3 \cdot 2 \cdot 1 Möglichkeiten („n Fakultät“) die Objekte hintereinander anzuordnen (n! Permutationen). Zusätzliche Definition : \displaystyle 0! := 1 .


Beispiel 2

  1. Möglichkeiten der Anordnung von \displaystyle a, m, b, u ? \displaystyle 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24
  2. \displaystyle \dfrac{5!}{3!} = \dfrac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1} = 5 \cdot 4
  3. \displaystyle \dfrac{(n+1)!}{(n-1)!} = \dfrac {(n+1) n (n-1) (n-2) \cdot ... \cdot 2 \cdot 1}{(n-1)(n-2) \cdot …. \cdot 2 \cdot 1} = (n+1) n
  4. \displaystyle 2n! = 2 \cdot n \cdot (n-1) \cdot … \cdot 2 \cdot 1 \displaystyle (2n)! = 2n \cdot (2n-1) \cdot (2n-2) \cdot ... \cdot n \cdot (n-1) \cdot ... \cdot 2 \cdot 1

Stichproben aus n- elementigen Mengen:

Beispiel 3

Wie viele Worte mit 4 Buchstaben kann ich mit den Buchstaben A, R, T, E, N und S bilden? (mit Doppelbenutzung) 1. Buchstabe 2. Buchstabe 3. Buchstabe 4. Buchstabe 6 Möglichkeiten 6 Möglichkeiten 6 Möglichkeiten 6 Möglichkeiten

Also gibt es \displaystyle 6 \cdot 6 \cdot 6 \cdot 6 = 6^4 Möglichkeiten.

Allgemein: Es gibt \displaystyle n^k Möglichkeiten der Anordnung, die beim k- maligen Auswählen aus n Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge entstehen können.

Beispiel 4

Wie vorher nur ohne Doppelbenutzung.

1.Ziehen : 6 Möglichkeiten 2.Ziehen : 5 Möglichkeiten 3.Ziehen : 4 Möglichkeiten 4.Ziehen : 3 Möglichkeiten insgesamt: \displaystyle 6 \cdot 5 \cdot 4 \cdot 3 Möglichkeiten. \displaystyle 6 \cdot 5 \cdot 4 \cdot 3 = \dfrac{6!}{2!} = \dfrac{6!}{(6-4)!}

Allgemein: Es gibt \displaystyle n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) = \dfrac{n!}{(n-k)!} Möglichkeiten aus n Objekten k Stück unter Berücksichtigung der Reihenfolge und ohne Zurücklegen auszusuchen.

Beispiel 5

„Lotto“ mit Reihenfolge

Anzahl der Möglichkeiten: \displaystyle \dfrac{49!}{(49-6)!} = 49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44 \approx 10 \cdot 10^9 (*)

Aber: Die Reihenfolge ist bei echtem Lotto unwichtig. Für sechs feste Zahlen sind 6! Kombinationen in (*) enthalten.

Beispiel 6

Also: „echtes“ Lotto \displaystyle \dfrac{49!}{(49-6)!} \cdot \dfrac{1}{6!} = \dfrac{49!}{(49-6)!6!} = \binom{49}{6} \approx 13 \cdot 10^6 Möglichkeiten.

Auswahlmöglichkeiten für k aus n Elementen ohne Zurücklegen und ohne Reihenfolge:

\displaystyle \binom{n}{k} = \dfrac{n!}{(n-k)!k!}

Binomialkoeffizient

mit \displaystyle n /in N , k /in N , n /ge k

Zusammenfassung Urnenmodell: Das Urnenmodell ist ein allgemeines Beispiel für die Kombinatorik. Hier ist die Idee ein Behältnis mit n Kugeln zu haben aus dem man k mal zieht. Die Beispiele von oben lassen sich durch das Modell und die dazugehörigen Formeln alle rechnen.

x Mit Zurücklegen Ohne Zurücklegen
Reihenfolge wichtig \displaystyle n^k

(Beispiel 1)

\displaystyle \dfrac{n!}{(n-k)!}

(Beispiel 2)

Reihenfolge unwichtig \displaystyle \binom{n+k-1}{k}

(wird selten gebraucht, hier ist es aber der Vollständigkeit halber aufgeführt)

\displaystyle \binom{n}{k} = \dfrac{n!}{(n-k)!k!}

(Beispiel 4)


Beispiel 7

Wähle 3 Personen aus 10 aus. Wie viele Möglichkeiten gibt es?

Nach Urnenmodell: Ziehe 3 aus 10, ohne Zurück legen und ohne Reihenfolge.

Es gilt \displaystyle \binom{10}{3} = \dfrac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120 Möglichkeiten

Beispiel 8

Wie viele Möglichkeiten gibt es beim Skat spielen 32 Karten auf 3 Spieler (10 Karten) zu und Skat (2 Karten) zu verteilen?

Kombinationen f&ume;r den 1.Spieler \displaystyle \cdot Kombinationen f&ume;r den 2. Spieler \displaystyle \cdot Kombinationen f&ume;r den 3. Spieler \displaystyle \cdot Kombinationen f&ume;r den 4. Spieler \displaystyle = \binom{32}{10} \cdot \binom{22}{10} \cdot \binom{12}{10} \cdot \binom{2}{2} \displaystyle =\dfrac{32!}{22! \cdot 10!} \cdot \dfrac{22!}{12! \cdot 10!} \cdot \dfrac{12!}{2! \cdot 10!} \cdot \dfrac{2!}{2! \cdot 0!} \displaystyle =\dfrac{32!}{10! \cdot 10! \cdot 10! \cdot 2!}.

(Bemerkung: Es gibt auch noch andere Rechnungen, die auf das gleiche Ergebnis führen.)

Es gibt \displaystyle \dfrac{n!}{k_1! K_2! … k_i!} Möglichkeiten, n Objekte auf i Gruppen zu verteilen, wobei jede Gruppe \displaystyle k_j Elemente haben soll. (im Beispiel: n=32, j=4 Gruppen

Von „http://wiki.sommarmatte.se/wikis/2009/bridgecourse1-TU-Berlin/index.php/ZusatzStoffTUB“