Content

5. Trigonometrie und Kombinatorik in:

Michael Merz, Mario V. Wüthrich

Mathematik für Wirtschaftswissenschaftler, page 99 - 116

Die Einführung mit vielen ökonomischen Beispielen

1. Edition 2012, ISBN print: 978-3-8006-4482-7, ISBN online: 978-3-8006-4483-4, https://doi.org/10.15358/9783800644834_99

Bibliographic information
Kapitel5 Trigonometrie und Kombinatorik Kapitel 5 Trigonometrie und Kombinatorik 5.1 Trigonometrie Es existieren verschiedene Möglichkeiten den Sinus, Kosinus, Tangens und Kotangens eines Winkels zu definieren. Im Folgenden wird die anschauliche geometrische Definition in einem kartesischen Koordinatensystem mit einem Kreis um den Ursprung (0, 0) und dem Radius r > 0 bevorzugt (zum Begriff des kartesischen Koordinatensystems siehe Seite 119). Dazu sei ϕ der in Abbildung 5.1 eingezeichnete Winkel im Gradmaß, der seinen Scheitel im Ursprung (0, 0) hat und von den beiden Strecken (0, 0)P und (0, 0)A eingeschlossen wird. Dabei wird – wie in der Mathematik üblich – als positiver Drehsinn die dem Uhrzeigersinn entgegengesetzte Drehrichtung verstanden. Der Winkel ϕ gehört somit zu einem rechtwinkligen Dreieck mit der Ankathete a, der Gegenkathete b und der Hypotenuse r . Definition von Sinus, Kosinus, Tangens und Kotangens Sinus, Kosinus, Tangens und Kotangens des Winkels ϕ im Gradmaß sind durch die folgenden Quotienten definiert: sin(ϕ) : = b r (5.1) cos(ϕ) : = a r (5.2) tan(ϕ) : = sin(ϕ) cos(ϕ) = b a für a = 0 (5.3) cot(ϕ) : = cos(ϕ) sin(ϕ) = a b für b = 0 (5.4) Noch anschaulicher können der Sinus, der Kosinus, der Tangens und der Kotangens des Winkels ϕ im Einheitskreis (d. h. im Kreis mit dem Radius 1 um den Ursprung (0, 0)) dargestellt werden. Die Koordinaten a und b des Punktes P entsprechen dann cos(ϕ) bzw. sin(ϕ) und mit Hilfe des Strahlensatzes erhält man für den Tangens und Kotangens die Werte tan(ϕ) = sin(ϕ) cos(ϕ) = AC 1 = AC bzw. cot(ϕ) = cos(ϕ) sin(ϕ) = BC 1 = BC (vgl. Abbildung 5.2). Offensichtlich resultieren für Winkel ϕ′ im Gradmaß der Form ϕ′ = ϕ + k · 360◦ mit k ∈ Z dieselben Werte für den Sinus, Kosinus, Tangens und Kotangens wie für den Winkel ϕ. b a P (a, b) A 2 r 0 Abb. 5.1: Trigonometrie am Kreis si n ( ) cos( ) ta n ( ) cot( ) P 2 r = 1 0 x A B C Abb. 5.2: Sinus, Kosinus, Tangens und Kotangens am Einheitskreis Während es im täglichen Leben üblich ist, einen Winkel ϕ mittels Gradmaß zu messen, ist es in der Mathematik oftmals praktikabler das Bogenmaß zu verwenden. Dabei misst man die Größe eines Winkels ϕ durch die Länge x des Kreisbogens, den der Winkel ϕ aus der Kreislinie des Einheitskreises schneidet (vgl. Abbildung 5.2). Jedem Winkel ϕ im Gradmaß ist auf diese Weise eindeutig ein Kreisbogen der Länge x zugeordnet, und umgekehrt jedem Kreisbogen der Länge x ein Winkel ϕ im Gradmaß. Insbesondere entspricht die komplette Kreislinie des Einheitskreises mit der Länge 2π dem Winkel 360◦ im Gradmaß. Folglich gilt für die Umrechnung von Grad- in Bogenmaß und umgekehrt die Formel x = ϕ 360◦ 2π bzw. ϕ = x 2π 360◦. (5.5) 88 Kapitel 55.1 Trigonometrie Man definiert daher sin(x) := sin(ϕ), cos(x) := cos(ϕ), tan(x) := tan(ϕ) und cot(x) := cot(ϕ) für alle x = ϕ360◦ 2π ∈ R. Analog zu Winkeln ϕ im Gradmaß resultieren für Winkel x ′ im Bogenmaß der Form x ′ = x + 2kπ mit k ∈ Z für den Sinus, Kosinus, Tangens und Kotangens dieselben Werte wie für den Winkel x. Eigenschaften von Sinus und Kosinus Der folgende Satz fasst wichtige elementare Eigenschaften des Sinus und des Kosinus zusammen. Dabei wird der Winkel im Bogenmaß x angegeben. Mit Hilfe von (5.5) können jedoch diese Gleichungen leicht auch für Winkel ϕ im Gradmaß formuliert werden: Satz 5.1 (Eigenschaften des Sinus und Kosinus) Für alle x ∈ R gilt: a) sin(x), cos(x) ∈ [−1, 1] b) sin2(x)+ cos2(x) = 1 c) sin(−x) = − sin(x) und cos(−x) = cos(x) d) sin(π − x) = sin(x) und cos(π − x) = − cos(x) e) sin ( x ± π2 )=± cos(x) und cos (x ± π2 )=∓ sin(x) f) sin(x + 2kπ) = sin(x) und cos(x + 2kπ) = cos(x) für k ∈ Z g) sin(kπ) = 0 und cos ( π2 + kπ ) = 0 für k ∈ Z h) cos(kπ) = (−1)k und sin ( π2 + kπ ) = (−1)k für k ∈ Z Gradmaß ϕ 0◦ 30◦ 45◦ 60◦ 90◦ 180◦ 270◦ 360◦ Bogenmaß x 0 π6 π 4 π 3 π 2 π 3π 2 2π sin(ϕ) = sin(x) 0 12 12 √ 2 12 √ 3 1 0 −1 0 cos(ϕ) = cos(x) 1 12 √ 3 12 √ 2 12 0 −1 0 1 tan(ϕ) = tan(x) 0 13 √ 3 1 √ 3 − 0 − 0 cot(ϕ) = cot(x) − √3 1 13 √ 3 0 − 0 − Tabelle 5.1: Sinus-, Kosinus-, Tangens- und Kotangenswerte für ausgewählte Grad- und Bogenmaße ϕ bzw. x Beweis: Die Aussagen a)-h) folgen unmittelbar aus der Definition von Sinus und Kosinus und lassen sich leicht aus den Abbildungen 5.1 und 5.2 ablesen. Der folgende Satz fasst wichtige trigonometrische Identitäten für den Sinus und Kosinus zusammen. Satz 5.2 (Trigonometrische Identitäten für Sinus und Kosinus) Für alle x, y ∈ R gilt: a) sin(x + y) = sin(x) cos(y)+ cos(x) sin(y) (Additionstheorem für Sinus) b) cos(x + y) = cos(x) cos(y)− sin(x) sin(y) (Additionstheorem für Kosinus) c) sin(x)+ sin(y) = 2 sin ( x+y2 ) cos ( x−y 2 ) d) sin(x)− sin(y) = 2 cos ( x+y2 ) sin ( x−y 2 ) e) cos(x)+ cos(y) = 2 cos ( x+y2 ) cos ( x−y 2 ) f) cos(x)− cos(y) = −2 sin ( x+y2 ) sin ( x−y 2 ) Beweis: Zu a) und b): Mit der Eulerschen Formel (3.26) in Satz 3.15 erhält man cos(x + y)+ i sin(x + y) = ei(x+y) = eixeiy = (cos(x)+ i sin(x)) (cos(y)+ i sin(y)) = cos(x) cos(y)− sin(x) sin(y) + i( sin(x) cos(y)+ cos(x) sin(y)) und somit insbesondere die Behauptungen a) und b). Zu c) und d): Ersetzt man in a) x durch x+y2 und y durch x−y 2 , dann erhält man sin(x) = sin ( x + y 2 ) cos ( x − y 2 ) + cos ( x + y 2 ) sin ( x − y 2 ) . (5.6) 89 Kapitel 5 Trigonometrie und Kombinatorik Ersetzt man dagegen x durch x+y2 und y durch − x−y2 , dann folgt sin(y) = sin ( x + y 2 ) cos ( −x − y 2 ) + cos ( x + y 2 ) sin ( −x − y 2 ) . (5.7) Zusammen mit Satz 5.1c) erhält man durch Addition und Subtraktion von (5.6) und (5.7) die beiden Identitäten c) bzw. d). Zu e) und f): Ausgehend von der Identität b) zeigt man dies analog zu c) und d). Büste von Pythagoras Der Satz 5.1b) ist ein Spezialfall des Satz des Pythagoras, einem der bekanntesten und fundamentalsten Sätze der gesamten Geometrie. Dieser besagt, dass in einem rechtwinkligen Dreieck die Summe der Flächeninhalte der beiden Kathetenquadrate gleich dem Flächeninhalt des Hypotenusenquadrates ist. Er ist nach dem griechischen Mathematiker und Philosophen Pythagoras von Samos (ca. 570–510 v. Chr.) benannt, der ihn wahrscheinlich als erster bewiesen hat. Für den Satz des Pythagoras existieren mehrere hundert verschiedene Beweise. Er ist damit vermutlich der meistbewiesene mathematische Satz. Auf der Liste der 100 wichtigsten mathematischen Sätze, die 1999 von den Mathematikern Paul und Jack Abad veröffentlicht wurde, befindet sich der Satz des Pythagoras auf einem bemerkenswerten 4. Platz. Im Folgenden wird ein rein geometrischer Beweis für den Satz des Pythagoras vorgestellt. Für eine Verallgemeinerung des Satz des Pythagoras auf beliebige sogenannte n-dimensionale euklidische Räume siehe Satz 7.5. a bc b a c2 a b a2 b2 Abb. 5.3: Satz des Pythagoras geometrisch veranschaulicht Satz 5.3 (Satz des Pythagoras) Für die drei Seiten a, b und c eines rechtwinkligen Dreiecks gilt a2 + b2 = c2. Beweis: Die Abbildung 5.3 zeigt zwei gleichgroße Quadrate mit der Seitenlänge a + b. In diese Quadrate sind jeweils vier gleiche (kongruente) rechtwinklige Dreiecke mit den Seitenlängen a, b (Katheten) und c (Hypotenuse) eingelegt (gelb dargestellt). Während jedoch das linke Quadrat neben diesen vier gleichen rechtwinkligen Dreiecken noch aus einem Quadrat mit der Seitenlänge c besteht (rot), enthält das rechte Quadrat neben den vier gleichen rechtwinkligen Dreiecken noch zwei Quadrate mit der Seitenlänge a (grün) bzw. b (blau). Die Fläche c2 des linken Quadrats ist somit gleich der Summe der Flächen a2 und b2 der beiden rechten Quadrate. Damit gilt c2 = a2 + b2. Der Sinus- und der Kosinussatz sind weitere bedeutende Resultate der Geometrie. Der Sinussatz stellt in einem allgemeinen Dreieck eine Beziehung zwischen den drei Winkeln des Dreiecks und den gegenüberliegenden Seiten her. Er wurde vermutlich erstmals vom persischen Mathematiker und Astronomen Abu Nasr Mansur (ca. 960–1036 n. Chr.) bewiesen. Der Kosinussatz ist dagegen eine Verallgemeinerung des Satzes des Pythagoras, welcher nur für rechtwinklige Dreiecke gilt, auf allgemeine Dreiecke. Der Kosinussatz stellt einen Zusammenhang zwischen den drei Seiten eines Dreiecks und dem Kosinus der Winkel des Dreiecks her. α γ β c ab hc c1 c2 Abb. 5.4: Veranschaulichung des Sinus- und des Kosinussatzes 90 Kapitel 55.1 Trigonometrie Satz 5.4 (Sinus- und Kosinussatz) Für die drei Seiten a, b und c und die drei jeweils gegen- überliegenden Winkel α, β und γ in einem allgemeinen Dreieck gilt: a) Sinussatz sin(α) sin(β) = a b , sin(α) sin(γ ) = a c , sin(β) sin(γ ) = b c und damit insbesondere sin(α) : sin(β) : sin(γ ) = a : b : c. b) Kosinussatz a2 = b2 + c2 − 2bc cos(α) b2 = a2 + c2 − 2ac cos(β) c2 = a2 + b2 − 2ab cos(γ ) Beweis: Zu a): Mit Abbildung 5.4 und der Definition (5.1) erhält man sin(α) = hc b und sin(β) = hc a . Das heißt, es gilt sin(α)sin(β) = ab . Auf dieselbe Weise erhält man sin(α) sin(γ ) = ac und sin(β)sin(γ ) = bc . Daraus folgt sin(α) : sin(β) : sin(γ ) = a : b : c und damit insgesamt auch die Behauptung. Zu b): Mit dem Satz des Pythagoras (siehe Satz 5.3) und der Abbildung 5.4 erhält man b2 = h2c+c21 und h2c = a2−c22. Ferner folgt mit der zweiten binomischen Formel c21 = (c − c2)2 = c2 − 2cc2 + c22. Es gilt somit b2 = h2c + c21 = a2 − c22 + c2 − 2cc2 + c22 = a2 + c2 − 2cc2. Zusammen mit cos(β) = c2 a und c2 = a cos(β) (vgl. (5.2)) impliziert dies jedoch b2 = a2 + c2 − 2cc2 = a2 + c2 − 2ac cos(β). Die beiden anderen Gleichungen zeigt man völlig analog. In einem rechtwinkligen Dreieck ist einer der drei Winkel α, β oder γ gleich 90◦ und somit gilt cos(α) = 0, cos(β) = 0 oder cos(γ ) = 0. Das heißt, für rechtwinklige Dreiecke resultiert aus dem Kosinussatz der Satz des Pythagoras als Spezialfall. Eigenschaften von Tangens und Kotangens Der Tangens und der Kotangens sind im Gegensatz zum Sinus und Kosinus nicht für alle Winkel definiert. Aus den beiden Definitionen (5.3) und (5.4) folgt, dass der Tangens für die Winkel ϕ = (2k + 1)90◦ bzw. x = (2k + 1)π 2 und der Kotangens für die Winkel ϕ = k180◦ bzw. x = kπ mit k ∈ Z nicht definiert ist. Der folgende Satz fasst wichtige elementare Eigenschaften des Tangens und des Kotangens zusammen. Dabei wird der Winkel wieder im Bogenmaß x angegeben. Mit Hilfe von (5.5) können jedoch auch diese Gleichungen leicht für Winkel ϕ im Gradmaß formuliert werden. Satz 5.5 (Eigenschaften des Tangens und Kotangens) Es gilt: a) tan(x) = − tan(−x) für alle x ∈ R mit x = (2k + 1) π2 und k ∈ Z b) cot(x) = − cot(−x) für alle x ∈ R mit x = kπ und k ∈ Z c) tan(x) = tan(x + kπ) für alle k ∈ Z und x ∈ R mit x = (2l + 1) π2 und l ∈ Z d) cot(x) = cot(x + kπ) für alle k ∈ Z und x ∈ R mit x = lπ und l ∈ Z e) tan(x) = 0 für alle x ∈ R mit x = kπ und k ∈ Z f) cot(x) = 0 für alle x ∈ R mit x = (2k + 1) π2 und k ∈ Z Beweis: Zu a) und b): Dies folgt unmittelbar mit Satz 5.1c). Zu c) und d): Mit Satz 5.2 a) und b) folgt sin(x+ (2k+1)π) = − sin(x) und sin(x+2kπ) = sin(x) sowie cos(x+(2k+1)π) = − cos(x) und cos(x+2kπ) = cos(x) für alle x ∈ R und k ∈ Z. Es gilt somit tan(x + kπ) = sin(x + kπ) cos(x + kπ) = sin(x) cos(x) = tan(x) 91 Kapitel 5 Trigonometrie und Kombinatorik für alle k ∈ Z und x ∈ R mit x = (2l + 1) π2 für l ∈ Z und damit auch cot(x + kπ) = 1 tan(x + kπ) = 1 tan(x) = cot(x) für alle k ∈ Z und x ∈ R mit x = lπ für l ∈ Z. Zu e) und f): Dies folgt unmittelbar mit Satz 5.1g). Der folgende Satz fasst wichtige trigonometrische Identitäten für den Tangens und den Kotangens zusammen: Satz 5.6 (Trigonometrische Identitäten für Tangens und Kotangens) Es gilt: a) tan(x + y) = tan(x)+tan(y)1−tan(x) tan(y) für alle x, y ∈ R mit x + y = (2k + 1) π2 und k ∈ Z (Additionstheorem für Tangens) b) cot(x + y) = cot(x) cot(y)−1cot(x)+cot(y) für alle x, y ∈ R mit x + y = kπ und k ∈ Z (Additionstheorem für Kotangens) c) 1+tan2(x) = 1 cos2(x) für alle x ∈ Rmit x = (2k+1) π2 und k ∈ Z d) 1+ cot2(x) = 1 sin2(x) für alle x ∈ R mit x = kπ und k ∈ Z Beweis: Zu a): Mit Satz 5.2a) und b) folgt tan(x + y) = sin(x + y) cos(x + y) = sin(x) cos(y)+ cos(x) sin(y) cos(x) cos(y)− sin(x) sin(y) für alle x, y ∈ R mit x + y = (2k+ 1) π2 und k ∈ Z. Nach Division von Zähler und Nenner durch cos(x) cos(y) folgt daraus die Behauptung tan(x + y) = tan(x)+ tan(y) 1 − tan(x) tan(y) . Zu b) Mit Aussage a) folgt cot(x + y) = 1 tan(x + y) = 1 − tan(x) tan(y) tan(x)+ tan(y) für alle x, y ∈ R mit x + y = kπ für k ∈ Z. Nach Division von Zähler und Nenner durch tan(x) tan(y) folgt daraus die Behauptung cot(x + y) = cot(x) cot(y)− 1 cot(x)+ cot(y) . Zu c) Mit Satz 5.1b) folgt 1 + tan2(x) = 1 + sin 2(x) cos2(x) = cos 2(x)+ sin2(x) cos2(x) = 1 cos2(x) für alle x ∈ R mit x = (2k + 1) π2 für k ∈ Z. Zu d) Der Beweis verläuft analog zu Aussage c). 5.2 Binomialkoeffizienten Für die Kombinatorik und auch für viele andere Bereiche ist die Definition des Binomialkoeffizienten hilfreich: Definition 5.7 (Binomialkoeffizient) Für k, n ∈ N0 mit k ≤ n heißt ( n k ) := n! k!(n− k)! (5.8) Binomialkoeffizient (sprich: „n über k“), wobei n! = n(n− 1) · . . . · 1 die Fakultät von n ist (vgl. (4.21)). Aus der Definition folgt unmittelbar ( n 0 ) = ( n n ) = 1 und ( n 1 ) = ( n n− 1 ) = n. Aus Definition 5.7 lässt sich ferner leicht die Formel ( n k ) = k−1∏ i=0 n− i k − i (5.9) herleiten. Sie ist zur Berechnung von Binomialkoeffizienten besser geeignet als Definition 5.7, da sie oftmals viele Multiplikationen weniger benötigt (vgl. Beispiel 5.9b)). Die Symmetrie- und die Additionsregel sind im Umgang mit Binomialkoeffizienten die beiden wichtigsten Hilfsmittel: Satz 5.8 (Symmetrieregel und Additionsregel) Für k, n ∈ N0 mit k ≤ n gilt: a) ( n k ) = ( n n− k ) (Symmetrieregel) b) ( n+ 1 k + 1 ) = ( n k ) + ( n k + 1 ) (Additionsregel) 92 Kapitel 55.2 Binomialkoeffizienten Beweis: Zu a): Es gilt ( n k ) = n! k!(n− k)! = n! (n− k)!(n− (n− k)!) = ( n n− k ) . Zu b): Es gilt ( n k ) + ( n k + 1 ) = n! k!(n− k)! + n! (k + 1)!(n− (k + 1))! = (k + 1)n! (k + 1)!(n− k)! + ((n+ 1)− (k + 1))n! (k + 1)!((n+ 1)− (k + 1))! = (k + 1)n! (k + 1)!((n+ 1)− (k + 1))! + ((n+ 1)− (k + 1))n! (k + 1)!((n+ 1)− (k + 1))! = (n+ 1)n! (k + 1)!((n+ 1)− (k + 1))! = ( n+ 1 k + 1 ) . Ursprüngliche Version von B. Pascal Die Symmetrie- und die Additionsregel sind für die effiziente Berechnung von Binomialkoeffizienten von unmittelbarer praktischer Bedeutung. Sie können durch das nach dem französischen Mathematiker Blaise Pascal (1623–1662) benannte Pascalsche Dreieck veranschaulicht werden. Aufgrund der Additionsregel ist jeder Eintrag gleich der Summe der beiden unmittelbar über ihm links und rechts stehenden Einträge. Die Symmetrieregel bewirkt, dass das Pascalsche Dreieck achsensymmetrisch ist (siehe Abbildung 5.5). Pascal verwendete sein Dreieck um verschiedene Probleme in der Wahrscheinlichkeitstheorie zu lösen. Beispiel 5.9 a) Für ( 4 2 ) , ( 4 3 ) und ( 5 3 ) erhält man ( 4 2 ) = 4! 2! · 2! = 24 2 · 2 = 6, ( 4 3 ) = 4! 3! · 1! = 24 6 · 1 = 4 und ( 5 3 ) = 5! 3! · 2! = 120 6 · 2 = 10. Das heißt, es gilt ( 5 3 ) = ( 4 2 ) + ( 4 3 ) . b) Für ( 12 5 ) erhält man ( 12 5 ) = 12! 5! · 7! = 479001600 120 · 5040 = 792. Das gleiche Ergebnis – aber mit weniger Multiplikationen – erhält man mit Formel (5.9) ( 12 5 ) = 12 · 11 · 10 · 9 · 8 5 · 4 · 3 · 2 · 1 = 792. c) Mit der Symmetrieregel (vgl. Satz 5.8a)) und der Formel (5.9) erhält man ( 20 17 ) = ( 20 3 ) = 20 · 19 · 18 3 · 2 · 1 = 1140. In der Definition 5.7 wird k, n ∈ N0 und n ≥ k vorausgesetzt. Die Definition des Binomialkoeffizienten kann jedoch wie folgt verallgemeinert werden: Definition 5.10 (Verallgemeinerter Binomialkoeffizient) Für k ∈ Z und α ∈ C heißt ( α k ) := ⎧ ⎪⎪⎨ ⎪⎪⎩ α(α − 1) · . . . · (α − (k − 1)) k! für k > 0 1 für k = 0 0 für k < 0 (5.10) Binomialkoeffizient α über k. Diese Verallgemeinerung stimmt für k, α ∈ N0 undα ≥ k mit der Definition 5.7 überein und wird vor allem in der Analysis benötigt. Das folgende Beispiel zeigt, dass der verallgemeinerte Binomialkoeffizient analog zum gewöhnlichen Binomialkoeffizienten berechnet wird: 93 Kapitel 5 Trigonometrie und Kombinatorik 1 1 1 1 2 + 1 1 3 + 3 + 1 1 4 + 6 + 4 + 1 1 5 + 10 + 10 + 5 + 1 1 6 + 15 + 20 + 15 + 6 + 1 1 7 + 21 + 35 + 35 + 21 + 7 + 1 1 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 1 9 + 36 + 84 + 126 + 126 + 84 + 36 + 9 + 1 1 10 + 45 + 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1 1 11 + 55 + 165 + 330 + 462 + 462 + 330 + 165 + 55 + 11 + 1 1 12 + 66 + 220 + 495 + 792 + 924 + 792 + 495 + 220 + 66 + 12 + 1 1 13 + 78 + 286 + 715 + 1287 + 1716 + 1716 + 1287 + 715 + 286 + 78 + 13 + 1 1 14 + 91 + 364 + 1001 + 2002 + 3003 + 3432 + 3003 + 2002 + 1001 + 364 + 91 + 14 + 1 1 15 + 105 + 455 + 1365 + 3003 + 5005 + 6435 + 6435 + 5005 + 3003 + 1365 + 455 + 105 + 15 + 1 1 16 + 120 + 560 + 1820 + 4368 + 8008 + 11440 + 12870 + 11440 + 8008 + 4368 + 1820 + 560 + 120 + 16 + 1 Abb. 5.5: Veranschaulichung der Binomialkoeffizienten (n k ) im Pascalschen Dreieck für n = 0, 1, . . . , 16 Beispiel 5.11 (Verallgemeinerter Binomialkoeffizient) a) Der verallgemeinerte Binomialkoeffizient ( 3,5 3 ) beträgt ( 3,5 3 ) = 3,5 · 2,5 · 1,5 6 = 13,125. b) Der verallgemeinerte Binomialkoeffizient (−2 3 ) beträgt (−2 3 ) = (−2) · (−3) · (−4) 3! = −4. 5.3 Binomischer Lehrsatz A. G. Kästner Die Bezeichnung Binomialkoeffizient für ( n k ) tauchte bereits in den Arbeiten des deutschen Mathematikers und Dichters Abraham Gotthelf Kästner (1719–1800) auf. Sie hängt eng mit dem Auftauchen der Terme ( n k ) bei der Auflösung von binomischen Ausdrücken der Form (a + b)n zusammen. Denn es gilt: (a + b)0 = 1 = ( 0 0 ) (a + b)1 = a + b = ( 1 0 ) a + ( 1 1 ) b (a + b)2 = a2 + 2ab + b2 = ( 2 0 ) a2 + ( 2 1 ) ab + ( 2 2 ) b2 (a + b)3 = a3 + 3a2b + 3ab2 + b3 = ( 3 0 ) a3 + ( 3 1 ) a2b + ( 3 2 ) ab2 + ( 3 3 ) b3 ... 94 Kapitel 55.4 Kombinatorik Diese Formeln sind Spezialfälle des folgenden Resultats, das als Binomischer Lehrsatz bekannt ist: Satz 5.12 (Binomischer Lehrsatz) Für a, b ∈ R und n ∈ N0 gilt (a + b)n = an + nan−1b + ( n 2 ) an−2b2 + . . .+ nabn−1 + bn = n∑ i=0 ( n i ) an−ibi . (5.11) Beweis: Mit Hilfe von vollständiger Induktion wird bewiesen, dass (5.11) für alle n ∈ N0 gilt. Induktionsanfang: Die Gleichung (5.11) ist für n = 0 richtig, denn in diesem Fall sind beide Seiten der Gleichung gleich 1. Induktionsschritt: Es wird angenommen, dass die Gleichung (5.11) für ein beliebiges n ∈ N0 richtig ist. Dann gilt (a + b)n+1 = (a + b)n(a + b) = ( n∑ i=0 ( n i ) an−ibi ) (a + b) = n∑ i=0 ( n i ) an−i+1bi + n∑ i=0 ( n i ) an−ibi+1 = n∑ i=0 ( n i ) a(n+1)−ibi + n∑ i=0 ( n i ) a(n+1)−(i+1)bi+1 = n∑ i=0 ( n i ) a(n+1)−ibi + n+1∑ i=1 ( n i − 1 ) a(n+1)−ibi = an+1 + n∑ i=1 ( n i ) a(n+1)−ibi + n∑ i=1 ( n i − 1 ) a(n+1)−ibi + bn+1. Daraus folgt mit der Additionsregel von Satz 5.8b) (a + b)n+1 = an+1 + n∑ i=1 ( n+ 1 i ) a(n+1)−ibi + bn+1 = n+1∑ i=0 ( n+ 1 i ) a(n+1)−ibi und damit die Behauptung. Für a = b = 1 erhält man aus (5.11) die nützliche Identität n∑ i=0 ( n i ) = 2n. Die erste und zweite binomische Formel (a + b)2 = a2 + 2ab + b2 bzw. (a − b)2 = a2 − 2ab + b2 (5.12) sind Spezialfälle des Binomischen Lehrsatzes (5.11), die sich für n = 2 ergeben. Diese beiden Formeln lassen sich, wie auch die dritte binomische Formel (a + b)(a − b) = a2 − b2, sehr gut zum schnellen Kopfrechnen einsetzen. Beispiel 5.13 (Kopfrechnen mit binomischen Formeln) Zum Beispiel erhält man mit Hilfe der binomischen Formeln: 542 = (50 + 4)2 = 2500 + 2 · 50 · 4 + 16 = 2916 892 = (100 − 11)2 = 10000 − 2 · 100 · 11 + 121 = 7921 55 · 45 = (50 − 5)(50 + 5) = 2500 − 25 = 2475 Der Binomische Lehrsatz spielt in der Wahrscheinlichkeitsrechnung bei der Untersuchung einer Serie von gleichartigen, unabhängigen und zufallsbehafteten Versuchen, die jeweils nur die beiden Ergebnisse „Erfolg“ oder „Misserfolg“ haben können, eine wichtige Rolle. Durch a = p ∈ [0, 1] und b = 1 − p ist dann die Erfolgs- bzw. die Misserfolgswahrscheinlichkeit gegeben. 5.4 Kombinatorik Bei der Untersuchung vieler ökonomischer und wahrscheinlichkeitstheoretischer Fragestellungen wird man mit dem Problem konfrontiert, dass die Anzahl der verschiedenen Zusammenstellungen zu bestimmen ist, die aus einer gegebenen Auswahl a1 a2 . . . an von n Elementen gebildet werden können. 95 Kapitel 5 Trigonometrie und Kombinatorik G. Pólya Das Teilgebiet der Mathematik, welches sich speziell mit dieser Art von Problemstellungen beschäftigt, wird als Kombinatorik bezeichnet. Zum Beispiel charakterisierte der bedeutende ungarische Kombinatoriker George Pólya (1887–1985) in seinem Lehrbuch „Notes on introductory combinatorics“ die Kombinatorik als das mathematische Teilgebiet, das sich mit der Untersuchung des Abzählens sowie der Existenz und Konstruktion von Konfigurationen beschäftigt. Oft ist für die Kombinatorik auch die prägnante Umschreibung „Kombinatorik ist die Kunst des schnellen Zählens.“ zu hören. In der Kombinatorik lassen sich sechs Arten von Problemstellungen, die sogenannten Grundaufgaben der Kombinatorik, unterscheiden. Diese verschiedenen Problemstellungen resultieren je nachdem, ob bei einer zu bildenden Zusammenstellung von Elementen aus einer gegebenen Auswahl a1 a2 . . . an von n Elementen a) alle n Elemente berücksichtigt werden sollen oder nicht, b) die einzelnen Elemente wiederholt vorkommen dürfen oder nicht und c) die Reihenfolge der Elemente beachtet werden soll oder nicht. Zum Zwecke einer besseren Differenzierung zwischen diesen sechs verschiedenen Problemstellungen haben sich in der Kombinatorik die drei Begriffe Permutation, Variation und Kombination etabliert. Permutationen Man unterscheidet in der Kombinatorik zwischen Permutation mit Wiederholung und Permutation ohne Wiederholung: Definition 5.14 (Permutation mit und ohne Wiederholungen) Eine beliebige Zusammenstellung ai1 ai2 . . . ain von n Elementen aus einer gegebenen Auswahl a1 a2 . . . an von n Elementen heißt Permutation, wenn jedes Element der Auswahl a1 a2 . . . an genau einmal in der Zusammenstellung ai1 ai2 . . . ain vorkommt. Sind alle n Elemente verschieden, dann spricht man genauer von einer Permutation ohne Wiederholungen und die Anzahl dieser Permutationen wird mit P(n) bezeichnet. Sind dagegen nicht alle n Elemente verschieden, sondern lassen sich die n Elemente der Auswahl in k < n verschiedene Gruppen mit jeweils n1, . . . , nk gleichen Elementen einteilen, so dass die Elemente verschiedener Gruppen verschieden sind und∑k j=1 nj = n gilt, dann spricht man von einer Permutation mit Wiederholungen und die Anzahl dieser Permutationen wird mit PWn1,...,nk (n) bezeichnet. Die Berechnung der Anzahl P(n) von Permutationen ohne Wiederholungen einer Auswahl a1 a2 . . . an von n verschiedenen Elementen wird als erste Grundaufgabe der Kombinatorik bezeichnet. Permutationen ohne Wiederholungen Zwei Permutationen ai1 ai2 . . . ain und aj1 aj2 . . . ajn einer Auswahl a1 a2 . . . an von n verschiedenen Elementen unterscheiden sich lediglich durch die Reihenfolge oder Anordnung ihrer n Elemente. Stimmt auch die Reihenfolge überein, dann sind die beiden Permutationen identisch. Zum Beispiel können für eine Auswahl a1 a2 zwei verschiedene Permutationen a1 a2 und a2 a1 (5.13) gebildet werden. Damit gilt P(2) = 2 = 2!. Kommt zu der zweielementigen Auswahl ein drittes Element a3 hinzu, dann kann dies bei jeder der beiden Permutationen in (5.13) an die erste, zweite oder dritte Stelle treten. Für eine Auswahl a1 a2 a3 von drei Elementen a1, a2 und a3 gibt es somit bereits die sechs verschiedenen Permutationen a3 a1 a2, a1 a3 a2, a1 a2 a3, a3 a2 a1, a2 a3 a1, a2 a1 a3. (5.14) 96 Kapitel 55.4 Kombinatorik Demnach gilt P(3) = 3!. Diese Überlegungen legen die Vermutung nahe, dass die Antwort auf die erste Grundaufgabe der Kombinatorik wie folgt lautet: Satz 5.15 (Anzahl P(n) – erste Grundaufgabe der Kombinatorik) Für eine gegebene Auswahl a1 a2 . . . an von n verschiedenen Elementen existieren P(n) = n! verschiedene Permutationen ohne Wiederholungen. Beweis: Im Folgenden wird mit Hilfe von vollständiger Induktion bewiesen, dass die Aussage P(n) = n! für alle n ∈ N gilt. Induktionsanfang: Die Aussage ist offensichtlich für n = 1 wahr, da dann nur eine Permutation existiert. Induktionsschritt: Es wird angenommen, dass die Aussage P(n) = n! für ein beliebiges n ∈ N wahr ist. Wird nun zu der Auswahl a1 a2 . . . an von n verschiedenen Elementen ein (n+1)-tes verschiedenes Element an+1 hinzugenommen, dann kann dies bei jeder der n! existierenden verschiedenen Permutationen der n Elemente an die erste, zweite, dritte, . . . , (n+1)-te Stelle treten. Dies ergibt n!(n+1) = (n+1)! verschiedene Permutationen. Beispiel 5.16 (Permutationen ohne Wiederholungen) a) Bei einem Schwimmwettbewerb mit 8 Bahnen und 8 Schwimmerinnen gibt es P(8) = 8! = 40.320 verschiedene Startanordnungen. b) Ein Vertreter, der an einem Tag sechs Kunden besuchen will, hat P(6) = 6! = 720 verschiedene Möglichkeiten die Reihenfolge festzulegen. Permutationen mit Wiederholungen Wenn die n Elemente einer Auswahl a1 a2 . . . an nicht alle voneinander verschieden sind, dann handelt es sich bei den Permutationen um Permutationen mit Wiederholungen. Die Berechnung der Anzahl PWn1,...,nk (n) von Permutationen mit Wiederholungen einer Auswahl a1 a2 . . . an von n Elementen wird als zweite Grundaufgabe der Kombinatorik bezeichnet. Bei identischer Anzahl n von gegebenen Elementen ist die Anzahl PWn1,...,nk (n) der verschiedenen Permutationen mit Wiederholungen stets kleiner als die Anzahl P(n) von verschiedenen Permutationen ohne Wiederholungen. Denn hat man eine Auswahl a1 a2 . . . an von n verschiedenen Elementen, dann existieren gemäß Satz 5.15 P(n) = n! verschiedene Permutationen ohne Wiederholungen. Sind nun n1 Elemente einander gleich, dann sind alle ursprünglichen Permutationen nicht mehr zu unterscheiden, bei denen nur diese n1 Elemente die Plätze untereinander vertauschen. Dafür gibt es aber jeweils n1! Möglichkeiten. Das heißt, es gibt nur n! n1 ! verschiedene Permutationen mit Wiederholungen. Entsprechend erhält man, dass nur n! n1 !n2 ! verschiedene Permutationen mit Wiederholungen existieren, wenn es eine weitere Gruppe mit n2 einander gleichen Elementen gibt, die sich von den Elementen der ersten Gruppe unterscheiden. Diese Überlegungen legen die Vermutung nahe, dass die Antwort auf die zweite Grundaufgabe der Kombinatorik wie folgt lautet: Satz 5.17 (Anzahl PWn1,...,nk (n) – zweite Grundaufgabe der Kombinatorik) Für eine gegebene Auswahl a1 a2 . . . an von nElementen, die sich in k verschiedene Gruppen von jeweils n1, . . . , nk gleichen Elementen einteilen lassen, so dass die Elemente verschiedener Gruppen verschieden sind und ∑k j=1 nj =n gilt, existieren PWn1,...,nk (n) = n! n1! n2! · · · nk! verschiedene Permutationen mit Wiederholungen. Beweis: Ein Beweis dieses Satzes kann ebenfalls mit Hilfe von vollständiger Induktion erfolgen. Der Satz 5.17 enthält den Satz 5.15 als Spezialfall. Denn bestehen die k verschiedenen Gruppen jeweils aus nur einem Element, dann gilt n1 = n2 = . . . = nk = 1 und mit Satz 5.17 folgt P(n) = PW1,...,1(n) = n! 1! 1! · · · 1! = n!. Einen weiteren wichtigen Spezialfall erhält man aus Satz 5.17, wenn nur zwei verschiedene Gruppen mit m bzw. n−m 97 Kapitel 5 Trigonometrie und Kombinatorik nicht unterscheidbaren Elementen vorliegen. Dann gibt es PWm,n−m(n) = n! m! (n−m)! = ( n m ) verschiedene Permutationen mit Wiederholungen (vgl. Definition 5.7). Beispiel 5.18 (Permutationen mit Wiederholungen) a) Betrachtet werden die Buchstaben des Wortes M A T H E M A T I K. Dann gilt n = 10, nA = 2, nE = 1, nH = 1, nI = 1, nK = 1, nM = 2 und nT = 2. Aus den Buchstaben dieses Wortes können somit – ohne Beachtung des Wortsinns – PW2,1,1,1,1,2,2(10) = 10! 2! 1! 1! 1! 1! 2! 2! = 453.600 verschiedene Wörter gebildet werden. b) Gegeben sei die Auswahl 1 1 1 1 1 2 2 2 2 3 3 3 4 4 5. Dann gilt n = 15, n1 = 5, n2 = 4, n3 = 3, n4 = 2 und n5 = 1. Es gibt somit PW5,4,3,2,1(15) = 15! 5! 4! 3! 2! 1! = 37.837.800 Permutationen mit Wiederholungen. c) Beim Skat werden 32 verschiedene Karten ausgegeben, wobei jeder der drei Spieler 10 Karten erhält und zwei Karten in den „Skat“ wandern. Zur Beantwortung der Frage, wieviele verschiedene Kartenverteilungen beim Skat möglich sind, genügt es zu erkennen, dass es sich hierbei ebenfalls um einen Spezialfall der zweiten Grundaufgabe der Kombinatorik handelt. Es gilt n = 32 und es gibt vier Gruppen mit n1 = n2 = n3 = 10 bzw. n4 = 2 Elementen. Das heißt, es gibt PW10,10,10,2(32) = 32! 10! 10! 10! 2! = 2.753.294.408.504.640 Permutationen mit Wiederholungen bzw. verschiedene Kartenverteilungen beim Skat. In Beispiel 5.26a) wird diese Anzahl auf eine etwas andere Weise ermittelt. Variationen Analog zu Permutationen wird auch bei Variationen zwischen Variation mit Wiederholungen und Variation ohne Wiederholungen unterschieden: Definition 5.19 (Variation mit und ohne Wiederholungen) Eine beliebige Zusammenstellung ai1 ai2 . . . ail von l ≤ n Elementen aus einer gegebenen Auswahl a1 a2 . . . an von n verschiedenen Elementen heißt Variation der Ordnung l, wenn die Reihenfolge bei den l Elementen der Zusammenstellung beachtet wird. Können dabei die n Elemente der gegebenen Auswahl a1 a2 . . . an jeweils maximal nur einmal in der Zusammenstellung ai1 ai2 . . . ail vorkommen, dann spricht man genauer von einer Variation der Ordnung l ohne Wiederholungen und die Anzahl dieser Variationen wird mit V l(n) bezeichnet. Können dagegen die nElemente der gegebenen Auswahl a1 a2 . . . an mehrfach in der Zusammenstellung ai1 ai2 . . . ail vorkommen, dann spricht man von einer Variation der Ordnung l mit Wiederholungen und die Anzahl dieser Variationen wird mit V lW (n) bezeichnet. Anstelle von Variation mit oder ohne Wiederholungen wird in der Literatur auch die Bezeichnung Kombination mit Berücksichtigung der Reihenfolge mit bzw. ohne Wiederholungen verwendet. Die Berechnung der AnzahlV l(n) von Variationen ohne Wiederholungen einer Auswahl a1 a2 . . . an von n verschiedenen Elementen wird als dritte Grundaufgabe der Kombinatorik bezeichnet. Für die Anzahl V l(n) gilt der folgende Satz: Satz 5.20 (Anzahl V l(n) – dritte Grundaufgabe der Kombinatorik) Für eine gegebene Auswahl a1 a2 . . . an von n verschiedenen Elementen existieren V l(n) = n! (n− l)! (5.15) verschiedene Variationen der Ordnung l ohne Wiederholungen. 98 Kapitel 55.4 Kombinatorik Beweis: Im Folgenden wird mit Hilfe von vollständiger Induktion bewiesen, dass die Aussage V l(n) = n! (n−l)! für alle n ∈ N und 1 ≤ l ≤ n gilt. Induktionsanfang: Die Aussage ist offensichtlich für l = 1 wahr. Denn die Variationen der Ordnung 1 sind durch die n Elemente gegeben. Das heißt, es gilt V 1(n) = n! (n−1)! = n. Induktionsschritt: Es wird angenommen, dass die Aussage V l(n) = n! (n−l)! für ein beliebiges 1 ≤ l < n wahr ist. Für eine Variation der Ordnung l+1 ohne Wiederholungen gibt es dann noch (n − l) weitere Elemente, die in der Variation der Ordnung l nicht auftreten. Wird je eines dieser (n − l) Elemente an diese Variationen – ohne Einschränkung der Allgemeinheit – am Ende hinzugefügt, dann resultieren (n− l) Variationen der Ordnung l+1. Wird dies nacheinander für alle V l(n) Variationen durchgeführt, dann erhält man alle Variationen der Ordnung l + 1 ohne Wiederholungen genau einmal. Es gilt somit V l+1(n)=V l(n) · (n− l)= n! (n− l)! · (n− l)= n! (n− (l + 1))! und damit die Behauptung. Bei einer Permutation ohne Wiederholungen handelt es sich offensichtlich um eine spezielle Variation der Ordnung l ohne Wiederholungen, die man für den Fall l = n erhält. Beispiel 5.21 (Variationen ohne Wiederholungen) a) In einem Unternehmen ist die Stelle eines Abteilungsleiters, eines stellvertretenden Abteilungsleiters und eines Teamleiters zu besetzen, wobei für alle drei Stellen dieselben 20 Personen zur Auswahl stehen. Zur Besetzung dieser drei Stellen gibt es somit für die Unternehmensleitung V 3(20) = 20! (20 − 3)! = 20! 17! = 6840 Möglichkeiten. b) Aus den zehn Ziffern 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 sollen dreistellige Zahlen gebildet werden, wobei jede Ziffer nur einmal vorkommen darf und die Null nicht an erster Stelle stehen soll. Da es V 3(10) = 10! (10−3)! = 10! 7! = 720 Möglichkeiten gibt, aus den zehn Ziffern eine dreistellige Zahl zu bilden und V 2(9) = 9! (9−2)! = 9! 7! = 72 von diesen dreistelligen Zahlen mit der Null beginnen, existieren V 3(10)− V 2(9) = 648 dreistellige Zahlen, die nicht mit einer Null beginnen. c) Beim „Zahlenlotto 6 aus 49“ werden aus einer Trommel mit 1 bis 49 durchnummerierten Kugeln nacheinander 6 Kugeln als Gewinnzahlen gezogen (wobei hier von der Zusatzzahl abgesehen wird). Wird bei der Ziehung dieser 6 Kugeln die Ziehungsreihenfolge beachtet, dann gibt es V 6(49) = 49! (49 − 6)! = 49! 43! = 10.068.347.520 Möglichkeiten für den Ziehungsverlauf unter Beachtung der Ziehungsreihenfolge. Die vierte Grundaufgabe der Kombinatorik besteht in der Berechnung der Anzahl V lW (n) von Variationen mit Wiederholungen einer Auswahl a1 a2 . . . an von n verschiedenen Elementen. Für die Anzahl V lW (n) gilt der folgende Satz: Satz 5.22 (Anzahl V lW (n) – vierte Grundaufgabe der Kombinatorik) Für eine gegebene Auswahl a1 a2 . . . an von n verschiedenen Elementen existieren V lW (n) = nl (5.16) verschiedene Variationen der Ordnung l mit Wiederholungen. Beweis: Ein Beweis dieses Satzes kann völlig analog zum Beweis von Satz 5.20 mit Hilfe von vollständiger Induktion nach l erfolgen. Beispiel 5.23 (Variationen mit Wiederholungen) a) Bei der „13er Wette im Fußballtoto“ kann an jedem Wochenende der Fußballsaison für 13 im Voraus bekannte Spielpaarungen ein Tipp abgegeben werden. 99 Kapitel 5 Trigonometrie und Kombinatorik Dazu ist auf dem Tippschein für die 13 Spielpaarungen jeweils eine der drei Möglichkeiten „1“ (für einen Sieg der Heimmannschaft), „0“ (für ein Unentschieden) oder „2“ (für eine Niederlage der Heimmannschaft) anzukreuzen. Es gibt somit V 13W (3) = 313 = 1.594.323 verschiedene Tippreihen. b) Aus den 26 Buchstaben des Alphabets lassen sich – ohne Berücksichtigung des Wortsinns – V lW (26) = 26l verschiedene Wörter mit genau l Buchstaben bilden. Zum Beispiel gibt es 262 = 676 Wörter aus zwei Buchstaben, z. B. xi,rz,bl, 263 = 17.576 Wörter aus drei Buchstaben, z. B. aaa, brz, lwi, und 264 = 456.976 Wörter aus vier Buchstaben, z. B. rwkl, jhiu, hekw. c) Eine Urne enthält sechs verschiedenfarbige Kugeln. Es wird nacheinander zehnmal je eine Kugel entnommen, wobei die gezogene Kugel vor jeder neuen Ziehung wieder in die Urne zurückgelegt wird. Es existieren dann V 10W (6) = 610 = 60.466.176 verschiedene Farbkombinationen, wenn sowohl die Vielfachheit, in der eine Farbe gezogen wird, als auch die Reihenfolge berücksichtigt werden. Kombinationen Die Begriffe Kombination mit Wiederholungen und Kombination ohne Wiederholungen sind wie folgt definiert: Definition 5.24 (Kombination mit und ohne Wiederholungen) Eine beliebige Zusammenstellung ai1 ai2 . . . ail von l ≤ n Elementen aus einer gegebenen Auswahl a1 a2 . . . an von n verschiedenen Elementen heißt Kombination der Ordnung l, wenn die Reihenfolge bei den l Elementen der Zusammenstellung nicht beachtet wird. Können dabei die n Elemente der gegebenen Auswahl a1 a2 . . . an jeweils maximal nur einmal in der Zusammenstellung ai1 ai2 . . . ail vorkommen, dann spricht man genauer von einer Kombination der Ordnung l ohne Wiederholungen und die Anzahl dieser Kombinationen wird mit Kl(n) bezeichnet. Können dagegen die n Elemente der gegebenen Auswahl a1 a2 . . . an mehrfach in der Zusammenstellung ai1 ai2 . . . ail vorkommen, dann spricht man von einer Kombination der Ordnung l mit Wiederholungen und die Anzahl dieser Kombinationen wird mitKlW (n) bezeichnet. Die Berechnung der Anzahl Kl(n) von Kombinationen ohne Wiederholungen einer Auswahl a1 a2 . . . an von n verschiedenen Elementen wird fünfte Grundaufgabe der Kombinatorik genannt. Für die Anzahl Kl(n) erhält man den folgenden Satz: Satz 5.25 (Anzahl Kl(n) – fünfte Grundaufgabe der Kombinatorik) Für eine gegebene Auswahl a1 a2 . . . an von n verschiedenen Elementen existieren Kl(n) = n! (n− l)! l! = ( n l ) = PWl,n−l (n) verschiedene Kombinationen der Ordnung l ohne Wiederholungen. Beweis: Im Folgenden wird von der Anzahl V l(n) von Variationen der Ordnung l ohne Wiederholungen bei Vorliegen einer Auswahl von n verschiedenen Elementen ausgegangen. Nach Satz 5.20 gilt für ihre Anzahl V l(n) = n! (n−l)! . Im Gegensatz zu einer Variation werden bei einer Kombination Zusammenstellungen, die die gleichen Elemente in verschiedenen Anordnun- 100 Kapitel 55.4 Kombinatorik gen enthalten, als gleich identifiziert. Da jedoch l verschiedene Elemente auf genau l! verschiedene Weisen angeordnet werden können (siehe Satz 5.15) muss somit Kl(n) · l! = V l(n) bzw. Kl(n) = V l(n) l! = n! (n− l)! l! gelten. Zusammen mit der Definition 5.7 folgt daraus die Behauptung. Der Satz 5.25 gibt somit insbesondere eine Antwort auf die Frage, wieviele verschiedene l-elementige Teilmengen sich aus einer Menge mit n verschiedenen Elementen bilden lassen. Beispiel 5.26 (Kombinationen ohne Wiederholungen) a) Beim Skat gibt es K10(32) = ( 32 10 ) = 64.512.240 verschiedene Möglichkeiten für die Verteilung von 10 Karten an den ersten Spieler. Für den zweiten und dritten Spieler existieren entsprechend noch K10(22) = ( 22 10 ) = 646.646 bzw. K10(12) = ( 12 10 ) = 66 verschiedene Möglichkeiten. Für die beiden Karten, die in den „Skat“ wandern, gibt es dann wegen K2(2) = (22 ) = 1 nur noch eine Möglichkeit. Damit erhält man für die Anzahl der verschiedenen Kartenverteilungen, die beim Skat existieren, K10(32) ·K10(22) ·K10(12) ·K2(2) = ( 32 10 )( 22 10 )( 12 10 )( 2 2 ) = 2.753.294.408.504.640. In Beispiel 5.18c) wurde diese Anzahl bereits auf eine etwas andere Weise ermittelt. b) In Beispiel 5.21c) wurde ermittelt, dass beim „Zahlenlotto 6 aus 49“ – ohne Berücksichtigung der Zusatzzahl – genau V 6(49) = 10.068.347.520 verschiedene Ziehungsverläufe existieren. Da jedoch die Reihenfolge, in der die sechs Zahlen gezogen werden, keinen Einfluss auf die Anzahl richtig getippter Zahlen hat, gibt es „nur“ K6(49) = V 6(49) 6! = ( 49 6 ) = 13.983.816 verschiedene Möglichkeiten. Demnach existieren immer noch fast 14 Millionen verschiedene Tippreihen. Die Chance, „6 Richtige“ zu haben, ist damit verschwindend gering, wenn man davon ausgeht, dass alle 49 Zahlen mit der gleichen Wahrscheinlichkeit gezogen werden können. c) Werden bei einer Stichprobe zur Qualitätskontrolle aus 100 hergestellten Produkten zufällig 5 herausgegriffen, dann beträgt die Anzahl der verschiedenen Auswahlmöglichkeiten (Stichproben) K5(100) = ( 100 5 ) = 75.287.520. Die sechste Grundaufgabe der Kombinatorik ist schließlich gegeben durch die Berechnung der Anzahl KlW (n) von Kombinationen mit Wiederholungen einer Auswahl a1 a2 . . . an von n verschiedenen Elementen. Für die Anzahl KlW (n) gilt der folgende Satz: Satz 5.27 (Anzahl KlW (n) – sechste Grundaufgabe der Kombinatorik) Für eine gegebene Auswahl a1 a2 . . . an von n verschiedenen Elementen existieren KlW (n) = ( n+ l − 1 l ) verschiedene Kombinationen der Ordnung l mit Wiederholungen. Beweis: Ein Beweis dieses Satzes kann mit Hilfe von vollständiger Induktion nach l erfolgen. Beispiel 5.28 (Kombinationen mit Wiederholungen) a) Ein Würfel wird dreimal geworfen, wobei die Reihenfolge der Würfe keine Rolle spielt. Dann gilt n = 6 und l = 3 und es gibt somit K3W(6) = ( 8 3 ) = 56 verschiedene Möglichkeiten. 101 Kapitel 5 Trigonometrie und Kombinatorik b) Ein Unternehmen plant für die kommende Woche an den sechs Wochentagen Montag bis Samstag jeweils eine Werbeaktion. Zur Auswahl stehen Radiodurchsagen, Verteilung von Handzetteln und Plakatwerbung. Es gilt somit n = 3 und l = 6 und es liegt eine Kombination mit Wiederholungen vor. Wenn die Reihenfolge der Werbeaktionen eine Rolle spielt, sind V 6W(3) = 36 = 729 verschiedene Möglichkeiten (Variationen) mit Wiederholungen zu unterscheiden. Ist dagegen die Reihenfolge der Werbeaktionen nicht bedeutsam und wird sie deshalb auch nicht berücksichtigt, dann ergeben sich nur K6W(3) = ( 8 6 ) = 28 verschiedene Möglichkeiten (Kombinationen) mit Wiederholungen. In der Tabelle 5.2 sind die Ergebnisse für die sechs Grundaufgaben der Kombinatorik zusammengefasst, wobei von n Elementen ausgegangen wird: verschiedene gruppenweise identische Permutationen Elemente Elemente P(n) = n! PWn1,...,nk (n) = n!n1 ! n2 ! ··· nk ! ohne Wieder- mit Wieder- Variationen holung holung der Ordnung l V l(n) = n! (n−l)! V l W (n) = nl ohne Wieder- mit Wieder- Kombinationen holung holung der Ordnung l Kl(n) = (n l ) KlW (n) = ( n+l−1 l ) Tabelle 5.2: Zusammenstellung der sechs Grundaufgaben der Kombinatorik Wahrscheinlichkeitsrechnung P.-S. Laplace Die Kombinatorik ist eine der wichtigsten Grundlagen der klassischen Wahrscheinlichkeitstheorie. Diese basiert auf der sogenannten klassischen Auffassung des Wahrscheinlichkeitsbegriffs, welche vom bedeutenden französischen Mathematiker und Physiker Pierre-Simon Laplace (1749–1827) formuliert wurde und deshalb oft auch als Laplacesche Auffassung bezeichnet wird. Diese Auffassung besteht darin, dass die Wahrscheinlichkeit dafür, dass ein bestimmtes Ereignis eintritt, durch das Verhältnis Anzahl der günstigen Fälle Anzahl der möglichen Fälle (5.17) gegeben ist. Zur Bestimmung solcher Verhältnisse ist die Kombinatorik das wichtigste Hilfsmittel. Die große Bedeutung der Kombinatorik für die Wahrscheinlichkeitstheorie wird auch im folgenden Beispiel deutlich, das auch als Geburtstagsparadoxon oder Geburtstagsproblem bekannt ist. Es besagt: Befinden sich in einem Raum mindestens 23 Personen, dann ist die Wahrscheinlichkeit dafür, dass mindestens zwei dieser Personen am selben Tag Geburtstag haben, größer als 50%. Das Geburtstagsparadoxon ist eines der bekanntesten Beispiele dafür, dass bestimmte Wahrscheinlichkeiten von den meisten Menschen intuitiv falsch eingeschätzt und deshalb als paradox wahrgenommen werden. Denn häufig schätzen Menschen die Wahrscheinlichkeit dafür, dass von 23 Personen mindestens zwei Personen am selben Tag Geburtstag haben, mit 1% bis 5% um eine ganze Zehnerpotenz falsch ein. R. v. Mises Das Geburtstagsparadoxon wird oft dem österreichischen Mathematiker Richard von Mises (1883–1953) zugeschrieben. Gemäß dem US-amerikanischen emeritierten Informatikprofessor Donald Ervin Knuth (*1938), dem Entwickler des Textsatzsystems TEX, das auch zur An- 102 Kapitel 55.4 Kombinatorik fertigung dieses Lehrbuches verwendet wurde, steht der genaue Ursprung des Geburtstagsparadoxons nicht sicher fest. Richard von Mises war der jüngere Bruder des bekannten österreichischen Ökonomen Ludwig von Mises (1881–1973). Beispiel 5.29 (Geburtstagsparadoxon) Zur Berechnung der Wahrscheinlichkeit, dass in einer Gruppe von l Personen mindestens zwei dieser Personen am selben Tag Geburtstag haben, ist laut Formel (5.17) die Anzahl der günstigen Fälle sowie die Anzahl der möglichen Fälle zu bestimmen. Die Anzahl der möglichen Fälle ist gegeben durch die Anzahl der möglichen Geburtstagsvariationen bei l Personen. Mit (5.16) ergibt sich hierfür Anzahl der möglichen Fälle = 365l . Mit (5.15) erhält man, dass von diesen möglichen Fällen lediglich 365! (365 − l)! = 365 · 364 · · · (365 − l + 1) Geburtstagsvariationen aus ausschließlich unterschiedlichen Geburtstagen bestehen. Das heißt, bei 365l − 365 · 364 · · · (365 − l + 1) Geburtstagsvariationen haben mindestens zwei der l anwesenden Personen am selben Tag Geburtstag. Die Wahrscheinlichkeit, dass in einer Gruppe von l Personen mindestens zwei Personen am selben Tag Geburtstag haben, beträgt somit gemäß Formel (5.17) 365l − 365 · 364 · · · (365 − l + 1) 365l = 1 − 365 · 364 · · · (365 − l + 1) 365l . Zum Beispiel ergibt sich für l = 23 die Wahrscheinlichkeit 1 − 365 · 364 · · · 343 36523 ≈ 0,5073 > 0,5. Bei l = 50 Personen ist die Wahrscheinlichkeit sogar bereits größer als 97%. Für zwei weitere interessante wahrscheinlichkeitstheoretische Anwendungen der Kombinatorik siehe die sogenannte 37%-Regel in Beispiel 11.47 und den Nachweis dafür, dass Wahrscheinlichkeiten im Allgemeinen nicht transitiv sind in Beispiel 6.10. Urnenmodell Die letzten vier Grundaufgaben der Kombinatorik, d. h. die Bestimmung der Anzahl von Variationen und Kombinationen mit und ohne Wiederholungen, lassen sich gut am Beispiel einer Urne mit n verschiedenen Kugeln verdeutlichen. Urne mit verschiedenen Kugeln Bei dieser Veranschaulichung spricht man von einer geordneten Stichprobe vom Umfang l, wenn l Kugeln aus der Urne entnommen werden und dabei die Reihenfolge beachtet wird, und von einer ungeordneten Stichprobe vom Umfang l, wenn es bei der Ziehung nicht auf die Reihenfolge ankommt. Wird bei der Ziehung einer Kugel diese nach Notierung der Farbe oder Nummer wieder in die Urne zurückgelegt, dann ist von einer Stichprobe mit Zurücklegen die Rede. Werden dagegen gezogene Kugeln nicht in die Urne zurückgelegt, dann wird von einer Stichprobe ohne Zurücklegen gesprochen. Damit gelten insgesamt die folgenden Zusammenhänge: geordnete Stichproben ohne Zurücklegen = Variationen ohne Wiederholungen geordnete Stichproben mit Zurücklegen = Variationen mit Wiederholungen ungeordnete Stichproben ohne Zurücklegen = Kombinationen ohne Wiederholungen ungeordnete Stichproben mit Zurücklegen = Kombinationen mit Wiederholungen Die Tabelle 5.3 fasst diese Zusammenhänge zusammen, wobei von n Kugeln bzw. Elementen ausgegangen wird: 103 Kapitel 5 Trigonometrie und Kombinatorik Variation der Ordnung l Kombination der Ordnung l ohne Wiederholungen ohne Wiederholungen = = geordnete Stichprobe von l ungeordnete Stichprobe von l Kugeln ohne Zurücklegen Kugeln ohne Zurücklegen Anzahl: V l(n) = n! (n−l)! Anzahl: K l(n) = (n l ) Variation der Ordnung l Kombination der Ordnung l mit Wiederholungen mit Wiederholungen = = geordnete Stichprobe von l ungeordnete Stichprobe von l Kugeln mit Zurücklegen Kugeln mit Zurücklegen Anzahl: V lW (n) = nl Anzahl: KlW (n) = ( n+l−1 l ) Tabelle 5.3: Zusammenhang zwischen Stichproben, Variationen und Kombinationen mit und ohne Wiederholungen 104

Chapter Preview

References

Zusammenfassung

"uneingeschränkt zu empfehlen, [...] insbesondere als Einstiegslektüre im Bachelor-Studium". In: Studium, 2013.

So zentral die Rolle der Mathematik in der Ökonomie ist, so schwer tun sich die Studierenden mit mathematischen Methoden und Konzepten. Umso wichtiger ist es, die Studierenden bei ihrem aktuellen Wissensstand abzuholen und vorsichtig an den Stoff heranzuführen. Diesem Ziel verschreibt sich dieses Lehrbuch. Es führt mit vielen interessanten Beispielen aus der Ökonomie, kurzen Anekdoten und einem modernen mehrfarbigen Design in die zentralen mathematischen Methoden für ein erfolgreiches Wirtschaftsstudium ein, ohne dabei auf mathematische Klarheit sowie die notwendige Formalität und Stringenz zu verzichten. Auch nach dem Studium ist dieses Buch ein wertvoller Begleiter bei der mathematischen Lösung wirtschaftswissenschaftlicher Problemstellungen.

Aus dem Inhalt:

* Mathematische Grundlagen

* Lineare Algebra

* Matrizentheorie

* Folgen und Reihen

* Reellwertige Funktionen in einer und mehreren Variablen

* Differential- und Integralrechnung

* Optimierung mit und ohne Nebenbedingungen

* Numerische Verfahren

Dozenten finden auf der Website zum Buch unter www.vahlen.de zusätzliche Materialien zum Download.

"Indem Sie den Lehrstoff schrittweise aufbereiten und den Leser bei seinem aktuellen Wissenstand abholen, gelingt es ihnen [den Autoren], auch komplexe Zusammenhänge leicht nachvollziehbar zu vermitteln. Geschickt bauen sie immer wieder kurze Anekdoten, historische Ereignisse und überraschende Erkenntnisse in den Text ein". In: Studium, 2013.

Prof. Dr. Michael Merz ist Inhaber des Lehrstuhls für Mathematik und Statistik in den Wirtschaftswissenschaften an der Universität Hamburg. Prof. Dr. Mario V. Wüthrich forscht und lehrt am Department für Mathematik der ETH Zürich.