So zählen Sie die Anzahl möglicher Zahlenkombinationen. Grundformeln der Kombinatorik
Eine Kombination ist eine ungeordnete Auswahl von Elementen einer endlichen Menge mit einer festen Anzahl und ohne Wiederholungen von Elementen. Unterschiedliche Kombinationen müssen sich in mindestens einem Element unterscheiden und die Reihenfolge der Elemente spielt keine Rolle. Beispielsweise können Sie aus der Menge aller Vokale lateinischer Buchstaben (AEIOU) 10 verschiedene Kombinationen von 3 Buchstaben bilden und so die folgenden ungeordneten Triolen bilden:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Es ist interessant festzustellen, dass man aus den gleichen fünf Buchstaben auch zehn verschiedene Kombinationen erhalten kann, wenn man jeweils zwei Buchstaben kombiniert und so die folgenden ungeordneten Paare ergibt:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Wenn Sie jedoch dieselben lateinischen Vokalbuchstaben mit 4 kombinieren, erhalten Sie nur die folgenden 5 verschiedenen Kombinationen:
AEIO, AEIU, AIOU, EIOU, AEOU.
Um die Anzahl der Kombinationen von n verschiedenen Elementen aus m Elementen anzugeben, wird im Allgemeinen die folgende Funktions-, Index- oder Vektorsymbolik (Appel) verwendet:
Unabhängig von der Notationsform kann die Anzahl der Kombinationen von n Elementen mal m Elementen mithilfe der folgenden multiplikativen und faktoriellen Formeln bestimmt werden:
Es lässt sich leicht überprüfen, ob das Ergebnis der Berechnungen mit diesen Formeln mit den Ergebnissen des oben diskutierten Beispiels mit Vokalkombinationen in lateinischen Buchstaben übereinstimmt. Insbesondere bei n=5 und m=3 führen Berechnungen mit diesen Formeln zu folgendem Ergebnis:
Im allgemeinen Fall haben Formeln für die Anzahl der Kombinationen eine kombinatorische Bedeutung und gelten für alle ganzzahligen Werte von n und m, so dass n > m > 0. Wenn m > n und m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Darüber hinaus ist es nützlich, sich die folgenden Grenzzahlen an Kombinationen zu merken, die leicht durch direkte Substitution in die multiplikativen und faktoriellen Formeln überprüft werden können:
Es sollte auch beachtet werden, dass die multiplikative Formel auch dann gültig bleibt, wenn n eine reelle Zahl ist, solange m noch ein ganzzahliger Wert ist. Allerdings verliert dann das Ergebnis der Berechnung unter Beibehaltung der formalen Gültigkeit seine kombinatorische Bedeutung.
IDENTITÄTEN VON KOMBINATIONEN
Die praktische Verwendung multiplikativer und faktorieller Formeln zur Bestimmung der Anzahl der Kombinationen für beliebige Werte von n und m erweist sich aufgrund des exponentiellen Wachstums der faktoriellen Produkte ihres Zählers und Nenners als wenig produktiv. Selbst für relativ kleine Werte von n und m übersteigen diese Produkte häufig die Möglichkeiten zur Darstellung ganzer Zahlen in modernen Computer- und Softwaresystemen. Darüber hinaus fallen ihre Werte deutlich größer aus als der resultierende Wert der Anzahl der Kombinationen, der relativ klein sein kann. Beispielsweise beträgt die Anzahl der Kombinationen von n=10 mal m=8 Elementen nur 45. Um diesen Wert mithilfe der Fakultätsformel zu ermitteln, müssen Sie jedoch zunächst viel größere Werte von 10 berechnen! im Zähler und 8! im Nenner:
Um zeitaufwändige Vorgänge zur Verarbeitung großer Mengen zu vermeiden und die Anzahl der Kombinationen zu bestimmen, können Sie verschiedene Wiederholungsbeziehungen verwenden, die sich direkt aus den multiplikativen und faktoriellen Formeln ergeben. Aus der Multiplikationsformel folgt insbesondere die folgende Rekursionsrelation, die es uns ermöglicht, das Verhältnis ihrer Indizes über das Vorzeichen der Anzahl der Kombinationen hinaus zu nehmen:
Schließlich liefert die Beibehaltung des Indexes die folgende Wiederholungsbeziehung, die leicht aus der Fakultätsformel für die Anzahl der Kombinationen ermittelt werden kann:
Nach elementaren Transformationen können die drei resultierenden Rekursionsrelationen in den folgenden Formen dargestellt werden:
Wenn wir nun die linke und rechte Seite der ersten beiden Formeln addieren und das Ergebnis um n reduzieren, erhalten wir eine wichtige Rekursionsrelation, die Identität der Addition von Kombinationszahlen genannt wird:
Die Additionsidentität bietet eine grundlegende Wiederholungsregel zur effizienten Bestimmung der Anzahl von Kombinationen für große Werte von n und m, da sie es ermöglicht, die Multiplikationsoperationen in faktoriellen Produkten durch die einfacheren Additionsoperationen zu ersetzen, und zwar für kleinere Anzahlen von Kombinationen. Unter Verwendung der Additionsidentität ist es nun insbesondere einfach, die oben diskutierte Anzahl der Kombinationen von n=10 mal m=8 Elementen zu bestimmen, indem die folgende Folge wiederkehrender Transformationen durchgeführt wird:
Darüber hinaus können aus der Additionsidentität mehrere nützliche Beziehungen zur Berechnung endlicher Summen abgeleitet werden, insbesondere die Formel für die Summierung nach Index, die die folgende Form hat:
Diese Beziehung erhält man, wenn man in der Additionsidentität die Rekursion entlang des Termes mit dem größten hochgestellten Index erweitert, während sein tiefgestellter Index größer als 0 ist. Das folgende numerische Beispiel veranschaulicht diesen Prozess wiederkehrender Transformationen:
Die tiefgestellte Summationsformel wird häufig verwendet, um die Summe der Potenzen natürlicher Zahlen zu berechnen. Unter der Annahme, dass m=1 ist, ist es mit dieser Formel insbesondere einfach, die Summe der ersten n Zahlen der natürlichen Reihe zu ermitteln:
Eine weitere nützliche Version der Summationsformel kann erhalten werden, indem die Wiederholung der Additionsidentität entlang des Termes mit dem kleinsten hochgestellten Index erweitert wird. Das folgende Zahlenbeispiel veranschaulicht diese Version wiederkehrender Transformationen:
Im allgemeinen Fall erhält man als Ergebnis solcher Transformationen die Summe der Anzahlen von Kombinationen, deren Indizes sich um eins von den benachbarten Termen unterscheiden und der Unterschied der Indizes konstant bleibt (im betrachteten Beispiel ist dies der Fall). auch gleich eins). Somit erhalten wir für beide Indizes der Kombinationszahlen die folgende Summationsformel:
Zusätzlich zu den oben diskutierten Wiederholungsbeziehungen und Summationsformeln wurden in der kombinatorischen Analyse viele andere nützliche Identitäten für Kombinationszahlen erhalten. Der wichtigste unter ihnen ist Symmetrieidentität, das so aussieht:
Die Gültigkeit der Symmetrieidentität kann im folgenden Beispiel überprüft werden, indem die Anzahl der Kombinationen von 5 Elementen mit 2 und mit (5 2) = 3 verglichen wird:
Die Symmetrieidentität hat eine offensichtliche kombinatorische Bedeutung, da sie durch die Bestimmung der Anzahl der Optionen zur Auswahl von m Elementen aus n Elementen gleichzeitig die Anzahl der Kombinationen aus den verbleibenden (nm) nicht ausgewählten Elementen festlegt. Die angegebene Symmetrie erhält man sofort, indem man in der Fakultätsformel für die Anzahl der Kombinationen m durch (nm) ersetzt:
Zahlen und Kombinationsidentitäten werden in verschiedenen Bereichen der modernen Computermathematik häufig verwendet. Ihre beliebtesten Anwendungen beziehen sich jedoch auf das Newtonsche Binomial und das Pascalsche Dreieck.
BINOMIALSATZ
Um verschiedene mathematische Transformationen und Berechnungen durchführen zu können, ist es wichtig, jede natürliche Potenz eines algebraischen Binomials (Binom) in Form eines Polynoms darstellen zu können. Für kleine Potenzen kann das gewünschte Polynom leicht durch direkte Multiplikation von Binomialen erhalten werden. Aus dem Studium der Elementarmathematik sind insbesondere die folgenden Formeln für Quadrat und Potenz der Summe zweier Terme bekannt:
Im allgemeinen Fall wird für einen beliebigen Grad n eines Binomials die erforderliche Darstellung in Form eines Polynoms durch den Binomialsatz von Newton bereitgestellt, der die folgende Gleichheit für wahr erklärt:
Diese Gleichheit wird üblicherweise als Newtonsches Binomial bezeichnet. Das Polynom auf seiner rechten Seite wird durch die Summe der Produkte von n Termen X und Y des Binomials auf der linken Seite gebildet, und die Koeffizienten davor werden Binomial genannt und sind gleich der Anzahl der Kombinationen mit Indizes, die werden aus ihren Kräften gewonnen. Aufgrund der besonderen Beliebtheit der Newtonschen Binomialformel in der kombinatorischen Analyse werden die Begriffe Binomialkoeffizient und Anzahl der Kombinationen im Allgemeinen als Synonyme betrachtet.
Offensichtlich sind die quadrierten und kubischen Summenformeln Sonderfälle des Binomialsatzes für n=2 bzw. n=3. Um höhere Grade (n>3) zu handhaben, sollte die Binomialformel von Newton verwendet werden. Seine Anwendung für ein Binomial vierten Grades (n=4) wird durch das folgende Beispiel demonstriert:
Es sei darauf hingewiesen, dass die Binomialformel den mittelalterlichen Mathematikern des arabischen Ostens und Westeuropas bereits vor Newton bekannt war. Daher ist sein allgemein akzeptierter Name historisch nicht fair. Newtons Verdienst besteht darin, dass er diese Formel auf den Fall eines beliebigen reellen Exponenten r verallgemeinert hat, der beliebige positive oder negative rationale und irrationale Werte annehmen kann. Im allgemeinen Fall hat eine solche Newton-Binomialformel auf der rechten Seite eine unendliche Summe und wird normalerweise wie folgt geschrieben:
Beispielsweise erhält man bei einem positiven Bruchwert des Exponenten r=1/2 unter Berücksichtigung der Werte der Binomialkoeffizienten die folgende Entwicklung:
Im allgemeinen Fall ist Newtons Binomialformel für jeden Exponenten eine spezielle Version der Maclaurin-Formel, die die Entwicklung einer beliebigen Funktion in eine Potenzreihe angibt. Newton hat das für |z| gezeigt< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Wenn wir nun Z=X/Y setzen und die linke und rechte Seite mit Yn multiplizieren, erhalten wir eine Version der oben besprochenen Newton-Binomialformel.
Trotz seiner Universalität behält der Binomialsatz seine kombinatorische Bedeutung nur für nichtnegative ganzzahlige Potenzen des Binomials. In diesem Fall kann es verwendet werden, um mehrere nützliche Identitäten für Binomialkoeffizienten zu beweisen. Insbesondere wurden oben Formeln zum Summieren der Anzahl von Kombinationen nach Index und nach beiden Indizes besprochen. Die fehlende hochgestellte Summationsidentität kann leicht aus der Binomialformel von Newton ermittelt werden, indem man X = Y = 1 oder Z = 1 einsetzt:
Eine weitere nützliche Identität stellt die Gleichheit der Summen von Binomialkoeffizienten mit geraden und ungeraden Zahlen her. Sie ergibt sich sofort aus der Newtonschen Binomialformel, wenn X = 1 und Y = 1 oder Z = 1:
Aus beiden betrachteten Identitäten erhalten wir schließlich die Identität der Summe von Binomialkoeffizienten mit nur geraden oder nur ungeraden Zahlen:
Basierend auf den betrachteten Identitäten und der wiederkehrenden Regel, Indizes unter dem Vorzeichen der Anzahl der Kombinationen zu entfernen, können eine Reihe interessanter Beziehungen ermittelt werden. Wenn wir beispielsweise in der hochgestellten Summationsformel n überall durch (n1) ersetzen und die Indizes in jedem Term entfernen, erhalten wir die folgende Beziehung:
Mit einer ähnlichen Technik in der Formel für die Summe der Binomialkoeffizienten mit geraden und ungeraden Zahlen lässt sich beispielsweise die Gültigkeit der folgenden Beziehung nachweisen:
Mit einer weiteren nützlichen Identität können Sie die Summe der Produkte symmetrisch angeordneter Binomialkoeffizienten zweier Binome beliebigen Grades n und k mithilfe der folgenden Cauchy-Formel einfach berechnen:
Die Gültigkeit dieser Formel ergibt sich aus der notwendigen Koeffizientengleichheit für jeden Grad m der Variablen Z auf der linken und rechten Seite der folgenden identischen Beziehung:
Im Sonderfall n=k=m erhält man unter Berücksichtigung der Symmetrieidentität eine gängigere Formel für die Summe der Quadrate von Binomialkoeffizienten:
Viele weitere nützliche Identitäten für Binomialkoeffizienten finden sich in der umfangreichen Literatur zur kombinatorischen Analyse. Ihre bekannteste praktische Anwendung hängt jedoch mit dem Pascalschen Dreieck zusammen.
PASCALS DREIECK
Das arithmetische Dreieck von Pascal bildet eine unendliche numerische Tabelle, die aus Binomialkoeffizienten besteht. Seine Linien sind von oben nach unten nach Binomialpotenzen geordnet. In jeder Zeile sind die Binomialkoeffizienten in aufsteigender Reihenfolge der hochgestellten Zeichen der entsprechenden Kombinationszahlen von links nach rechts angeordnet. Das Pascalsche Dreieck wird normalerweise entweder in gleichschenkliger oder rechteckiger Form geschrieben.
Anschaulicher und gebräuchlicher ist das gleichschenklige Format, bei dem die versetzten Binomialkoeffizienten ein unendliches gleichschenkliges Dreieck bilden. Sein Anfangsfragment für Binome bis zum 4. Grad (n=4) hat die folgende Form:
Im Allgemeinen stellt das gleichschenklige Dreieck von Pascal eine praktische geometrische Regel zur Bestimmung von Binomialkoeffizienten dar, die auf der Identität der Addition und der Symmetrie von Zahlenkombinationen basiert. Insbesondere ist gemäß der Additionsidentität jeder Binomialkoeffizient die Summe der beiden ihm am nächsten liegenden Koeffizienten der vorherigen Zeile. Gemäß der Symmetrieidentität ist das gleichschenklige Dreieck von Pascal symmetrisch bezüglich seiner Winkelhalbierenden. Somit ist jede seiner Linien ein numerisches Palindrom von Binomialkoeffizienten. Die angegebenen algebraischen und geometrischen Merkmale ermöglichen es, das gleichschenklige Dreieck von Pascal einfach zu erweitern und konsistent die Werte von Binomialkoeffizienten beliebiger Potenzen zu ermitteln.
Um jedoch verschiedene Eigenschaften des Pascalschen Dreiecks zu untersuchen, ist es bequemer, das formal strengere rechteckige Format zu verwenden. In diesem Format wird es durch eine untere Dreiecksmatrix von Binomialkoeffizienten angegeben, die ein unendliches rechtwinkliges Dreieck bilden. Das Anfangsfragment des Pascalschen rechtwinkligen Dreiecks für Binome bis zum 9. Grad (n=9) hat die folgende Form:
Geometrisch gesehen wird eine solche rechteckige Tabelle durch horizontale Verformung des gleichschenkligen Dreiecks von Pascal erhalten. Dadurch verwandeln sich die Zahlenreihen parallel zu den Seiten des gleichschenkligen Dreiecks von Pascal in Vertikalen und Diagonalen des rechtwinkligen Dreiecks von Pascal, und die horizontalen Linien beider Dreiecke fallen zusammen. Gleichzeitig bleiben die Regeln der Addition und Symmetrie der Binomialkoeffizienten gültig, obwohl das rechtwinklige Dreieck von Pascal die visuelle Symmetrie verliert, die für sein gleichschenkliges Gegenstück charakteristisch ist. Um dies zu kompensieren, ist es einfacher, die verschiedenen numerischen Eigenschaften der Binomialkoeffizienten für die Horizontalen, Vertikalen und Diagonalen des rechtwinkligen Dreiecks von Pascal formal zu analysieren.
Wenn man mit der Analyse der Horizontalen des rechtwinkligen Dreiecks von Pascal beginnt, fällt es leicht auf, dass die Summe der Elemente jeder Zeile mit der Nummer n gemäß der Formel zum Summieren von Binomialen durch Hochstellung gleich 2n ist. Daraus folgt, dass die Summe der Elemente über einer der horizontalen Linien mit der Nummer n gleich (2 n 1) ist. Dieses Ergebnis wird deutlich, wenn der Wert der Summe der Elemente jeder Horizontalen im binären Zahlensystem geschrieben wird. Für n=4 kann dieser Zusatz beispielsweise wie folgt geschrieben werden:
Hier sind ein paar weitere interessante Eigenschaften von Horizontalen, die auch mit Zweierpotenzen zusammenhängen. Es stellt sich heraus, dass, wenn die horizontale Zahl eine Zweierpotenz ist (n=2 k), alle ihre inneren Elemente (außer den äußeren) gerade Zahlen sind. Im Gegenteil, alle Zahlen einer horizontalen Linie sind ungerade, wenn ihre Zahl eins kleiner als eine Zweierpotenz ist (n=2 k 1). Die Gültigkeit dieser Eigenschaften kann überprüft werden, indem die Parität der internen Binomialkoeffizienten überprüft wird, beispielsweise in den Horizontalen n=4 und n=3 oder n=8 und n=7.
Sei nun die Zeilennummer des Pascalschen rechtwinkligen Dreiecks eine Primzahl p. Dann sind alle seine internen Binomialkoeffizienten durch p teilbar. Diese Eigenschaft lässt sich leicht für kleine Werte von Primkonturzahlen überprüfen. Beispielsweise sind alle internen Binomialkoeffizienten der fünften Horizontalen (5, 10 und 5) offensichtlich durch 5 teilbar. Um dieses Ergebnis für jede horizontale Primzahl p zu beweisen, müssen Sie die Multiplikationsformel für ihre Binomialkoeffizienten wie folgt schreiben:
Da p eine Primzahl ist und daher nicht durch m! teilbar ist, muss das Produkt der verbleibenden Faktoren des Zählers dieser Formel durch m! teilbar sein, um einen ganzzahligen Wert des Binomialkoeffizienten zu gewährleisten. Daraus folgt, dass das Verhältnis in eckigen Klammern eine natürliche Zahl N ist und das gewünschte Ergebnis offensichtlich wird:
Mit diesem Ergebnis können wir feststellen, dass die Zahlen aller horizontalen Geraden des Pascalschen Dreiecks, deren innere Elemente durch eine gegebene Primzahl p teilbar sind, Potenzen von p sind, das heißt, sie haben die Form n=p·k. Insbesondere wenn p=3, dann teilt die Primzahl p nicht nur alle internen Elemente der Zeile 3, wie oben festgestellt, sondern beispielsweise auch die 9. Horizontale (9, 36, 84 und 126). Andererseits ist es im Pascalschen Dreieck unmöglich, eine horizontale Linie zu finden, deren innere Elemente alle durch eine zusammengesetzte Zahl teilbar sind. Andernfalls muss die Zahl einer solchen horizontalen Linie gleichzeitig eine Potenz von Primteilern der zusammengesetzten Zahl sein, durch die alle ihre inneren Elemente geteilt werden. Dies ist jedoch aus offensichtlichen Gründen unmöglich.
Die betrachteten Überlegungen ermöglichen es uns, das folgende allgemeine Kriterium für die Teilbarkeit der horizontalen Elemente des Pascalschen Dreiecks zu formulieren. Der größte gemeinsame Teiler (GCD) aller internen Elemente einer horizontalen Linie des Pascalschen Dreiecks mit der Zahl n ist gleich der Primzahl p, wenn n=pk oder 1 in allen anderen Fällen:
GCD(Cmn) = ( ) für jede 0< m < n .
Zum Abschluss der Analyse der Horizontalen lohnt es sich, eine weitere interessante Eigenschaft der sie bildenden Reihe von Binomialkoeffizienten zu berücksichtigen. Wenn die Binomialkoeffizienten einer horizontalen Linie mit der Zahl n mit aufeinanderfolgenden Potenzen der Zahl 10 multipliziert werden und dann alle diese Produkte addiert werden, ist das Ergebnis 11 n. Die formale Begründung für dieses Ergebnis ist die Substitution der Werte X=10 und Y=1 (oder Z=1) in die Newton-Binomialformel. Das folgende Zahlenbeispiel verdeutlicht die Erfüllung dieser Eigenschaft für n=5:
Die Analyse der Eigenschaften der Vertikalen des rechtwinkligen Dreiecks von Pascal kann mit der Untersuchung der individuellen Eigenschaften ihrer Bestandteile beginnen. Formal wird jede Vertikale m durch die folgende unendliche Folge von Binomialkoeffizienten mit einem konstanten hochgestellten Index (m) und einem Inkrement des tiefgestellten Index gebildet:
Offensichtlich erhält man bei m=0 eine Folge von Einsen und bei m=1 eine Reihe natürlicher Zahlen. Bei m=2 besteht die Vertikale aus Dreieckszahlen. Jede Dreieckszahl kann auf einer Ebene in Form eines gleichseitigen Dreiecks dargestellt werden, das mit beliebigen schachbrettartig angeordneten Objekten (Kernen) gefüllt ist. In diesem Fall bestimmt der Wert jeder Dreieckszahl T k die Anzahl der darstellenden Kernel, und der Index zeigt an, wie viele Kernelzeilen zur Darstellung erforderlich sind. Beispielsweise stellen 4 anfängliche Dreieckszahlen die folgenden Konfigurationen der entsprechenden Anzahl nuklearer „@“-Symbole dar:
Es sei darauf hingewiesen, dass man auf ähnliche Weise quadratische Zahlen S k in Betracht ziehen kann, die man durch Quadrieren natürlicher Zahlen erhält, und im Allgemeinen vieleckige Zahlen, die durch regelmäßiges Füllen regelmäßiger Vielecke gebildet werden. Insbesondere können die 4 anfänglichen Quadratzahlen wie folgt dargestellt werden:
Zurück zur Analyse der Vertikalen des Pascalschen Dreiecks können wir feststellen, dass die nächste Vertikale bei m=3 mit tetraedrischen (pyramidenförmigen) Zahlen gefüllt ist. Jede dieser Zahlen P k gibt die Anzahl der Kerne an, die in Form eines Tetraeders angeordnet werden können, und der Index bestimmt, wie viele horizontale dreieckige Schichten von Kernreihen erforderlich sind, um ihn im dreidimensionalen Raum darzustellen. In diesem Fall müssen alle horizontalen Schichten als aufeinanderfolgende Dreieckszahlen dargestellt werden. Die Elemente der folgenden Vertikalen des Pascalschen Dreiecks für m>3 bilden Reihen hypertetraedischer Zahlen, die weder in der Ebene noch im dreidimensionalen Raum eine visuelle geometrische Interpretation haben, sondern formal mehrdimensionalen Analoga von Dreiecks- und Tetraederzahlen entsprechen.
Obwohl die vertikalen Zahlenreihen des Pascalschen Dreiecks die betrachteten individuellen Formmerkmale aufweisen, ist es für sie möglich, die Teilsummen der Werte der Anfangselemente auf die gleiche Weise zu berechnen, indem man die Formel zum Summieren der Kombinationszahlen nach Index verwendet . Im Pascalschen Dreieck hat diese Formel die folgende geometrische Interpretation. Die Summe der Werte der n oberen Binomialkoeffizienten einer beliebigen Vertikale ist gleich dem Wert des Elements der nächsten Vertikalen, das sich eine Zeile darunter befindet. Dieses Ergebnis stimmt auch mit der geometrischen Struktur von Dreiecks-, Tetraeder- und Hypertetraederzahlen überein, da die Darstellung jeder dieser Zahlen aus Kernschichten besteht, die Zahlen niedrigerer Ordnung darstellen. Insbesondere kann die n-te Dreieckszahl T n durch Summieren aller natürlichen Zahlen erhalten werden, die ihre linearen Schichten darstellen:
Ebenso ist es nicht schwierig, die Tetraederzahl Pn zu ermitteln, indem man die folgende Summe der ersten n Dreieckszahlen berechnet, aus denen die horizontalen Kernschichten bestehen:
Zusätzlich zu den Horizontalen und Vertikalen im rechtwinkligen Dreieck von Pascal kann man auch diagonale Reihen von Elementen verfolgen, deren Untersuchung ebenfalls von Interesse ist. Dabei wird üblicherweise zwischen absteigenden und aufsteigenden Diagonalen unterschieden. Die Abwärtsdiagonalen verlaufen parallel zur Hypotenuse des Pascalschen rechtwinkligen Dreiecks. Sie werden durch eine Reihe von Binomialkoeffizienten mit einem Inkrement beider Indizes gebildet. Aufgrund der Identität der Symmetrie stimmen die absteigenden Diagonalen in den Werten ihrer Elemente mit den entsprechenden vertikalen Reihen des Pascalschen Dreiecks überein und wiederholen daher alle ihre oben diskutierten Eigenschaften. Die angegebene Entsprechung kann durch die Übereinstimmung der Werte der Elemente der absteigenden Diagonale und der Vertikalen mit einer beliebigen Zahl n verfolgt werden, wenn vertikale Nullen nicht berücksichtigt werden:
Aufsteigende Diagonalen bilden Zahlenreihen, die geometrisch senkrecht zur Hypotenuse des rechtwinkligen Dreiecks von Pascal stehen. Sie sind mit Binomialkoeffizienten gefüllt, wobei der untere Wert dekrementiert und der hochgestellte Wert erhöht wird. Insbesondere bilden die 7 oberen aufsteigenden Diagonalen ohne Berücksichtigung der nachgestellten Nullen die folgende Zahlenfolge:
Im Allgemeinen enthält die aufsteigende Diagonalzahl n die folgenden Binomialkoeffizienten, deren Summe der Indizes jeweils gleich (n1) ist:
Aufgrund der Additionsidentität für Kombinationszahlen ist jedes Diagonalelement gleich der Summe zweier Elemente, deren Indizes den beiden vorherigen aufsteigenden Diagonalen entsprechen. Dadurch kann jede nachfolgende aufsteigende Diagonale durch paarweise Summierung benachbarter horizontaler Elemente aus den beiden vorherigen Diagonalen konstruiert werden, wodurch das Pascal-Dreieck entlang der Diagonale unendlich erweitert wird. Das folgende Fragment des Pascalschen Dreiecks veranschaulicht die Konstruktion einer aufsteigenden Diagonale Nummer 8 entlang der Diagonalen Nummer 6 und 7:
Bei dieser Konstruktionsmethode ist die Summe der Elemente jeder aufsteigenden Diagonale, beginnend mit der dritten, gleich der Summe der Elemente der beiden vorherigen aufsteigenden Diagonalen, und die ersten beiden Diagonalen bestehen nur aus einem Element, dem Wert davon ist 1. Die Ergebnisse der entsprechenden Berechnungen bilden die folgende Zahlenreihe, anhand derer Sie die Gültigkeit der betrachteten Eigenschaft der aufsteigenden Diagonalen des rechtwinkligen Dreiecks von Pascal überprüfen können:
Wenn Sie diese Zahlen analysieren, können Sie sehen, dass nach einem ähnlichen Gesetz die bekannte Folge von Fibonacci-Zahlen gebildet wird, wobei jede nächste Zahl gleich der Summe der beiden vorherigen ist und die ersten beiden Zahlen gleich 1 sind:
Daraus können wir die folgende wichtige Schlussfolgerung ziehen: Die Diagonalsummen der Elemente des Pascalschen Dreiecks bilden die Fibonacci-Folge. Diese Eigenschaft ermöglicht es uns, ein weiteres interessantes Merkmal des Pascalschen Dreiecks festzustellen. Durch rekursive Erweiterung der Fibonacci-Formel lässt sich leicht beweisen, dass die Summe der ersten n Fibonacci-Zahlen gleich (F n+2 1) ist.
Daher ist die Summe der Binomialkoeffizienten, die die oberen n Diagonalen füllen, auch gleich (F n+2 1). Daraus folgt, dass die Summe der ersten n Diagonalen des Pascalschen Dreiecks um 1 kleiner ist als die Summe der Binomialkoeffizienten, die auf seiner Diagonale mit der Zahl (n+2) stehen.
Abschließend ist festzuhalten, dass die betrachteten Eigenschaften der Horizontalen, Vertikalen und Diagonalen des Pascalschen Dreiecks nicht die große Vielfalt an Möglichkeiten erschöpfen, die verschiedene mathematische Aspekte miteinander verbinden, die auf den ersten Blick nichts gemeinsam haben. Aufgrund dieser ungewöhnlichen Eigenschaften können wir das Pascalsche Dreieck als eines der perfektesten numerischen Systeme betrachten, dessen Fähigkeiten nicht alle aufgelistet werden können und schwer zu überschätzen sind.
Der Algorithmus zur Berechnung der Anzahl der Kombinationen mithilfe des Pascal-Dreiecks ist unten dargestellt:
Private Funktion SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) Für i = 0 bis n TT (0, i) = 1 TT (i, i) = 1 Weiter Für i = 2 Bis n Für j = 1 Bis i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Weiter Weiter SochTT = TT (n, k) Endfunktion
Wenn Sie die Anzahl der Kombinationen viele Male berechnen müssen, ist es möglicherweise bequemer, das Pascal-Dreieck einmal zu konstruieren und dann Daten aus dem Array zu empfangen.
Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) For i = start To end TT (0, i) = 1 TT (i, i) = 1 Next If end< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Zuerst müssen Sie die CreateTT-Prozedur aufrufen. Anschließend können Sie die Anzahl der Kombinationen mithilfe der SochTT-Funktion ermitteln. Wenn Sie das Dreieck nicht mehr benötigen, rufen Sie die TerminateTT-Prozedur auf. Wenn im obigen Code beim Aufruf der SochTT-Funktion das Dreieck noch nicht auf das erforderliche Niveau vervollständigt wurde, wird es mithilfe der BuildTT-Prozedur vervollständigt. Die Funktion ruft dann das gewünschte Element des TT-Arrays ab und gibt es zurück.
Dim ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 Für j = 1 Zu N Wenn X1(j)<>0 Dann n1 = n1 + 1 Wenn n1 = Counter(i) Dann Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
KOMBINATIONEN NATÜRLICHER ZAHLEN AUFLISTEN
Um viele praktische Probleme zu lösen, ist es notwendig, alle Kombinationen fester Kardinalität aufzulisten, die aus den Elementen einer gegebenen endlichen Menge erhalten werden können, und nicht nur deren Anzahl zu bestimmen. Unter Berücksichtigung der immer bestehenden Möglichkeit der ganzzahligen Nummerierung der Elemente jeder endlichen Menge ist es in den meisten Fällen zulässig, sich auf die Verwendung von Algorithmen zur Aufzählung von Kombinationen natürlicher Zahlen zu beschränken. Der natürlichste und einfachste davon ist der Algorithmus zum Auflisten von Kombinationen natürlicher Zahlen in Lexigraphische Ordnung.
Um diesen Algorithmus formal zu beschreiben, ist es zweckmäßig anzunehmen, dass die Hauptmenge, von der alle Kombinationen von m Elementen aufgelistet werden müssen, aufeinanderfolgende natürliche Zahlen von 1 bis n bildet. Dann ist jede Kombination von m Als Ergebnis der Reihenfolge stellt sich heraus, dass der Wert an jeder Position eines solchen Kombinationsvektors natürlich von oben und unten wie folgt wertmäßig begrenzt ist: Der lexigraphische Algorithmus generiert sequentiell solche Kombinationsvektoren, beginnend mit dem lexigraphisch kleinsten Vektor, wobei alle Positionen die folgenden minimal möglichen Werte von Elementen enthalten, die ihren Indizes entsprechen: Jeder aufeinanderfolgende Kombinationsvektor wird aus dem aktuellen gebildet, nachdem seine Elemente von links nach rechts gescannt wurden, um das Element ganz rechts zu finden, das seinen Grenzwert noch nicht erreicht hat: Der Wert eines solchen Elements sollte um 1 erhöht werden. Jedem Element rechts davon sollte der kleinstmögliche Wert zugewiesen werden, der um 1 größer ist als sein Nachbar links. Nach diesen Änderungen wird der nächste Kombinationsvektor die folgende Elementzusammensetzung haben: Somit wird der nächste Kombinationsvektor lexigraphisch größer sein als der vorherige, da die Werte ihrer anfänglichen (j1) Elemente gleichwertig sind und der Wert des Elements an Position j um 1 größer ist als der des vorherigen . Die angegebene Beziehung der zunehmenden lexigraphischen Reihenfolge wird garantiert bei allen Iterationen des Algorithmus erfüllt. Das Ergebnis ist eine aufsteigende lexigraphische Folge, die durch den lexigraphisch größten Kombinationsvektor vervollständigt wird, wobei die Elemente an allen Positionen die folgenden Maximalwerte haben: Der betrachtete lexigraphische Algorithmus wird durch das folgende Beispiel veranschaulicht, in dem es notwendig ist, alle 15 Kombinationen von n=6 ersten natürlichen Zahlen mal m=4 Zahlen, also alle möglichen 4-elementigen Teilmengen der Hauptgenerierung, in aufsteigender lexigraphischer Reihenfolge aufzulisten Menge (1, 2, 3, 4, 5, 6) aus 6 Elementen. Die Berechnungsergebnisse sind in der folgenden Tabelle dargestellt: In diesem Beispiel sind die größten zulässigen Zahlenwerte an den Positionen der Kombinationsvektoren 3, 4, 5 und 6. Zur einfacheren Interpretation der Ergebnisse ist in jedem Kombinationsvektor das Element ganz rechts angegeben, das hat der Maximalwert noch nicht erreicht ist, ist unterstrichen. Numerische Indizes von Kombinationsvektoren bestimmen ihre Nummern in lexigraphischer Reihenfolge. Im allgemeinen Fall kann die lexigraphische Zahl N einer beliebigen Kombination von n Elementen mal m mit der folgenden Formel berechnet werden, wobei aus kosmetischen Gründen die Appel-Symbolik zur Bezeichnung der Anzahl der Kombinationen verwendet wird: Insbesondere die folgenden Berechnungen unter Verwendung dieser Formel für die Kombinationszahl (1, 3, 4, 6) von n=6 Elementen von m=4 in lexigraphischer Reihenfolge ergeben das Ergebnis N=8, was dem oben diskutierten Beispiel entspricht: Im allgemeinen Fall lässt sich anhand der Identität für die Summe der Kombinationszahlen für beide Indizes zeigen, dass die Zahl der lexigraphisch kleinsten Kombination (1, ... i, ... m) bei der Berechnung damit berechnet wird Formel wird immer gleich 1 sein: Es ist auch offensichtlich, dass die Anzahl der lexigraphisch größten Kombinationen (m, … nm+i, … n), wenn sie mit dieser Formel berechnet wird, gleich der Anzahl der Kombinationen von n Elementen mal m ist: Die Formel zur Berechnung lexigrafischer Kombinationszahlen kann zur Lösung des Umkehrproblems verwendet werden, bei dem Sie den Kombinationsvektor anhand seiner Zahl in lexigrafischer Reihenfolge bestimmen müssen. Um ein solches inverses Problem zu lösen, muss es in Form einer Gleichung geschrieben werden, in der alle unbekannten Werte der Elemente des Vektors der gewünschten Kombination (C 1, ... C i, ... C m) enthalten sind ) sind in der Anzahl der Kombinationen auf der rechten Seite konzentriert, und auf der linken Seite wird die bekannte Differenz L der Anzahl der Kombinationen von jeweils n Elementen m und der Anzahl der erforderlichen Kombinationen N geschrieben: Die Lösung dieser Gleichung liefert der folgende „gierige“ Algorithmus, bei dessen Iterationen die Werte der Elemente des Vektors der gewünschten Kombination nacheinander ausgewählt werden. Bei der ersten Iteration wird der minimal mögliche (innerhalb seiner Grenzen) Wert von C 1 ausgewählt, bei dem der erste Term auf der rechten Seite einen Maximalwert hat, der L nicht überschreitet: Jetzt sollte die linke Seite von L um die erste Anzahl von Kombinationen auf der rechten Seite mit dem ausgewählten Wert von C 1 reduziert werden und auf ähnliche Weise der Wert von C 2 bei der zweiten Iteration bestimmt werden: In ähnlicher Weise sollten alle nachfolgenden Iterationen durchgeführt werden, um die Werte aller anderen Elemente C i der gewünschten Kombination bis zum letzten Element C m auszuwählen: Aus offensichtlichen Gründen kann der Wert des letzten Elements C m basierend auf der Gleichheit seiner Anzahl von Kombinationen mit dem Restwert der linken Seite von L bestimmt werden: Es ist zu beachten, dass der Wert des letzten Elements der Kombination C m noch einfacher ermittelt werden kann, ohne seine möglichen Werte aufzuzählen: Die Implementierung von Iterationen des betrachteten Algorithmus wird durch das folgende Beispiel veranschaulicht, bei dem es notwendig ist, Kombinationen mit der Zahl N=8 in lexigraphischer Reihenfolge zu bestimmen, wenn n=6 und m=4: Die algorithmische Fähigkeit, eine Kombination aus einer gegebenen Zahl in lexigraphischer Reihenfolge zu bestimmen, kann in verschiedene Richtungen genutzt werden. Insbesondere bei der Auflistung von Kombinationen in lexigraphischer Reihenfolge ist es notwendig, eine Rückkehr zu jeder zuvor erhaltenen Kombination sicherzustellen; es reicht aus, nur deren Nummer zu kennen. Darüber hinaus wird es möglich, Kombinationen in beliebiger Reihenfolge zu erzeugen, die durch eine willkürlich vorgegebene Reihenfolge ihrer lexigraphischen Zahlen geregelt wird. Jetzt stellen wir einen Algorithmus zum Generieren von Kombinationen in lexikografischer Reihenfolge vor: 2 für i:= 1 bis k do A[i] := i; 5 begin write(A, …, A[k]); 6 if A[k] = n then p:= p 1 else p:= k; 8 für i:= k downto p do A[i] := A[p] + i p + 1 KOMBINATIONEN MIT WIEDERHOLENDEN ELEMENTEN Im Gegensatz zu einer klassischen Kombination, bei der alle Elemente unterschiedlich sind, bildet eine Kombination mit Wiederholungen eine ungeordnete Auswahl von Elementen einer endlichen Menge, wobei jedes Element unbegrenzt oft vorkommen kann und nicht unbedingt in einer einzigen Kopie vorhanden ist. In diesem Fall ist die Anzahl der Wiederholungen von Elementen in der Regel nur durch die Länge der Kombination begrenzt und Kombinationen, die sich in mindestens einem Element unterscheiden, gelten als unterschiedlich. Durch die Auswahl von 4 optional unterschiedlichen Zahlen aus der Menge 1, 2 und 3 können Sie beispielsweise die folgenden 15 Kombinationen mit Wiederholungen erstellen: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Im Allgemeinen können Kombinationen mit Wiederholungen durch Auswahl von n Elementen beliebigen Typs gebildet werden. Sie können jedoch immer aufeinanderfolgenden natürlichen Zahlen von 1 bis n zugeordnet werden. Dann kann jede Kombination von m optional unterschiedlichen Zahlen in diesem Bereich in Vektorform geschrieben werden, indem man sie in nicht abnehmender Reihenfolge von links nach rechts anordnet: Selbstverständlich können bei dieser Notationsform aufgrund der Möglichkeit unbegrenzter Wiederholungen alle benachbarten Elemente gleich sein. Allerdings kann jedem Kombinationsvektor mit Wiederholungen von n Elementen mal m ein Kombinationsvektor von (n+m−1) Elementen mal m zugeordnet werden, der wie folgt aufgebaut ist: Es ist klar, dass für alle Werte der Elemente des Vektors f die Elemente des Vektors C garantiert unterschiedlich und streng in aufsteigender Reihenfolge ihrer Werte aus dem Bereich von 1 bis (n+m1) geordnet sind. : Das Vorhandensein einer Eins-zu-eins-Entsprechung zwischen den Elementen der Kombinationsvektoren f und C ermöglicht es uns, die folgende einfache Methode zur systematischen Auflistung von Kombinationen mit Wiederholungen von n Elementen durch m vorzuschlagen. Es ist lediglich erforderlich, beispielsweise alle C-Kombinationen von (n+m1) Elementen von m in lexigraphischer Reihenfolge aufzulisten und die Elemente jedes einzelnen von ihnen nacheinander in die entsprechenden Elemente von Kombinationen mit Wiederholungen f unter Verwendung der folgenden Formel umzuwandeln: Dadurch wird eine Folge von Vektoren von Kombinationen mit Elementwiederholungen gebildet, die in der Reihenfolge angeordnet werden, die durch die Auflistung der entsprechenden Kombinationen ohne Elementwiederholungen erzeugt wird. Um insbesondere die obige Folge von Kombinationen aus 3 Ziffern 1, 2 und 3 mit Wiederholungen von 4 Ziffern zu erhalten, ist es notwendig, alle Kombinationen ohne Wiederholungen von 6 Ziffern 1,2,3,4, 5 in lexikalischer Reihenfolge aufzulisten und 6 sind jeweils 4 Ziffern und werden wie angegeben umgewandelt. Das folgende Beispiel zeigt eine solche Konvertierung der Kombination (1,3,4,6) mit der lexikografischen Zahl 8: Die berücksichtigte Eins-zu-eins-Entsprechung zwischen Kombinationen mit und ohne Wiederholungen von Elementen bedeutet, dass ihre Mengen gleich mächtig sind. Daher ist im allgemeinen Fall die Anzahl der Kombinationen mit Wiederholungen von n Elementen um m gleich der Anzahl der Kombinationen ohne Wiederholungen von (n+m1) Elementen um m. Unter Verwendung derselben Symbolik zur Bezeichnung der Anzahl von Kombinationen mit Wiederholungen f und ohne Wiederholungen C kann diese Gleichheit wie folgt geschrieben werden: Es lässt sich leicht überprüfen, dass für das oben betrachtete Beispiel mit n=3 und m=4 die Anzahl der Wiederholungskombinationen 15 beträgt, was mit dem Ergebnis ihrer direkten Auflistung übereinstimmt: Es ist zu beachten, dass im Gegensatz zur klassischen Version die Werte der Kombinationsparameter mit Wiederholungen n und m nicht direkt miteinander in Zusammenhang stehen, daher f(n,m)>0 für jede Kombination ihrer positiven Werte. Die entsprechenden Randbedingungen ergeben sich aus der Gleichheit der Werte von (n+m1) und (n1) bzw. (n+m1) und m: Es sollte auch ganz offensichtlich sein, dass, wenn m gleich 1 ist, keine Wiederholungen von Elementen möglich sind und daher für jeden positiven Wert von n>0 die folgende Gleichheit gilt: Darüber hinaus gilt für Kombinationszahlen mit Wiederholungen für beliebige positive Werte von n und m die folgende Wiederholungsrelation, die der Additionsidentität für Kombinationszahlen ohne Wiederholungen von Elementen ähnelt: Tatsächlich verwandelt es sich in die angegebene Additionsidentität, wenn die entsprechende Anzahl von Kombinationen ohne Wiederholungen formal auf der linken und rechten Seite ersetzt wird: Die betrachtete Wiederholungsbeziehung kann verwendet werden, um die Anzahl der Kombinationen mit Wiederholungen effektiv zu bestimmen, wenn es darauf ankommt, die arbeitsintensiven Operationen zur Berechnung faktorieller Produkte zu eliminieren und sie durch einfachere Additionsoperationen zu ersetzen. In diesem Fall müssen Sie zur Berechnung des Werts von f(n,m) nur diese Wiederholungsrelation anwenden, bis Sie die Summe der Terme der Form f(1,m) und f(i,1) erhalten, wobei i nimmt Werte im Bereich von n bis 1 an. Per Definition der Größe sind solche Terme gleich 1 bzw. i. Das folgende Beispiel veranschaulicht die Verwendung dieser Transformationstechnik für den Fall n=3 und m=4: BINÄRKOMBINATIONEN AUFLISTEN Bei der Implementierung von Kombinationen in Hardware oder der Programmierung in Assembler ist es wichtig, Kombinationsdatensätze im Binärformat verarbeiten zu können. In diesem Fall sollte jede Kombination von n Elementen von m in Form einer n-Bit-Binärzahl (B n,...B j,...B 1) angegeben werden, wobei m Einheitsziffern die Elemente von angeben Kombination, und die verbleibenden (nm) Ziffern haben Nullwerte. Offensichtlich müssen sich bei dieser Notationsform verschiedene Kombinationen in der Anordnung der Einsen-Ziffern unterscheiden, und es gibt nur C(n,m) Möglichkeiten, m Einsen oder (nm) Nullen in einem n-Bit-Binärsatz anzuordnen. Die folgende Tabelle listet beispielsweise alle 6 solcher Binärkombinationen auf, die 4-Bit-Binärzahlen für alle Kombinationen von 4 Elementen einer beliebigen Menge (E 1 , E 2 , E 3 , E 4 ) mal 2 liefern: Im Allgemeinen besteht die Aufgabe, solche Binärkombinationen aufzuzählen, darin, alle n-Bit-Binärmengen mit unterschiedlichen Anordnungen von m Eins- und (nm) Nullbits systematisch zu durchsuchen. In der einfachsten Form wird eine solche Suche durch verschiedene Methoden der Transponierung benachbarter Bits mit einer Verschiebung (Transpositiv-Verschiebungsalgorithmen) implementiert. Dabei handelt es sich um iterative Algorithmen, und ihre Namen spiegeln die Art der bei jedem Schritt durchgeführten Operationen wider. Iterative Verfahren transpositiver Verschiebungsalgorithmen bilden Folgen binärer Kombinationen, die mit einer binären Menge beginnen, in der alle Einsen in den Ziffern niedriger Ordnung konzentriert sind (rechts), und enden, wenn alle Einsen in den Ziffern höherer Ordnung stehen ( auf der Linken): Diese Sequenzen stimmen zwar in den Anfangs- und Endkombinationen überein, unterscheiden sich jedoch in der Reihenfolge, in der binäre Zwischensätze aufgelistet sind. In allen Fällen wird jedoch jede nachfolgende Binärkombination aus der vorherigen als Ergebnis der Durchführung der entsprechenden Transpositions- und Schiebeoperationen gebildet. Gleichzeitig unterscheiden sich verschiedene Algorithmen zur transpositiven Verschiebung in der Art und Weise, wie sie ein Bitpaar für die Transposition und eine Gruppe von Bits für die Verschiebung auswählen. Diese Besonderheit wird im Folgenden für Transpositionsalgorithmen mit Links- und Rechtsverschiebung diskutiert. Im Transpositionsalgorithmus mit Linksverschiebung wird bei jedem Schritt die nächste Binärkombination aus der aktuellen erhalten, indem das am weitesten links stehende Ziffernpaar 01 durch 10 ersetzt wird (Transposition) und die Gruppe der führenden Einheitsziffern, falls vorhanden, in die Nähe der verschoben wird Paar 10 nach der Transposition (Verschiebung) erhalten. Wenn in diesem Fall keine Einheiten in den führenden Ziffern der aktuellen Binärkombination vorhanden sind, wird die Verschiebung nicht durchgeführt, selbst wenn die führende Einheit nach der Transposition in diesem Schritt erhalten wird. Die Verschiebung wird auch nicht durchgeführt, wenn in den höchstwertigen Bits vor dem nach der Transposition erhaltenen Paar 10 keine Nullen vorhanden sind. Die betrachteten Aktionen werden durch das folgende Beispiel der Durchführung zweier aufeinanderfolgender Iterationen dieses Algorithmus veranschaulicht, wobei bei einer Iteration (15) nur die Transposition (T") durchgeführt wird und bei der anderen Iteration (16) die Transposition durch eine Verschiebung ergänzt wird ( T"+S"): Beim Rechtsverschiebungs-Transpositionsalgorithmus werden bei jedem Schritt konzeptionell ähnliche Schritte ausgeführt. Nur die Transposition stellt sicher, dass die Bits ganz rechts von 01 durch 10 ersetzt werden (anstelle der Bits ganz links) und dann alle Bits rechts davon auf die niedrigstwertigen Bits verschoben werden. Nach wie vor wird die Verschiebung nur durchgeführt, wenn Einheiten vorhanden sind, die nach rechts verschoben werden können. Die betrachteten Aktionen werden durch das folgende Beispiel der Durchführung zweier aufeinanderfolgender Iterationen dieses Algorithmus veranschaulicht, wobei bei einer Iteration (3) nur eine Transposition (T") durchgeführt wird und bei der anderen Iteration (4) die Transposition durch eine Verschiebung ergänzt wird ( T"+S"): Es ist zu beachten, dass die Iterationen beider Algorithmen in additiver Form geschrieben werden können, wenn binäre Kombinationen als ganze Zahlen im Zahlensystem zur Basis 2 interpretiert werden. Insbesondere für den Transpositionsalgorithmus mit einer Rechtsverschiebung wird jede nächste binäre Kombination (B" n ,…B" j , …B" 1), kann immer aus der aktuellen Kombination (B n,…B j,…B 1) erhalten werden, indem die Operationen zum Addieren ganzer Zahlen mithilfe der folgenden Additionsformel ausgeführt werden: In dieser additiven Formel bezeichnen die Exponenten der Zweierpotenzen f und t jeweils die Anzahl der niederwertigen Nullstellen der aktuellen Binärkombination und die Anzahl der Einsen in einer Reihe links davon. Zum Beispiel für die 4. Binärkombination (001110) von n=6 Ziffern f =1 und t =3. Daher führt die Berechnung der nächsten Binärkombination mithilfe der Additivformel bei Iteration 5 zu dem folgenden Ergebnis, das der Durchführung der Transpositions- und Verschiebungsoperationen entspricht: Für eine vergleichende Analyse der betrachteten Transpositionsalgorithmen mit Links- und Rechtsverschiebungen empfiehlt es sich, die Folgen binärer Kombinationen zu vergleichen, die sie in ihren Iterationen erzeugen. Die folgende Tabelle zeigt zwei solcher Folgen binärer Kombinationen von 4 Elementen von 2, die durch die Links- (TSL) bzw. Rechtsverschiebungsalgorithmen (TSR) erhalten werden: Wenn man diese beiden Sequenzen vergleicht, erkennt man, dass es sich um umgekehrte Sequenzen handelt. Dies bedeutet, dass zwei beliebige Binärkombinationen, die sich in ihnen im gleichen Abstand von den einander gegenüberliegenden Enden ihrer Sequenzen befinden, ein Spiegelbild voneinander sind, das heißt, sie fallen zusammen, wenn die Indizierung der Bits in einer von ihnen umgekehrt ist. Beispielsweise ist das zweite binäre Muster vom Anfang der TSL-Sequenz (0101) ein Spiegelbild des binären Musters (1010), das am zweiten vom Ende der TSR-Sequenz liegt. Im Allgemeinen ist jede Binärkombination mit der Nummer i einer Sequenz ein Spiegelbild einer Binärkombination mit der Nummer (ni+1) einer anderen Sequenz. Diese Beziehung zwischen diesen Sequenzen ist eine Folge der symmetrischen Natur der Transpositions- und Verschiebungsoperationen in den beiden betrachteten Algorithmen zur Aufzählung binärer Kombinationen. Es ist zu beachten, dass das Binärformat auch zur Aufzeichnung von Kombinationen mit Wiederholungen von Elementen verwendet werden kann. Dazu ist es notwendig, eine Eins-zu-eins-Entsprechung zwischen Kombinationen mit Wiederholungen und Binärkombinationen herzustellen, die wie folgt aufgebaut sind. Es gebe eine beliebige Kombination mit Wiederholungen, die man erhält, indem man aus den n Elementen des Erzeugersatzes m optional unterschiedliche Elemente auswählt. Um die gewünschte Übereinstimmung herzustellen, müssen Sie zunächst alle Elemente des bildenden Satzes (cat) zur Kombination hinzufügen und dann die resultierende Verkettung sortieren (sortieren), sodass alle identischen Elemente nebeneinander liegen. Das Ergebnis ist eine Folge von (n+m) Elementen, wobei es n Gruppen identischer Elemente gibt. Es wird insgesamt (n+m1) Lücken zwischen Elementen geben, darunter (n1) Lücken zwischen Gruppen identischer Elemente und m Lücken zwischen Elementen innerhalb von Gruppen. Der Übersichtlichkeit halber können Sie die Symbole „|“ an den angegebenen Stellen platzieren. und entsprechend. Wenn wir nun den Leerzeichen zwischen den Gruppen (|) eine 1 und allen anderen Leerzeichen eine 0 zuordnen (), erhalten wir eine Binärkombination. Es besteht aus einem binären Satz von (n+m1) Bits, wobei (n1) Einsen und m Nullbits sind, deren Position eindeutig der ursprünglichen Kombination mit Wiederholungen der Elemente n bis m entspricht. Die betrachtete Transformationstechnik wird durch das folgende Beispiel der Konstruktion einer Binärkombination (1001101) unter Verwendung einer Kombination mit Wiederholungen (BBD) veranschaulicht, deren Elemente aus dem Erzeugungssatz der ersten fünf lateinischen Buchstaben ausgewählt werden: Im Allgemeinen bestimmt die Anzahl solcher Binärmengen die Anzahl der Möglichkeiten, (n1) Einsen (oder m Nullen) in (n+m1) Binärziffern anzuordnen. Dieser Wert ist offensichtlich gleich der Anzahl der Kombinationen von (n+m1) mal (n1) oder mal m, also C(n+m1,n1) oder C(n+m1,m), was gleich dem ist Anzahl der Kombinationen mit Wiederholungen f( n,m) von n Elementen, jeweils m. Da also eine Eins-zu-eins-Entsprechung zwischen Kombinationen mit Wiederholungen und Binärkombinationen vorliegt, ist es legitim, die Aufzählung von Kombinationen mit Wiederholungen auf die Aufzählung von Binärkombinationen zu reduzieren, beispielsweise durch die Verwendung von Transpositionsalgorithmen mit Links- oder Rechtsverschiebung. Danach müssen Sie nur noch die erforderlichen Kombinationen mit Wiederholungen mithilfe der resultierenden Binärkombinationen wiederherstellen. Dies kann jederzeit mithilfe der folgenden Wiederherstellungstechnik erfolgen. Die Hauptmenge, aus deren Elementen Kombinationen mit Wiederholungen von m nicht unbedingt unterschiedlichen Elementen gebildet werden, sei beliebig geordnet, so dass jedes ihrer Elemente eine bestimmte Seriennummer von 1 bis n hat. Implementieren wir auch die Aufzählung binärer Kombinationen von (n+m1) Binärziffern, wobei (n1) Einsen und m Nullziffern sind. Jede resultierende Binärkombination kann links um eine fiktive Einheitsziffer ergänzt werden, und alle Einheitsziffern können von links nach rechts mit ganzen Zahlen von 1 bis n nummeriert werden. Dann ist die Anzahl der Nullen in einer Zeile nach jeder i-ten Einheit der Binärkombination gleich der Anzahl der Instanzen des i-ten Elements der Hauptmenge in der entsprechenden Kombination mit Wiederholungen. Die betrachtete Technik wird durch das folgende Beispiel veranschaulicht, bei dem unter Verwendung einer Binärkombination (1001101) eine Kombination mit Wiederholungen von BBD wiederhergestellt wird, deren Elemente aus dem Erzeugungssatz der ersten fünf lateinischen Buchstaben in alphabetischer Reihenfolge ausgewählt werden , und der Überstrich zeigt Elemente an, die in dieser Kombination fehlen: Indem Sie ähnliche Aktionen unter den Bedingungen dieses Beispiels ausführen, können Sie alle 35 Binärkombinationen auflisten, die 7-Bit-Binärmengen bilden, in denen es 4 Einsen und 3 Nullen gibt, und die entsprechenden Kombinationen mit Wiederholungen von 5 Elementen von 3 wiederherstellen. In diesem Artikel werden wir über einen speziellen Zweig der Mathematik sprechen, der Kombinatorik genannt wird. Formeln, Regeln, Beispiele zur Problemlösung – all das finden Sie hier, indem Sie den Artikel bis zum Ende lesen. Was ist also dieser Abschnitt? Die Kombinatorik beschäftigt sich mit der Frage des Zählens beliebiger Objekte. Aber in diesem Fall handelt es sich bei den Objekten nicht um Pflaumen, Birnen oder Äpfel, sondern um etwas anderes. Kombinatorik hilft uns, die Wahrscheinlichkeit eines Ereignisses zu ermitteln. Wie hoch ist zum Beispiel beim Kartenspielen die Wahrscheinlichkeit, dass der Gegner eine Trumpfkarte hat? Oder dieses Beispiel: Wie hoch ist die Wahrscheinlichkeit, dass man aus einer Tüte mit zwanzig Murmeln eine weiße bekommt? Für diese Art von Problem müssen wir zumindest die Grundlagen dieses Teilgebiets der Mathematik kennen. Betrachtet man die Frage nach den Grundkonzepten und Formeln der Kombinatorik, kommt man nicht umhin, den kombinatorischen Konfigurationen Aufmerksamkeit zu schenken. Sie werden nicht nur zum Formulieren, sondern auch zum Lösen verschiedener Beispiele verwendet. Beispiele für solche Modelle sind: Wir werden später ausführlicher auf die ersten drei eingehen, konzentrieren uns in diesem Abschnitt jedoch auf die Zusammensetzung und Aufteilung. Wenn sie über die Zusammensetzung einer bestimmten Zahl (zum Beispiel a) sprechen, meinen sie die Darstellung der Zahl a als geordnete Summe bestimmter positiver Zahlen. Und eine Partition ist eine ungeordnete Summe. Bevor wir uns direkt den Formeln der Kombinatorik und der Problembetrachtung zuwenden, ist es erwähnenswert, dass die Kombinatorik, wie auch andere Zweige der Mathematik, eigene Unterabschnitte hat. Diese beinhalten: Im ersten Fall handelt es sich um rechnerische Kombinatorik; bei den Problemen geht es um die Aufzählung oder Zählung verschiedener Konfigurationen, die durch Elemente von Mengen gebildet werden. In der Regel unterliegen diese Mengen einigen Einschränkungen (Unterscheidbarkeit, Ununterscheidbarkeit, Wiederholungsmöglichkeit usw.). Und die Anzahl dieser Konfigurationen wird anhand der Additions- oder Multiplikationsregeln berechnet, über die wir etwas später sprechen werden. Die strukturelle Kombinatorik umfasst die Theorien von Graphen und Matroiden. Ein Beispiel für ein extremes kombinatorisches Problem ist die Frage nach der größten Dimension eines Graphen, der die folgenden Eigenschaften erfüllt ... Im vierten Absatz haben wir die Ramsey-Theorie erwähnt, die das Vorhandensein regelmäßiger Strukturen in zufälligen Konfigurationen untersucht. Die probabilistische Kombinatorik kann die Frage beantworten: Wie hoch ist die Wahrscheinlichkeit, dass eine bestimmte Menge eine bestimmte Eigenschaft hat? Wie Sie vielleicht erraten haben, wendet die topologische Kombinatorik Methoden in der Topologie an. Und schließlich der siebte Punkt: Die unendliche Kombinatorik untersucht die Anwendung kombinatorischer Methoden auf unendliche Mengen. Unter den Formeln der Kombinatorik finden sich recht einfache Formeln, mit denen wir schon seit längerem vertraut sind. Ein Beispiel ist die Summenregel. Angenommen, wir erhalten zwei Aktionen (C und E). Wenn sie sich gegenseitig ausschließen, kann Aktion C auf verschiedene Arten ausgeführt werden (z. B. a) und Aktion E kann auf b-Arten ausgeführt werden, dann ist jede davon ( C oder E) können auf a + b-Arten durchgeführt werden. Theoretisch ist das ziemlich schwer zu verstehen; wir werden versuchen, den ganzen Punkt anhand eines einfachen Beispiels zu vermitteln. Nehmen wir die durchschnittliche Anzahl der Schüler in einer Klasse – sagen wir, sie beträgt fünfundzwanzig. Unter ihnen sind fünfzehn Mädchen und zehn Jungen. Jeder Klasse ist täglich eine diensthabende Person zugeteilt. Wie viele Möglichkeiten gibt es heute, einen Klassensprecher zu ernennen? Die Lösung des Problems ist ganz einfach: Wir greifen auf die Additionsregel zurück. Im Problemtext heißt es nicht, dass nur Jungen oder nur Mädchen Dienst haben dürfen. Daher könnte es sich um eines der fünfzehn Mädchen oder einen der zehn Jungen handeln. Wenn wir die Summenregel anwenden, erhalten wir ein recht einfaches Beispiel, mit dem ein Grundschüler problemlos umgehen kann: 15 + 10. Nach dem Auszählen erhalten wir die Antwort: fünfundzwanzig. Das heißt, es gibt nur fünfundzwanzig Möglichkeiten, eine Klasse für den heutigen Tag einzuteilen. Zu den Grundformeln der Kombinatorik gehört auch die Multiplikationsregel. Beginnen wir mit der Theorie. Nehmen wir an, wir müssen mehrere Aktionen ausführen (a): Die erste Aktion wird auf eine Art und Weise ausgeführt, die zweite auf zwei Arten, die dritte auf drei Arten usw. bis zur letzten A-Aktion, die auf drei Arten ausgeführt wird. Dann können alle diese Aktionen (von denen wir eine Gesamtzahl haben) auf N Arten ausgeführt werden. Wie berechnet man das unbekannte N? Dabei hilft uns die Formel: N = c1 * c2 * c3 *…* ca. Auch hier ist theoretisch nichts klar, also schauen wir uns ein einfaches Beispiel für die Anwendung der Multiplikationsregel an. Nehmen wir dieselbe Klasse von 25 Personen, in der es fünfzehn Mädchen und zehn Jungen gibt. Nur dieses Mal müssen wir zwei diensthabende Personen auswählen. Es können nur Jungen oder Mädchen oder ein Junge und ein Mädchen sein. Kommen wir zur elementaren Lösung des Problems. Wir wählen die erste diensthabende Person aus, wie wir im letzten Absatz entschieden haben, wir erhalten fünfundzwanzig mögliche Optionen. Die zweite diensthabende Person kann eine beliebige der übrigen Personen sein. Wir hatten 25 Schüler, wir wählten einen aus, was bedeutet, dass der zweite Diensthabende jeder der übrigen 24 Personen sein konnte. Schließlich wenden wir die Multiplikationsregel an und stellen fest, dass zwei diensthabende Beamte auf sechshundert Arten gewählt werden können. Wir haben diese Zahl durch Multiplikation von fünfundzwanzig und vierundzwanzig erhalten. Jetzt schauen wir uns eine andere kombinatorische Formel an. In diesem Abschnitt des Artikels werden wir über Permutationen sprechen. Wir schlagen vor, das Problem sofort anhand eines Beispiels zu betrachten. Nehmen wir Billardkugeln, wir haben deren n-te Anzahl. Wir müssen zählen, wie viele Möglichkeiten es gibt, sie in einer Reihe anzuordnen, also eine geordnete Menge zu erstellen. Fangen wir an: Wenn wir keine Bälle haben, dann haben wir auch null Platzierungsmöglichkeiten. Und wenn wir eine Kugel haben, dann ist auch die Anordnung dieselbe (mathematisch lässt sich das wie folgt schreiben: P1 = 1). Die beiden Bälle können auf zwei verschiedene Arten platziert werden: 1,2 und 2,1. Daher ist P2 = 2. Drei Kugeln können auf sechs Arten angeordnet werden (P3 = 6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. Was wäre, wenn es nicht drei solcher Bälle wären, sondern zehn oder fünfzehn? Es würde sehr lange dauern, alle möglichen Optionen aufzulisten, dann kommt uns die Kombinatorik zu Hilfe. Die Permutationsformel hilft uns, die Antwort auf die Frage zu finden, die uns interessiert. Pn = n * P (n-1). Wenn wir versuchen, die Formel zu vereinfachen, erhalten wir: Pn = n* (n - 1) *…* 2 * 1. Und das ist das Produkt der ersten natürlichen Zahlen. Diese Zahl wird Fakultät genannt und mit n! bezeichnet. Betrachten wir das Problem. Jeden Morgen stellt der Berater seine Truppe (zwanzig Leute) auf. Es gibt drei beste Freunde im Kader – Kostya, Sasha und Lesha. Wie groß ist die Wahrscheinlichkeit, dass sie nebeneinander stehen? Um die Antwort auf die Frage zu finden, müssen Sie die Wahrscheinlichkeit eines „guten“ Ergebnisses durch die Gesamtzahl der Ergebnisse dividieren. Die Gesamtzahl der Permutationen beträgt 20! = 2,5 Trillionen. Wie zählt man die Anzahl der „guten“ Ergebnisse? Nehmen wir an, dass Kostya, Sasha und Lesha ein Übermensch sind. Dann haben wir nur achtzehn Fächer. Die Anzahl der Permutationen beträgt in diesem Fall 18 = 6,5 Billiarden. Mit all dem können sich Kostya, Sasha und Lesha in ihrer unteilbaren Drei beliebig untereinander bewegen, und das sind noch drei! = 6 Optionen. Damit haben wir insgesamt 18 „gute“ Arrangements! * 3! Wir müssen lediglich die gewünschte Wahrscheinlichkeit finden: (18! * 3!) / 20! Das entspricht ungefähr 0,016. In Prozent umgerechnet sind es nur 1,6 %. Jetzt werden wir uns eine weitere sehr wichtige und notwendige Formel der Kombinatorik ansehen. Die Platzierung ist unser nächstes Thema, mit dem wir Sie in diesem Abschnitt des Artikels befassen möchten. Wir rechnen mit Komplikationen. Angenommen, wir möchten mögliche Permutationen berücksichtigen, nicht aus der gesamten Menge (n), sondern aus einer kleineren Menge (m). Das heißt, wir betrachten Permutationen von n Elementen durch m. Die Grundformeln der Kombinatorik sollten nicht nur auswendig gelernt, sondern verstanden werden. Auch wenn sie komplizierter werden, da wir nicht einen, sondern zwei Parameter haben. Angenommen, m = 1, dann A = 1, m = 2, dann A = n * (n - 1). Wenn wir die Formel weiter vereinfachen und auf die Notation mit Fakultäten umsteigen, erhalten wir eine völlig lakonische Formel: A = n! / (n - m)! Wir haben fast alle grundlegenden Formeln der Kombinatorik anhand von Beispielen überprüft. Kommen wir nun zur letzten Phase der Betrachtung des Grundkurses Kombinatorik – dem Kennenlernen von Kombinationen. Jetzt werden wir m Elemente aus den n Elementen auswählen, die wir haben, und wir werden alles auf jede erdenkliche Weise auswählen. Wie unterscheidet sich das dann von der Platzierung? Wir werden die Bestellung nicht berücksichtigen. Diese ungeordnete Menge wird die Kombination sein. Lassen Sie uns sofort die Notation einführen: C. Wir nehmen die Platzierung von m Bällen aus n. Wir achten nicht mehr auf die Reihenfolge und es kommt zu immer wiederkehrenden Kombinationen. Um die Anzahl der Kombinationen zu erhalten, müssen wir die Anzahl der Platzierungen durch m dividieren! (m Fakultät). Das heißt, C = A / m! Somit gibt es nur wenige Möglichkeiten, aus n Bällen auszuwählen, was ungefähr der Anzahl der Möglichkeiten entspricht, fast alle auszuwählen. Dafür gibt es einen logischen Ausdruck: Wenig auszuwählen ist dasselbe, als würde man fast alles wegwerfen. Wichtig ist an dieser Stelle auch zu erwähnen, dass die maximale Kombinationszahl erreicht werden kann, wenn versucht wird, die Hälfte der Artikel auszuwählen. Wir haben die Grundformeln der Kombinatorik im Detail untersucht: Platzierung, Permutation und Kombination. Unsere Aufgabe besteht nun darin, die Auswahl der notwendigen Formel zur Lösung eines kombinatorischen Problems zu erleichtern. Sie können das folgende recht einfache Schema verwenden: Wir haben uns Elemente der Kombinatorik, Formeln und einige andere Themen angesehen. Kommen wir nun zum eigentlichen Problem. Stellen Sie sich vor, Sie haben eine Kiwi, eine Orange und eine Banane vor sich. Frage eins: Auf wie viele Arten können sie neu angeordnet werden? Dazu verwenden wir die Permutationsformel: P = 3! = 6 Wege. Frage zwei: Auf wie viele Arten kann man eine Frucht auswählen? Das ist klar, wir haben nur drei Möglichkeiten – wählen Sie Kiwi, Orange oder Banane, aber wenden wir die Kombinationsformel an: C = 3! / (2! * 1!) = 3. Frage drei: Auf wie viele Arten kann man zwei Früchte auswählen? Welche Möglichkeiten haben wir überhaupt? Kiwi und Orange; Kiwi und Banane; Orange und Banane. Das heißt, es gibt drei Möglichkeiten, aber das lässt sich leicht mit der Kombinationsformel überprüfen: C = 3! / (1! * 2!) = 3 Frage vier: Auf wie viele Arten kann man drei Früchte auswählen? Wie Sie sehen, gibt es nur eine Möglichkeit, drei Früchte auszuwählen: Kiwi, Orange und Banane. C = 3! / (0! * 3!) = 1. Frage fünf: Auf wie viele Arten kann man mindestens eine Frucht auswählen? Diese Bedingung bedeutet, dass wir eine, zwei oder alle drei Früchte nehmen können. Daher addieren wir C1 + C2 + C3 = 3 + 3 + 1 = 7. Das heißt, wir haben sieben Möglichkeiten, mindestens eine Frucht vom Tisch zu nehmen. Manchmal treffen wir eine Auswahl aus vielen ohne Rücksicht auf die Reihenfolge. Diese Wahl heißt Kombination
. Wenn Sie beispielsweise Karten spielen, wissen Sie, dass die Reihenfolge, in der Sie die Karten halten, in den meisten Situationen keine Rolle spielt. Beispiel 1 Finden Sie alle Kombinationen von 3 Buchstaben aus einem Satz von 5 Buchstaben (A, B, C, D, E). Lösung Diese Kombinationen sind wie folgt: Wenn wir alle Kombinationen aus einer Menge mit 5 Objekten finden und 3 Objekte gleichzeitig nehmen, finden wir alle 3-Element-Teilmengen. In diesem Fall wird die Reihenfolge der Objekte nicht berücksichtigt. Dann, Teilmenge Die Elemente der Teilmenge sind nicht geordnet. Bei Kombinationen wird die Reihenfolge nicht berücksichtigt! Kombination Wir wollen eine Formel aufschreiben, um die Anzahl der Kombinationen von n Objekten zu berechnen, wenn k Objekte gleichzeitig genommen werden. Kombinationsbezeichnungen Wir nennen n C k Anzahl der Kombinationen
. Wir wollen eine allgemeine Formel für n C k für jedes k ≤ n aufschreiben. Erstens gilt n C n = 1, da eine Menge mit n Elementen nur eine Teilmenge mit n Elementen hat, nämlich die Menge selbst. Zweitens ist n C 1 = n, weil eine Menge mit n Elementen nur n Teilmengen mit jeweils 1 Element hat. Schließlich ist n C 0 = 1, weil eine Menge mit n Elementen nur eine Teilmenge mit 0 Elementen hat, also die leere Menge ∅. Um uns andere Kombinationen anzusehen, kehren wir zu Beispiel 1 zurück und vergleichen die Anzahl der Kombinationen mit der Anzahl der Permutationen. Bitte beachten Sie, dass jede Kombination aus 3 Elementen 6 bzw. 3! Permutationen hat. Kombinationen von k Objekten aus n Objekten Eine andere Art der Notation für n C k ist Binomialkoeffizient
. Der Grund für diese Terminologie wird im Folgenden klar werden. Binominalkoeffizient Beispiel 2 Berechnen Sie mit den Formeln (1) und (2). Lösung Bedenken Sie, dass n/k nicht bedeutet. Beispiel 3 Berechnen und . Lösung Wir verwenden Formel (1) für den ersten Ausdruck und Formel (2) für den zweiten. Dann beachten Sie, dass Teilmengen von Größe k und Größe Jetzt werden wir Probleme mit Kombinationen lösen. Beispiel 4 Michigan-Lotterie.
Michigans zweimal wöchentlich stattfindende Lotterie WINFALL hat einen Jackpot von mindestens 2 Millionen US-Dollar. Für einen Dollar kann ein Spieler sechs beliebige Zahlen von 1 bis 49 durchstreichen. Wenn diese Zahlen mit den im Lotto gezogenen Zahlen übereinstimmen, gewinnt der Spieler. ( In der Kombinatorik untersuchen sie Fragen dazu, wie viele Kombinationen eines bestimmten Typs aus gegebenen Objekten (Elementen) hergestellt werden können. Die Geburt der Kombinatorik als Zweig ist mit den Arbeiten von B. Pascal und P. Fermat zur Theorie des Glücksspiels verbunden. Einen großen Beitrag zur Entwicklung kombinatorischer Methoden leistete G.V. Leibniz, J. Bernoulli und L. Euler. Der französische Philosoph, Schriftsteller, Mathematiker und Physiker Blaise Pascal (1623–1662) zeigte schon früh seine herausragenden mathematischen Fähigkeiten. Pascals Spektrum an mathematischen Interessen war sehr vielfältig. Pascal hat eines bewiesen Gottfried Wilhelm Leibniz (1646–1716) war ein deutscher Philosoph, Mathematiker, Physiker und Erfinder, Anwalt, Historiker und Sprachwissenschaftler. In der Mathematik entwickelte er zusammen mit I. Newton die Differential- und Integralrechnung. Er leistete wichtige Beiträge zur Kombinatorik. Insbesondere sein Name ist mit zahlentheoretischen Problemen verbunden. Gottfried Wilhelm Leibniz hatte wenig beeindruckendes Äußeres und machte daher den Eindruck eines eher unscheinbaren Menschen. Eines Tages ging er in Paris in einen Buchladen in der Hoffnung, ein Buch eines Philosophen zu kaufen, den er kannte. Als ein Besucher nach diesem Buch fragte, sagte der Buchhändler, nachdem er ihn von Kopf bis Fuß untersucht hatte, spöttisch: „Warum brauchen Sie es?“ Sind Sie wirklich in der Lage, solche Bücher zu lesen?“ Bevor der Wissenschaftler antworten konnte, betrat der Autor des Buches selbst den Laden mit den Worten: „Grüße und Respekt an den großen Leibniz!“ Der Verkäufer konnte nicht verstehen, dass es sich tatsächlich um den berühmten Leibniz handelte, dessen Bücher bei Wissenschaftlern sehr gefragt waren. Folgendes wird in Zukunft eine wichtige Rolle spielen Lemma. Lassen Sie eine Menge von Elementen und in einer Menge Elemente ein. Dann ist die Anzahl aller unterschiedlichen Paare gleich. Nachweisen. Tatsächlich können wir mit einem Element aus einer Menge so unterschiedliche Paare bilden, und zwar insgesamt in einer Menge von Elementen. Platzierungen, Permutationen, Kombinationen Lassen Sie uns eine Menge von drei Elementen haben. Auf welche Weise können wir zwei dieser Elemente auswählen? . Definition. Anordnungen einer Menge verschiedener Elemente nach Elementen sind Kombinationen, die aus gegebenen Elementen nach > Elementen bestehen und sich entweder in den Elementen selbst oder in der Reihenfolge der Elemente unterscheiden. Die Anzahl aller Anordnungen einer Menge von Elementen nach Elementen wird mit (aus dem Anfangsbuchstaben des französischen Wortes „arrangement“, was Anordnung bedeutet) bezeichnet, wobei und . Satz. Die Anzahl der Platzierungen einer Menge von Elementen nach Elementen ist gleich Nachweisen. Nehmen wir an, wir haben Elemente. Lassen Sie mögliche Platzierungen sein. Wir werden diese Platzierungen nacheinander aufbauen. Definieren wir zunächst das erste Platzierungselement. Aus einer gegebenen Menge von Elementen kann es auf verschiedene Weise ausgewählt werden. Nach Auswahl des ersten Elements gibt es noch Möglichkeiten, das zweite Element usw. auszuwählen. Da jede dieser Wahlmöglichkeiten eine neue Platzierung ergibt, können alle diese Wahlmöglichkeiten frei miteinander kombiniert werden. Deshalb haben wir: Beispiel. Auf wie viele Arten kann eine Flagge aus drei horizontalen Streifen unterschiedlicher Farbe bestehen, wenn Material in fünf Farben vorhanden ist? Lösung. Die erforderliche Anzahl an Dreiband-Flaggen: Definition. Permutation einer Menge von Elementen ist die Anordnung von Elementen in einer bestimmten Reihenfolge. Somit sind alle unterschiedlichen Permutationen einer Menge von drei Elementen Angegeben ist die Anzahl aller Permutationen von Elementen (vom Anfangsbuchstaben des französischen Wortes „Permutation“, was „Permutation“, „Bewegung“ bedeutet). Daher wird die Anzahl aller verschiedenen Permutationen durch die Formel berechnet Beispiel. Auf wie viele Arten können die Türme auf dem Schachbrett platziert werden, damit sie sich nicht gegenseitig angreifen? Lösung. Die erforderliche Anzahl Türme A-Priorat! Definition. Kombinationen verschiedener Elemente nach Elementen sind Kombinationen, die aus bestimmten Elementen nach Elementen bestehen und sich in mindestens einem Element unterscheiden (mit anderen Worten, Element-Teilmengen einer bestimmten Menge von Elementen). Wie Sie sehen, wird bei Kombinationen im Gegensatz zu Platzierungen die Reihenfolge der Elemente nicht berücksichtigt. Die Anzahl aller Kombinationen von Elementen, jeweils der Elemente, wird angegeben (vom Anfangsbuchstaben des französischen Wortes „combinasion“, was „Kombination“ bedeutet). Zahlen Alle Kombinationen aus einem Zweierset sind . Eigenschaften von Zahlen (\sf C)_n^k Tatsächlich entspricht jede Element-Teilmenge einer gegebenen Element-Menge einer und nur einer Element-Teilmenge derselben Menge. Tatsächlich können wir Teilmengen von Elementen auf folgende Weise auswählen: ein Element fixieren; die Anzahl der Element-Teilmengen, die dieses Element enthalten, ist gleich; Die Anzahl der Element-Teilmengen, die dieses Element nicht enthalten, ist gleich. Pascals Dreieck In diesem Dreieck sind die extremen Zahlen in jeder Zeile gleich 1 und jede nicht extreme Zahl ist gleich der Summe der beiden darüber liegenden Zahlen aus der vorherigen Zeile. Somit können Sie mit diesem Dreieck Zahlen berechnen. Satz. Nachweisen. Betrachten wir eine Menge von Elementen und lösen wir das folgende Problem auf zwei Arten: Wie viele Sequenzen können aus den Elementen eines gegebenen Elements erstellt werden? 1 Weg. Wir wählen das erste Mitglied der Sequenz aus, dann das zweite, dritte usw. Mitglied Methode 2. Wählen wir zunächst Elemente aus einer bestimmten Menge aus und ordnen sie dann in einer bestimmten Reihenfolge an Multiplizieren Sie Zähler und Nenner dieses Bruchs mit: Beispiel. Auf wie viele Arten kann man im Spiel „Sportloto“ 5 von 36 Zahlen wählen? Erforderliche Anzahl an Wegen Aufgaben. 1.
Autokennzeichen bestehen aus 3 Buchstaben des russischen Alphabets (33 Buchstaben) und 4 Zahlen. Wie viele verschiedene Kennzeichen gibt es? Partitionen gelten als unterschiedlich, wenn sie sich entweder in der Anzahl oder in der Reihenfolge ihrer Begriffe unterscheiden. Wie viele verschiedene Zerlegungen einer Zahl in Terme gibt es? Kombinatorische Konfigurationen
Abschnitte
Additionsregel
Multiplikationsregel
Neuordnung
Unterkunft
Kombination
Wie wählt man eine Formel zur Lösung eines Problems?
Beispiel
(A, B, C), (A, B, D),
(A, B, E), (A, C, D),
(A, C, E), (A, D, E),
(B, C, D), (B, C, E),
(B, D, E), (C, D, E).
Es gibt 10 Kombinationen von drei Buchstaben, die aus fünf Buchstaben ausgewählt werden können.
(A, C, B) heißt die gleiche Menge wie (A, B, C).
Eine Menge A ist eine Teilmenge von B, was bedeutet, dass A eine Teilmenge von und/oder dasselbe wie B ist, wenn jedes Element von A ein Element von B ist.
Kombination,
mit k Objekten ist eine Teilmenge, die aus k Objekten besteht.
Die Anzahl der Kombinationen von n Objekten, wenn k Objekte gleichzeitig genommen werden, wird mit n C k bezeichnet.
3! . 5 C 3 = 60 = 5 P 3 = 5. 4 . 3,
Also 
.
Im Allgemeinen muss die Anzahl der Kombinationen von k Elementen, die aus n Objekten ausgewählt werden, n C k mal Permutationen dieser Elemente k!, gleich der Anzahl der Permutationen von n Elementen durch k Elemente sein:
k!. n C k = n P k
n C k = n P k /k!
n C k = (1/k!). n P k
n C k = 
Die Gesamtzahl der Kombinationen von k Elementen aus n Objekten wird mit n C k bezeichnet, bestimmt durch
(1) n C k = ,
oder
(2) n C k = 
a) Gemäß (1), 
.
b) Gemäß (2), 
,
unter Verwendung von (1) und 
,
unter Verwendung der Formel (2).
,
und wenn wir das Ergebnis von Beispiel 2 verwenden, erhalten wir
.
Daraus folgt, dass die Anzahl einer 5-elementigen Teilmenge einer Menge von 7 Elementen dieselbe ist wie die Anzahl einer 2-elementigen Teilmenge einer Menge von 7 Elementen. Wenn 5 Elemente aus einem Satz ausgewählt werden, enthalten sie keine 2 Elemente. Um dies zu sehen, betrachten Sie die Menge (A, B, C, D, E, F, G): 
Im Allgemeinen haben wir Folgendes. Dieses Ergebnis bietet eine alternative Möglichkeit zur Berechnung der Kombination.
und n C k = n C n-k
Die Anzahl der Teilmengen der Größe k einer Menge mit n Objekten ist gleich der Anzahl der Teilmengen der Größe n - k. Die Anzahl der Kombinationen von k Objekten aus einer Menge von n Objekten ist gleich der Anzahl der Kombinationen von n gleichzeitig aufgenommene Objekte.
aus den Grundsätzen der projektiven Geometrie (Satz von Pascal), entwarf eine Summiermaschine (Additionsmaschine von Pascal), gab eine Methode zur Berechnung von Binomialkoeffizienten (Pascals Dreieck) an, war der erste, der die Methode der mathematischen Induktion zum Beweis genau definierte und anwendete, machte einen bedeutenden Schritt in der Entwicklung der Infinitesimalanalyse und spielte eine wichtige Rolle bei der Entstehung der Wahrscheinlichkeitstheorie. In der Hydrostatik hat Pascal ihr Grundgesetz (Pascalsches Gesetz) aufgestellt. Pascals „Briefe an einen Provinzial“ waren ein Meisterwerk der klassischen französischen Prosa.
Mengen, in denen jeweils kein Element zweimal vorkommt?
2.
Das Klavier verfügt über 88 Tasten. Auf wie viele Arten kann man 6 Töne hintereinander erzeugen?
3.
Wie viele sechsstellige Zahlen gibt es, die durch 5 teilbar sind?
4.
Auf wie viele Arten können 7 verschiedene Münzen in drei Taschen gesteckt werden?
5.
Wie viele fünfstellige Zahlen können Sie erstellen, in deren Dezimalschreibweise die Ziffer 5 mindestens einmal vorkommt?
6.
Auf wie viele Arten können 20 Personen an einem runden Tisch sitzen, wenn man davon ausgeht, dass die Möglichkeiten gleich sind, wenn sie durch Bewegung im Kreis voneinander erhalten werden können?
7.
Wie viele fünfstellige Zahlen gibt es, die durch 5 teilbar sind und keine identischen Ziffern enthalten?
8.
Auf kariertem Papier mit einer Zellenseite von 1 cm wird ein Kreis mit einem Radius von 100 cm gezeichnet, der nicht durch die Oberseite der Zellen geht und die Seiten der Zellen nicht berührt. Wie viele Zellen kann dieser Kreis schneiden?
9.
Auf wie viele Arten können Zahlen in einer Reihe angeordnet werden, sodass die Zahlen nebeneinander und in aufsteigender Reihenfolge liegen?
10.
Wie viele fünfstellige Zahlen können aus Ziffern gebildet werden, wenn jede Ziffer nur einmal verwendet werden kann?
11.
Aus dem Wort ROT können Sie durch Umordnen der Buchstaben die folgenden Wörter erhalten: TOP, ORT, OTR, TRO, RTO. Sie werden Anagramme genannt. Wie viele Anagramme kann man aus dem Wort LOGARITHMUS bilden?
12.
Lass uns anrufen Spaltung natürliche Zahl, ihre Darstellung als Summe natürlicher Zahlen. Hier sind zum Beispiel alle Partitionen einer Zahl:
13.
Wie viele dreistellige Zahlen gibt es mit nicht aufsteigender Ziffernreihenfolge?
14.
Wie viele vierstellige Zahlen gibt es mit nicht aufsteigender Ziffernreihenfolge?
15.
Auf wie viele Arten können 17 Personen in einer Reihe sitzen, sodass sie am Ende nebeneinander sitzen?
16.
Mädchen und Jungen sitzen zufällig in einer Sitzreihe. Auf wie viele Arten können sie sitzen, damit keine zwei Mädchen nebeneinander sitzen?
17.
Mädchen und Jungen sitzen zufällig in einer Sitzreihe. Auf wie viele Arten können sie sitzen, sodass alle Mädchen nebeneinander sitzen?
