Diskrete Mathematik - Zähltheorie
Im täglichen Leben muss man oft die Anzahl aller möglichen Ergebnisse für eine Reihe von Ereignissen herausfinden. Auf wie viele Arten kann beispielsweise eine Jury aus 6 Männern und 4 Frauen aus 50 Männern und 38 Frauen ausgewählt werden? Wie viele verschiedene PAN-Nummern mit 10 Buchstaben können so generiert werden, dass die ersten fünf Buchstaben Großbuchstaben, die nächsten vier Ziffern und der letzte wieder Großbuchstaben sind. Zur Lösung dieser Probleme wird die mathematische Zähltheorie verwendet.Counting umfasst hauptsächlich die grundlegende Zählregel, die Permutationsregel und die Kombinationsregel.
Die Regeln für Summe und Produkt
Das Rule of Sum und Rule of Product werden verwendet, um schwierige Zählprobleme in einfache Probleme zu zerlegen.
The Rule of Sum- Wenn eine Folge von Aufgaben $ T_1, T_2, \ dots, T_m $ auf $ w_1, w_2, \ dots w_m $ ausgeführt werden kann (die Bedingung ist, dass keine Aufgaben gleichzeitig ausgeführt werden können), dann die Anzahl der Möglichkeiten zu Eine dieser Aufgaben ausführen ist $ w_1 + w_2 + \ dots + w_m $. Wenn wir zwei disjunkte Aufgaben A und B betrachten (dh $ A \ cap B = \ Emptyset $), dann ist mathematisch $ | A \ cup B | = | A | + | B | $
The Rule of Product- Wenn eine Folge von Aufgaben $ T_1, T_2, \ dots, T_m $ auf $ w_1, w_2, \ dots w_m $ ausgeführt werden kann und jede Aufgabe nach dem Auftreten der vorherigen Aufgabe eintrifft, gibt es $ w_1 \ mal w_2 \ times \ dots \ times w_m $ Möglichkeiten zur Ausführung der Aufgaben. Mathematisch gesehen, wenn eine Aufgabe B nach einer Aufgabe A eintrifft, dann ist $ | A \ mal B | = | A | \ times | B | $
Beispiel
Question- Ein Junge lebt in X und möchte in Z zur Schule gehen. Von seinem Zuhause X muss er zuerst Y und dann Y nach Z erreichen. Er kann X nach Y entweder mit 3 Buslinien oder 2 Zuglinien fahren. Von dort kann er entweder 4 Buslinien oder 5 Zuglinien wählen, um Z zu erreichen. Wie viele Wege gibt es von X nach Z?
Solution- Von X nach Y kann er auf $ 3 + 2 = 5 $ Wege gehen (Summenregel). Danach kann er auf $ 4 + 5 = 9 $ Weise von Y nach Z gehen (Summenregel). Daher kann er von X bis Z auf 5 $ mal 9 = 45 $ Wege gehen (Produktregel).
Permutationen
EIN permutationist eine Anordnung einiger Elemente, in denen die Reihenfolge wichtig ist. Mit anderen Worten ist eine Permutation eine geordnete Kombination von Elementen.
Beispiele
Aus einer Menge S = {x, y, z}, indem zwei gleichzeitig genommen werden, sind alle Permutationen -
$ xy, yx, xz, zx, yz, zy $.
Wir müssen eine Permutation dreistelliger Zahlen aus einer Menge von Zahlen $ S = \ lbrace 1, 2, 3 \ rbrace $ bilden. Beim Anordnen der Ziffern werden unterschiedliche dreistellige Zahlen gebildet. Die Permutation ist = 123, 132, 213, 231, 312, 321
Anzahl der Permutationen
Die Anzahl der Permutationen von 'n' verschiedenen Dingen, die gleichzeitig 'r' genommen wurden, wird mit $ n_ {P_ {r}} $ bezeichnet
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
wo $ n! = 1.2.3. \ dots (n - 1) .n $
Proof - Es gebe 'n' verschiedene Elemente.
Es gibt n Möglichkeiten, den ersten Platz zu füllen. Nach dem Füllen der ersten Stelle (n-1) bleibt die Anzahl der Elemente übrig. Daher gibt es (n-1) Möglichkeiten, den zweiten Platz auszufüllen. Nach dem Ausfüllen des ersten und zweiten Platzes bleibt (n-2) Anzahl der Elemente übrig. Daher gibt es (n-2) Möglichkeiten, den dritten Platz zu belegen. Wir können nun die Anzahl der Möglichkeiten, die r-te Stelle zu füllen, als [n - (r - 1)] = n - r + 1 verallgemeinern
Also, die Gesamtzahl. von Möglichkeiten, vom ersten bis zum r-ten Platz aufzufüllen -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ Punkte 3.2.1] / [(nr) (nr-1) \ Punkte 3.2.1] $
Daher,
$ n_ {P_ {r}} = n! / (nr)! $
Einige wichtige Permutationsformeln
Wenn es n Elemente gibt, von denen $ a_1 $ in irgendeiner Weise gleich sind, sind $ a_2 $ in einer anderen Art gleich; $ a_3 $ sind gleich der dritten Art und so weiter und $ a_r $ sind von $ r ^ {th} $ Art, wobei $ (a_1 + a_2 + ... a_r) = n $.
Dann ist die Anzahl der Permutationen dieser n Objekte = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
Anzahl der Permutationen von n verschiedenen Elementen, die n Elemente gleichzeitig einnehmen = $ n_ {P_n} = n! $
Die Anzahl der Permutationen von n verschiedenen Elementen, die r Elemente gleichzeitig einnehmen, wenn x bestimmte Dinge immer bestimmte Stellen einnehmen = $ n-x_ {p_ {rx}} $
Die Anzahl der Permutationen von n verschiedenen Elementen, wenn r bestimmte Dinge immer zusammenkommen, ist - $ r! (n - r + 1)! $
Die Anzahl der Permutationen von n verschiedenen Elementen, wenn r bestimmte Dinge niemals zusammenkommen, ist - $ n! - [r! (n - r + 1)!] $
Die Anzahl der kreisförmigen Permutationen von n verschiedenen Elementen, die x Elemente zum Zeitpunkt = $ ^ np_ {x} / x $ genommen haben
Die Anzahl der zirkulären Permutationen von n verschiedenen Dingen = $ ^ np_ {n} / n $
Einige Probleme
Problem 1 - Wie viele Möglichkeiten haben wir, aus 6 verschiedenen Karten herauszukommen?
Solution- Da wir 6 Karten gleichzeitig aus einem Kartenspiel mit 6 Karten nehmen, beträgt die Permutation $ ^ 6P_ {6} = 6! = 720 $
Problem 2 - Auf wie viele Arten können die Buchstaben des Wortes "READER" angeordnet werden?
Solution - Das Wort 'READER' enthält 6 Buchstaben (2 E, 1 A, 1D und 2R).
Die Permutation ist $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - Wie können die Buchstaben des Wortes 'ORANGE' so angeordnet werden, dass die Konsonanten nur die geraden Positionen einnehmen?
Solution- Das Wort 'ORANGE' enthält 3 Vokale und 3 Konsonanten. Anzahl der Möglichkeiten, die Konsonanten untereinander anzuordnen $ = ^ 3P_ {3} = 3! = 6 $. Die verbleibenden 3 freien Plätze werden mit 3 Vokalen in $ ^ 3P_ {3} = 3 gefüllt! = 6 $ Wege. Daher beträgt die Gesamtzahl der Permutationen $ 6 \ mal 6 = 36 $
Kombinationen
EIN combination ist die Auswahl einiger vorgegebener Elemente, in denen die Reihenfolge keine Rolle spielt.
Die Anzahl aller Kombinationen von n Dingen, die r gleichzeitig genommen werden, ist -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Finden Sie die Anzahl der Teilmengen der Menge $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ mit 3 Elementen.
Solution
Die Kardinalität der Menge ist 6 und wir müssen 3 Elemente aus der Menge auswählen. Hier spielt die Bestellung keine Rolle. Daher beträgt die Anzahl der Teilmengen $ ^ 6C_ {3} = 20 $.
Problem 2
Es gibt 6 Männer und 5 Frauen in einem Raum. Auf wie viele Arten können wir 3 Männer und 2 Frauen aus dem Raum auswählen?
Solution
Die Anzahl der Möglichkeiten, 3 Männer aus 6 Männern auszuwählen, beträgt $ ^ 6C_ {3} $, und die Anzahl der Möglichkeiten, 2 Frauen aus 5 Frauen auszuwählen, beträgt $ ^ 5C_ {2} $
Daher beträgt die Gesamtzahl der Wege - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $
Problem 3
Auf wie viele Arten können Sie 3 verschiedene Gruppen von 3 Schülern aus insgesamt 9 Schülern auswählen?
Solution
Nummerieren wir die Gruppen als 1, 2 und 3
Für drei Studenten für 1 Wahl st Gruppe, die Anzahl der Möglichkeiten - $ ^ 9C_ {3} $
Die Anzahl der Möglichkeiten für die Wahl 3 Studenten für 2 nd - Gruppe nach dem 1. Gruppe der Wahl - $ ^ 6C_ {3} $
Die Anzahl der Möglichkeiten für die Wahl 3 Studenten für 3 rd Gruppe nach dem 1. Wahl st und 2 nd Gruppe - $ ^ 3C_ {3} $
Daher ist die Gesamtzahl der Wege $ = ^ 9C_ {3} \ mal ^ 6C_ {3} \ mal ^ 3C_ {3} = 84 \ mal 20 \ mal 1 = 1680 $
Pascals Identität
Pascal Identität, abgeleitet zuerst von Blasius Pascal in 17 - ten Jahrhundert, heißt es, dass die Anzahl der Möglichkeiten k Elemente aus n Elementen zu wählen , ist gleich die Summe der Anzahl von Wegen zu wählen (k-1) Elemente von (n-1) -Elementen und die Anzahl der Möglichkeiten, Elemente aus n-1 Elementen auszuwählen.
Mathematisch gilt für alle positiven ganzen Zahlen k und n: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $
Proof - -
$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$
$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $
$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $
$ = (n-1)! \ frac {n} {k! (nk)! } $
$ = \ frac {n! } {k! (nk)! } $
$ = n_ {C_ {k}} $
Pigeonhole-Prinzip
Der deutsche Mathematiker Peter Gustav Lejeune Dirichlet erklärte 1834 ein Prinzip, das er als Schubladenprinzip bezeichnete. Jetzt ist es als das Pigeonhole-Prinzip bekannt.
Pigeonhole Principlegibt an, dass, wenn es weniger Taubenlöcher als die Gesamtzahl der Tauben gibt und jede Taube in ein Taubenloch gelegt wird, mindestens ein Taubenloch mit mehr als einer Taube vorhanden sein muss. Wenn n Tauben in m Schubladen gelegt werden, in denen n> m ist, gibt es ein Loch mit mehr als einer Taube.
Beispiele
Zehn Männer sind in einem Raum und nehmen an Handshakes teil. Wenn jede Person mindestens einmal die Hand schüttelt und kein Mann mehr als einmal die Hand desselben Mannes schüttelt, nahmen zwei Männer an der gleichen Anzahl von Handshakes teil.
In einer Klasse von 30 Personen müssen mindestens zwei Personen sein, deren Namen mit demselben Alphabet beginnen.
Das Einschluss-Ausschluss-Prinzip
Das Inclusion-exclusion principleberechnet die Kardinalzahl der Vereinigung mehrerer nicht disjunkter Mengen. Für zwei Sätze A und B lautet das Prinzip:
$ | A \ cup B | = | A | + | B | - | A \ cap B | $
Für drei Sätze A, B und C lautet das Prinzip:
$ | A \ Tasse B \ Tasse C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
Die verallgemeinerte Formel -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limit_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limit_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $
Problem 1
Wie viele ganze Zahlen von 1 bis 50 sind Vielfache von 2 oder 3, aber nicht beide?
Solution
Von 1 bis 100 gibt es $ 50/2 = 25 $ Zahlen, die Vielfache von 2 sind.
Es gibt $ 50/3 = 16 $ Zahlen, die ein Vielfaches von 3 sind.
Es gibt $ 50/6 = 8 $ Zahlen, die Vielfache von 2 und 3 sind.
Also ist $ | A | = 25 $, $ | B | = 16 $ und $ | A \ cap B | = 8 $.
$ | A \ cup B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
In einer Gruppe von 50 Schülern mögen 24 kalte Getränke und 36 heiße Getränke und jeder Schüler mag mindestens eines der beiden Getränke. Wie viele mögen sowohl Kaffee als auch Tee?
Solution
Sei X die Gruppe von Schülern, die kalte Getränke mögen, und Y die Gruppe von Menschen, die heiße Getränke mögen.
Also $ | X \ Tasse Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ cup Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Daher gibt es 10 Studenten, die sowohl Tee als auch Kaffee mögen.