In der Mathematik wird der Begriff der Versetzung mit mehreren ein bisschen verschiedenen Bedeutungen, alle verwendet, die mit der Tat verbunden sind, (Umordnen) Gegenstände oder Werte zu permutieren. Informell ist eine Versetzung von einer Reihe von Gegenständen eine Einordnung jener Gegenstände in eine besondere Ordnung. Zum Beispiel gibt es sechs Versetzungen des Satzes {1,2,3}, nämlich (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), und (3,2,1). Man könnte ein Anagramm eines Wortes als eine Versetzung seiner Briefe definieren. Die Studie von Versetzungen in diesem Sinn gehört allgemein dem Feld von combinatorics.

Die Zahl von Versetzungen von n verschiedenen Gegenständen ist, welche Zahl "n factorial" genannt und "n geschrieben wird!".

Versetzungen kommen auf mehr oder weniger prominente Weisen auf fast jedes Gebiet der Mathematik vor. Sie entstehen häufig, wenn die verschiedene Einrichtung auf bestimmten begrenzten Sätzen vielleicht betrachtet wird, nur weil man solche Einrichtung ignorieren will und wissen muss, wie viele Konfigurationen so identifiziert werden. Aus ähnlichen Gründen entstehen Versetzungen in der Studie, Algorithmen in der Informatik zu sortieren.

In der Algebra und besonders in der Gruppentheorie wird eine Versetzung eines Satzes S als eine Bijektion von S bis sich definiert (d. h., eine Karte, für die jedes Element von S genau einmal als Bildwert vorkommt). Das ist mit der Neuordnung von S verbunden, in dem jedes Element s den Platz des entsprechenden f (s) nimmt. Die Sammlung solcher Versetzungen bildet eine symmetrische Gruppe. Der Schlüssel zu seiner Struktur ist die Möglichkeit, Versetzungen zusammenzusetzen: Das Durchführen von zwei gegebenen Neuordnungen in der Folge definiert eine dritte Neuordnung, die Zusammensetzung. Versetzungen können zerlegbaren Gegenständen durch das Umordnen ihrer Bestandteile, oder durch den bestimmten Ersatz (Ersetzungen) von Symbolen folgen.

In elementarem combinatorics bezieht sich der Name "Versetzungen und Kombinationen" auf zwei zusammenhängende Probleme, beide Zählen-Möglichkeiten, k verschiedene Elemente von einer Reihe von n Elementen auszuwählen, wo für K-Versetzungen die Ordnung der Auswahl in Betracht gezogen wird, aber für K-Kombinationen wird es ignoriert. Jedoch entsprechen K-Versetzungen Versetzungen, wie besprochen, in diesem Artikel (wenn k = n) nicht.

Geschichte

Die Regel, die Zahl von Versetzungen von N-Gegenständen zu bestimmen, war in der hinduistischen Kultur mindestens schon in ungefähr 1150 bekannt: Lilavati durch den Indianermathematiker Bhaskara II enthält einen Durchgang, der zu übersetzt

Das Produkt der Multiplikation des arithmetischen Reihe-Anfangs und Erhöhung durch die Einheit und hat zur Zahl von Plätzen weitergegangen, wird die Schwankungen der Zahl mit spezifischen Zahlen sein.

Ein erster Fall, in dem mathematische Fragen anscheinend ohne Beziehung mit der Hilfe von Versetzungen studiert wurden, ist 1770 vorgekommen, als Joseph Louis Lagrange, in der Studie von polynomischen Gleichungen, bemerkt hat, dass Eigenschaften der Versetzungen der Wurzeln einer Gleichung mit den Möglichkeiten verbunden sind, es zu lösen. Diese Linie der Arbeit hat schließlich durch die Arbeit von Évariste Galois in der Theorie von Galois resultiert, die eine ganze Beschreibung dessen gibt, was möglich und in Bezug auf das Lösen polynomischer Gleichungen (in einem unbekanntem) durch Radikale unmöglich ist. In der modernen Mathematik gibt es viele ähnliche Situationen, in denen das Verstehen eines Problems studierende bestimmte damit verbundene Versetzungen verlangt.

Allgemeinheiten

Der Begriff der Versetzung wird in den folgenden Zusammenhängen verwendet.

In der Gruppentheorie

In der Gruppentheorie und den verwandten Gebieten denkt man Versetzungen von willkürlichen Sätzen, sogar unendlichen. Eine Versetzung eines Satzes S ist eine Bijektion von S bis sich. Das berücksichtigt zusammenzusetzende Versetzungen, der die Definition von Gruppen von Versetzungen erlaubt. Wenn S ein begrenzter Satz von n Elementen ist, dann gibt es n! Versetzungen von S.

In combinatorics

In combinatorics, wie man gewöhnlich versteht, ist eine Versetzung eine Folge, die jedes Element von einem begrenzten Satz einmal, und nur einmal enthält. Das Konzept der Folge ist von diesem eines Satzes, darin verschieden die Elemente einer Folge erscheinen in einer Ordnung: Die Folge hat ein erstes Element (wenn es nicht leer ist), ein zweites Element (wenn seine Länge weniger als 2 nicht ist), und so weiter. Im Gegensatz haben die Elemente in einem Satz keine Ordnung; {1, 2, 3} und {3, 2, 1} sind verschiedene Weisen, denselben Satz anzuzeigen. In diesem Sinn ist eine Versetzung eines begrenzten Satzes S n Elemente zu einer Bijektion von {1, 2..., n} zu S gleichwertig (in dem irgendwelcher ich zum i-th Element der Folge kartografisch dargestellt werde), oder zu einer Wahl einer Gesamteinrichtung auf S (für der, wenn x vorher y in der Folge kommt). In diesem Sinn gibt es auch n! Versetzungen von S.

Es gibt auch eine schwächere Bedeutung des Begriffes "Versetzung", die manchmal in elementaren combinatorics Texten verwendet wird, jene Folgen benennend, in denen kein Element mehr vorkommt als einmal, aber ohne die Voraussetzung, um alle Elemente von einem gegebenen Satz zu verwenden. Tatsächlich ist dieser Gebrauch häufig mit dem Betrachten von Folgen einer festen Länge k Elemente verbunden, die von einem gegebenen Satz der Größe n genommen sind. Diese Gegenstände sind auch bekannt als Folgen ohne Wiederholung, ein Begriff, der Verwirrung mit dem anderen, üblicher, Bedeutungen "der Versetzung" vermeidet. Die Zahl solcher K-Versetzungen von n wird verschiedenartig durch solche Symbole wie P, P, P, oder P (n, k) angezeigt, und sein Wert wird durch das Produkt gegeben

:

der 0 ist, wenn, und sonst gleich

ist:

Das Produkt wird ohne die Annahme gut definiert, dass n eine natürliche Zahl ist, und draußen combinatorics ebenso wichtig ist; es ist als das Symbol von Pochhammer (n) oder als der k-th bekannt, der factorial Macht n n fällt.

Wenn M ein begrenzter Mehrsatz ist, dann ist eine Mehrsatz-Versetzung eine Folge von Elementen der M, in der jedes Element genau so häufig erscheint, wie seine Vielfältigkeit in der M ist. Wenn die Vielfältigkeit der Elemente der M (genommen in einer Ordnung) ist..., und ihre Summe (d. h., die Größe von M) n ist, dann wird die Zahl von Mehrsatz-Versetzungen der M durch den multinomial Koeffizienten gegeben

:

Versetzungen in der Gruppentheorie

In der Gruppentheorie bedeutet der Begriff Versetzung eines Satzes eine bijektive Karte oder Bijektion, von diesem Satz auf sich. Der Satz aller Versetzungen jedes gegebenen ist untergegangen S bildet eine Gruppe, mit der Zusammensetzung von Karten als Produkt und die Identität als neutrales Element. Das ist die symmetrische Gruppe von S. Bis zum Isomorphismus hängt diese symmetrische Gruppe nur vom cardinality des Satzes ab, so ist die Natur von Elementen von S für die Struktur der Gruppe irrelevant. Symmetrische Gruppen sind am meisten im Fall von begrenzte Sätze studiert worden, in welchem Fall man ohne Verlust der Allgemeinheit annehmen kann, dass S = {1,2..., n} für eine natürliche Zahl n, der die symmetrische Gruppe des Grads n, schriftlich definiert.

Jede Untergruppe einer symmetrischen Gruppe wird eine Versetzungsgruppe genannt. Tatsächlich durch den Lehrsatz von Cayley ist jede Gruppe zu einer Versetzungsgruppe und jeder begrenzten Gruppe zu einer Untergruppe von einer begrenzten symmetrischen Gruppe isomorph. Jedoch haben Versetzungsgruppen mehr Struktur als abstrakte Gruppen, zum Beispiel erlaubend, den Zyklus-Typ eines Elements einer Versetzungsgruppe zu definieren; verschiedene Verwirklichungen einer Gruppe als eine Versetzungsgruppe brauchen für diese zusätzliche Struktur nicht gleichwertig zu sein. Zum Beispiel ist natürlich eine Versetzungsgruppe, in der jede Umstellung Zyklus-Typ (2,1) hat, aber der Beweis des Lehrsatzes von Cayley begreift als eine Untergruppe dessen (nämlich die Versetzungen der 6 Elemente von sich), in dem Versetzungsgruppenumstellungen Zyklus-Typ (2,2,2) bekommen. So trotz des Lehrsatzes von Cayley unterscheidet sich die Studie von Versetzungsgruppen von der Studie von abstrakten Gruppen.

Notation

Es gibt drei Hauptnotationen für Versetzungen eines begrenzten Satzes S. In der Zwei-Linien-Notation von Cauchy verzeichnet man die Elemente von S in der ersten Reihe, und für jedes sein Image unter der Versetzung darunter in der zweiten Reihe. Zum Beispiel kann eine besondere Versetzung des Satzes {1,2,3,4,5} als geschrieben werden:

:

1 & 2 & 3 & 4 & 5 \\

2 & 5 & 4 & 3 & 1\end {pmatrix}; </Mathematik>

das bedeutet, dass σ σ (1) =2, σ (2) =5, σ (3) =4, σ (4) =3 und σ (5) =1 befriedigt.

In der Fachnotation gibt man nur die zweite Reihe dieser Reihe, so ist die Fachnotation für die Versetzung oben 25431. (Es ist typisch, um Kommas zu verwenden, um diese Einträge nur zu trennen, wenn einige zwei oder mehr Ziffern haben.)

Zyklus-Notation, die dritte Methode der Notation, konzentriert sich auf die Wirkung, nacheinander die Versetzung anzuwenden. Es drückt die Versetzung als ein Produkt von Zyklen entsprechend den Bahnen (mit mindestens zwei Elementen) der Versetzung aus; da verschiedene Bahnen zusammenhanglos sind, wird das lose "die Zergliederung in zusammenhanglose Zyklen" der Versetzung genannt. Es arbeitet wie folgt: Von einem Element x S mit anfangend, schreibt man die Folge (x σ (x) σ (σ (x))...) aufeinander folgender Images unter σ bis würde das Image x sein, an dem Punkt man stattdessen die Parenthese schließt. Der Satz von Werten niedergeschriebene Formen die Bahn (unter σ) x und des parenthesized Ausdrucks gibt den entsprechenden Zyklus von σ. Man setzt dann fort, ein Element y S zu wählen, der nicht in der Bahn bereits niedergeschrieben und solch ist, dass, und den entsprechenden Zyklus und so weiter niederschreibt, bis alle Elemente von S entweder einem Zyklus niedergeschrieben gehören oder befestigte Punkte von σ sind. Seitdem für jeden neuen Zyklus kann der Startpunkt unterschiedlich gewählt werden, es gibt im Allgemeinen viele verschiedene Zyklus-Notationen für dieselbe Versetzung; für das Beispiel oben hat man zum Beispiel

:

2 & 5 & 4 & 3 & 1\end {pmatrix} = \begin {pmatrix} 1 & 2 & 5 \end {pmatrix} \begin {pmatrix} 3 & 4 \end {pmatrix} = \begin {pmatrix} 3 & 4 \end {pmatrix} \begin {pmatrix} 1 & 2 & 5 \end {pmatrix} = \begin {pmatrix} 3 & 4 \end {pmatrix} \begin {pmatrix} 5 & 1 & 2 \end {pmatrix}. </Mathematik>

Jeder Zyklus (x x... x) σ zeigt eine Versetzung in seinem eigenen Recht, nämlich dasjenige an, das dieselben Werte wie σ auf dieser Bahn nimmt (so stellt es x zu x für und x zu x kartografisch dar), während man alle anderen Elemente von S zu sich kartografisch darstellt. Die Größe l der Bahn wird die Länge des Zyklus genannt. Verschiedene Bahnen von σ sind definitionsgemäß zusammenhanglos, so, wie man leicht sieht, pendeln die entsprechenden Zyklen, und σ das Produkt seiner Zyklen (genommen in jeder Ordnung) ist. Deshalb kann die Verkettung von Zyklen in der Zyklus-Notation als Bezeichnung der Zusammensetzung von Versetzungen, woher der Name "Zergliederung" der Versetzung interpretiert werden. Diese Zergliederung ist im Wesentlichen einzigartig: Abgesondert von der Umstellung die Zyklen im Produkt gibt es keine anderen Weisen, σ als ein Produkt von Zyklen zu schreiben (vielleicht ohne Beziehung zu den Zyklen von σ), die zusammenhanglose Bahnen haben. Die Zyklus-Notation ist weniger einzigartig, da jeder individuelle Zyklus unterschiedlich, als im Beispiel oben geschrieben werden kann, wo (5 1 2) denselben Zyklus wie (1 2 5) anzeigt (aber (5 2 1) würde eine verschiedene Versetzung anzeigen).

Eine Bahn der Größe 1 (ein fester Punkt x in S) hat keinen entsprechenden Zyklus, da diese Versetzung x sowie jedes andere Element von S befestigen würde, mit anderen Worten würde es die Identität unabhängig von x sein. Es ist möglich (x) in die Zyklus-Notation für σ einzuschließen, um zu betonen, dass σ x befestigt (und das sogar in combinatorics, wie beschrieben, in Zyklen und befestigten Punkten normal ist), aber das entspricht keinem Faktor in (Gruppe theoretisch) Zergliederung von σ. Wenn der Begriff "des Zyklus" genommen würde, um die Identitätsversetzung einzuschließen, dann würde das die Einzigartigkeit (bis zur Ordnung) der Zergliederung einer Versetzung in zusammenhanglose Zyklen verderben. Die Zergliederung in zusammenhanglose Zyklen der Identitätsversetzung ist ein leeres Produkt; seine Zyklus-Notation würde leer sein, so wird eine andere Notation wie e gewöhnlich stattdessen verwendet.

Zyklen der Länge zwei werden Umstellungen genannt; solche Versetzungen tauschen bloß den Platz von zwei Elementen aus.

Produkt und Gegenteil

Das Produkt von zwei Versetzungen wird als ihre Zusammensetzung als Funktionen, mit anderen Worten σ\definiert · π ist die Funktion, die jedes Element x des Satzes zu σ (π (x) kartografisch darstellt). Bemerken Sie, dass die niedrigstwertige Versetzung auf das Argument zuerst wegen der Weise angewandt wird, wie Funktionsanwendung geschrieben wird. Einige Autoren bevorzugen den leftmost Faktor, der zuerst handelt, aber zu diesem Ende müssen Versetzungen rechts von ihrem Argument zum Beispiel als eine Hochzahl geschrieben werden, wo σ, der x folgt, x geschrieben wird; dann wird das Produkt durch x = (x) definiert. Jedoch gibt das eine verschiedene Regel, um Versetzungen zu multiplizieren; dieser Artikel verwendet die Definition, wo die niedrigstwertige Versetzung zuerst angewandt wird.

Da die Zusammensetzung von zwei Bijektionen immer eine andere Bijektion gibt, ist das Produkt von zwei Versetzungen wieder eine Versetzung. Da Funktionszusammensetzung assoziativ ist, auch ist die Produktoperation auf Versetzungen: (σ\· π) · ρ =σ\· (π\· ρ). Deshalb werden Produkte von mehr als zwei Versetzungen gewöhnlich geschrieben, ohne Parenthesen hinzuzufügen, um Gruppierung auszudrücken; sie werden auch gewöhnlich ohne einen Punkt oder anderes Zeichen geschrieben, Multiplikation anzuzeigen.

Die Identitätsversetzung, die jedes Element des Satzes zu sich kartografisch darstellt, ist das neutrale Element für dieses Produkt. In der Zwei-Linien-Notation ist die Identität

:

Da Bijektionen Gegenteile, so Versetzungen haben, und das Gegenteil σ σ wieder eine Versetzung ist. Ausführlich, wann auch immer σ (x) =y man auch σ (y) =x hat. In der Zwei-Linien-Notation kann das Gegenteil durch das Austauschen der zwei Linien erhalten werden (und die Säulen sortierend, wenn man möchte, dass die erste Linie in einer gegebenen Ordnung ist). Zum Beispiel

:

= \begin {pmatrix} 2 & 5 & 4 & 3 & 1 \\1 & 2 & 3 & 4 & 5 \end {pmatrix }\

= \begin {pmatrix} 1 & 2 & 3 & 4 & 5 \\5 & 1 & 4 & 3 & 2\end {pmatrix}. </Mathematik>

In der Zyklus-Notation kann man die Ordnung der Elemente in jedem Zyklus umkehren, um eine Zyklus-Notation für sein Gegenteil zu erhalten.

Ein assoziatives Produkt habend, machen ein neutrales Element und Gegenteile für alle seine Elemente, den Satz aller Versetzungen von S in eine Gruppe, genannt die symmetrische Gruppe von S.

Jede Versetzung eines begrenzten Satzes kann als das Produkt von Umstellungen ausgedrückt werden.

Außerdem, obwohl viele solche Ausdrücke für eine gegebene Versetzung bestehen können, kann es unter ihnen beiden Ausdrücke mit einer geraden Zahl und Ausdrücke mit einer ungeraden Zahl von Umstellungen nie geben. Alle Versetzungen werden dann als sogar oder seltsamen gemäß der Gleichheit der Umstellungen in jedem solchem Ausdruck klassifiziert.

Das Multiplizieren von in der Zyklus-Notation geschriebenen Versetzungen folgt keinem leicht beschriebenen Muster, und die Zyklen des Produktes können von denjenigen der Versetzungen völlig verschieden sein, die zusammensetzen werden. Jedoch wird die Zyklus-Struktur im speziellen Fall bewahrt, eine Versetzung σ durch eine andere Versetzung π zu konjugieren, was bedeutet, das Produkt π\zu bilden · σ\· π. Hier kann die Zyklus-Notation des Ergebnisses durch die Einnahme der Zyklus-Notation für σ und die Verwendung π zu allen Einträgen darin erhalten werden.

Man kann eine Versetzung {1, 2..., n} als eine n×n Matrix vertreten. Es gibt zwei natürliche Weisen, so zu tun, aber nur ein, für die Multiplikationen von matrices Multiplikation von Versetzungen in derselben Ordnung entspricht: Das ist dasjenige, das zu σ die MatrixM vereinigt, deren Zugang M 1 wenn ich = σ (j), und 0 sonst ist. Die resultierende Matrix hat genau einen Zugang 1 in jeder Säule und in jeder Reihe, und wird eine Versetzungsmatrix genannt.

Hier ist eine Liste dieser matrices für Versetzungen von 4 Elementen. Der Cayley Tisch auf dem Recht zeigt diese matrices für Versetzungen von 3 Elementen.

Versetzungen in combinatorics

In combinatorics ist eine Versetzung eines Satzes S mit n Elementen eine Auflistung der Elemente von S in einer Ordnung (jedes Element, das genau einmal vorkommt). Das kann formell als eine Bijektion vom Satz {1, 2..., n} zu S definiert werden. Bemerken Sie dass, wenn S {1, 2..., n} gleich ist, dann fällt diese Definition mit der Definition in der Gruppentheorie zusammen. Mehr allgemein konnte man statt {1, 2..., n} jeder mit einer Gesamteinrichtung seiner Elemente ausgestattete Satz verwenden.

Ein kombinatorisches Eigentum, das mit der Gruppe theoretische Interpretation von Versetzungen verbunden ist und definiert werden kann, ohne eine Gesamteinrichtung von S zu verwenden, ist die Zyklus-Struktur einer Versetzung σ. Es ist die Teilung von n das Beschreiben der Längen der Zyklen von σ. Hier gibt es einen Teil "1" in der Teilung für jeden festen Punkt von σ. Eine Versetzung, die keinen festen Punkt hat, wird ein Durcheinander genannt.

Andere kombinatorische Eigenschaften sind jedoch direkt mit der Einrichtung von S, und zur Weise verbunden, wie sich die Versetzung darauf bezieht. Hier sind mehrere solche Eigenschaften.

Aufstiege, Abstiege und Läufe

Ein Aufstieg einer Versetzung σ n ist jede Position i &lt; n, wo der folgende Wert größer ist als der aktuelle. D. h. wenn σ = σσ...σ, dann bin ich ein Aufstieg wenn σ &lt; σ.

Zum Beispiel hat die Versetzung 3452167 Aufstiege (an Positionen) 1,2,5,6.

Ähnlich ist ein Abstieg eine Position i &lt; n mit σ &gt; σ, so jeder ich damit

Die Zahl von Versetzungen von n mit k Aufstiegen ist die Zahl von Eulerian; das ist auch die Zahl von Versetzungen von n mit k Abstiegen.

Ein steigender Lauf einer Versetzung ist eine nichtleere zunehmende aneinander grenzende Subfolge der Versetzung, die an keinem Ende erweitert werden kann; es entspricht einer maximalen Folge von aufeinander folgenden Aufstiegen (die Letzteren können leer sein: Zwischen zwei aufeinander folgenden Abstiegen gibt es noch einen steigenden Lauf der Länge 1). Im Vergleich ist eine zunehmende Subfolge einer Versetzung nicht notwendigerweise aneinander grenzend: Es ist eine zunehmende Folge von bei der Versetzung erhaltenen Elementen durch das Auslassen der Werte an einigen Positionen.

Zum Beispiel hat die Versetzung 2453167 die steigenden Läufe 245, 3, und 167, während sie eine zunehmende Subfolge 2367 hat.

Wenn eine Versetzung k  1 Abstiege hat, dann muss es die Vereinigung von k steigende Läufe sein. Folglich ist die Zahl von Versetzungen von n mit k steigende Läufe dasselbe als die Zahl von Versetzungen mit k  1 Abstiege.

Inversionen

Eine Inversion einer Versetzung σ ist ein Paar (ich, j) von Positionen, wo die Einträge einer Versetzung in der entgegengesetzten Ordnung sind:

Manchmal wird eine Inversion als das Paar von Werten (σ,σ) selbst definiert, wessen Ordnung umgekehrt wird; das macht keinen Unterschied für die Zahl von Inversionen, und dieses (umgekehrte) Paar ist auch eine Inversion im obengenannten Sinn für die umgekehrte Versetzung σ. Die Zahl von Inversionen ist ein wichtiges Maß für den Grad, zu dem die Einträge einer Versetzung in Unordnung sind; es ist dasselbe für σ und für σ. Um eine Versetzung mit k Inversionen in die Ordnung zu bringen (d. h., gestalten Sie es in die Identitätsversetzung um), durch die aufeinander folgende Verwendung (richtige Multiplikation durch) angrenzender Umstellungen, ist immer möglich und verlangt eine Folge von k solche Operationen. Außerdem wird jede angemessene Wahl für die angrenzenden Umstellungen arbeiten: es genügt, um an jedem Schritt eine Umstellung von mir zu wählen, und wo ich ein Abstieg der Versetzung, wie modifiziert, bis jetzt bin (so dass die Umstellung diesen besonderen Abstieg entfernen wird, obwohl es andere Abstiege schaffen könnte). Das ist so, weil Verwendung solch einer Umstellung die Anzahl von Inversionen durch 1 vermindert; bemerken Sie auch, dass so lange diese Zahl nicht Null ist, ist die Versetzung nicht die Identität, so hat es mindestens einen Abstieg. Luftblase-Sorte und Einfügungssorte können als besondere Beispiele dieses Verfahrens interpretiert werden, um eine Folge in die Ordnung zu stellen. Beiläufig beweist dieses Verfahren, dass jede Versetzung σ als ein Produkt von angrenzenden Umstellungen geschrieben werden kann; weil dieser einfach jede Folge solcher Umstellungen umkehren kann, die σ in die Identität umgestaltet. Tatsächlich, indem man alle Folgen von angrenzenden Umstellungen aufzählt, die σ in die Identität umgestalten würden, erhält man (nach der Umkehrung) eine ganze Liste aller Ausdrücke der minimalen Länge, σ als ein Produkt von angrenzenden Umstellungen schreibend.

Die Zahl von Versetzungen von n mit k Inversionen wird durch eine Zahl von Mahonian ausgedrückt, es ist der Koeffizient X in der Vergrößerung des Produktes

:

der auch (mit q bekannt ist, der X ausgewechselt ist) als der q-factorial n!.

Das Aufzählen von Folgen ohne Wiederholung

In dieser Abteilung ist eine K-Versetzung eines Satzes S eine bestellte Folge von k verschiedenen Elementen von S. Zum Beispiel, in Anbetracht des Satzes von Briefen {}, ist die Folge ein 3-Versetzungen-, und ist 4 Versetzungen, und ist 5 Versetzungen, und ist ein 6-Versetzungen-; seit dem letzten Gebrauch alle Briefe ist es eine Versetzung des gegebenen Satzes im gewöhnlichen kombinatorischen Sinn. andererseits ist nicht eine Versetzung wegen der Wiederholungen: Es verwendet die Elemente und zweimal.

Lassen Sie n die Größe von S, die für die Auswahl verfügbare Zahl der Elemente sein. Im Konstruieren einer K-Versetzung gibt es n mögliche Wahlen für das erste Element der Folge, und das ist dann Zahl von 1 Versetzungen. Sobald es gewählt worden ist, gibt es Elemente von S, der verlassen ist, davon zu wählen, so kann ein zweites Element auf Weisen gewählt werden, einen ganzen n × (n  1) mögliche 2 Versetzungen gebend. Für jedes aufeinander folgende Element der Folge nimmt die Zahl von Möglichkeiten um 1 ab, der zur Zahl von führt

:n × (n  1) × (n  2)... × (n  k + 1) mögliche K-Versetzungen.

Das gibt insbesondere die Zahl von N-Versetzungen (die alle Elemente von S einmal enthalten, und deshalb einfach Versetzungen von S sind):

:n × (n  1) × (n  2) ×... × 2 × 1,

eine Zahl, die so oft in der Mathematik vorkommt, dass es eine Kompaktnotation "n gegeben wird!" und wird "n factorial" genannt. Diese N-Versetzungen sind die längsten Folgen ohne Wiederholung von Elementen von S, der durch die Tatsache widerspiegelt wird, dass die obengenannte Formel für die Zahl von K-Versetzungen Null wann auch immer k &gt gibt; n.

Die Zahl von K-Versetzungen von einer Reihe von n Elementen wird manchmal durch P (n, k) oder eine ähnliche Notation angezeigt (gewöhnlich begleitet durch eine Notation für die Zahl von K-Kombinationen von einer Reihe von n Elementen, in denen der "P" durch "C" ersetzt wird). Diese Notation wird in anderen Zusammenhängen selten verwendet als dieses des Zählens von K-Versetzungen, aber der Ausdruck für die Zahl entsteht wirklich in vielen anderen Situationen. Ein Produkt von k Faktoren seiend, die an n anfangen und durch Einheitsschritte abnehmen, wird es den k-th genannt, der factorial Macht von n fällt:

:

obwohl viele andere Namen und Notationen im Gebrauch, wie ausführlich berichtet, am Symbol von Pochhammer sind. Wenn k  n die factorial Macht durch zusätzliche Faktoren vollendet werden kann: n × (n  k)! = n!, der erlaubt, zu schreiben

:

Die rechte Seite wird häufig als Ausdruck für dann die Zahl von K-Versetzungen gegeben, aber sein Hauptverdienst verwendet die factorial Kompaktnotation. Wenn er ein Produkt von k Faktoren weil ausdrückt, ist ein Quotient potenziell viel größerer Produkte, wo alle Faktoren im Nenner auch ausführlich im Zähler da sind, nicht besonders effizient; weil eine Methode der Berechnung dort die zusätzliche Gefahr der Überschwemmung oder Rundungsfehler ist. Es sollte auch bemerkt werden, dass der Ausdruck wenn k &gt unbestimmt ist; n, wohingegen in jenen Fällen die Nummer n von K-Versetzungen gerade 0 ist.

Versetzungen in der Computerwissenschaft

Das Numerieren von Versetzungen

Eine Weise, Versetzungen von n zu vertreten, ist durch eine ganze Zahl N mit 0  N &lt; n!, vorausgesetzt dass günstige Methoden gegeben werden, um sich zwischen der Zahl und der üblichen Darstellung einer Versetzung als eine Folge umzuwandeln. Das gibt die kompakteste Darstellung von willkürlichen Versetzungen, und in der Computerwissenschaft ist besonders attraktiv, wenn n klein genug ist, an dem N in einem Maschinenwort gehalten werden kann; für 32-Bit-Wörter bedeutet das n  12, und für 64-Bit-Wörter bedeutet das n  20. Die Konvertierung kann über die Zwischenform einer Folge von Nummern d, d..., d, d getan werden, wo d eine natürliche Zahl weniger ist als ich (man kann d weglassen, wie es immer 0 ist, aber seine Anwesenheit macht die nachfolgende Konvertierung zu einer Versetzung leichter zu beschreiben). Der erste Schritt ist dann einfach Ausdruck von N im factorial Zahl-System, das gerade eine besondere Mischbasis-Darstellung, wo für Zahlen bis zu n ist! die Basen für aufeinander folgende Ziffern sind n..., 2, 1. Der zweite Schritt interpretiert diese Folge als ein Code von Lehmer oder (fast gleichwertig) als ein Inversionstisch.

Im Code von Lehmer für eine Versetzung σ vertritt die Nummer d die Wahl, die für den ersten Begriff σ gemacht ist, die Nummer d vertritt die Wahl, die für den zweiten Begriff gemacht ist

σ unter den restlichen Elementen des Satzes, und so weiter. Genauer gibt jeder d die Zahl von restlichen Elementen ausschließlich weniger als der Begriff σ. Da jene restlichen Elemente verpflichtet werden, als ein späterer Begriff σ aufzutauchen, zählt die Ziffer d die Inversionen (ich, j) das Beteiligen i als kleinerer Index auf (die Zahl von Werten j für der ich &lt; j und σ &gt; σ). Der Inversionstisch für σ ist ziemlich ähnlich, aber hier zählt d die Zahl von Inversionen auf (ich, j), wo k = σ als die kleineren von den zwei Werten vorkommt, die in der umgekehrten Ordnung erscheinen. Beide encodings kann durch einen n durch das n Diagramm von Rothe vergegenwärtigt werden (genannt nach Heinrich August Rothe), in dem Punkte an (ich, σ) die Einträge der Versetzung und ein Kreuz an (ich, σ) kennzeichnen, kennzeichnen die Inversion (ich, j); durch die Definition von Inversionen erscheint ein Kreuz in jedem Quadrat, das beide vor dem Punkt (j, σ) in seiner Säule, und vor dem Punkt (ich, σ) in seiner Reihe kommt. Der Lehmer-Code verzeichnet die Zahlen von Kreuzen in aufeinander folgenden Reihen, während der Inversionstisch die Zahlen von Kreuzen in aufeinander folgenden Säulen verzeichnet; es ist gerade der Code von Lehmer für die umgekehrte Versetzung, und umgekehrt.

Um einen Code d, d von Lehmer..., d, d in eine Versetzung eines bestellten Satzes S effektiv umzuwandeln, kann man mit einer Liste der Elemente von S in der zunehmenden Ordnung anfangen, und weil ich, von 1 bis n zunehmend, σ auf das Element in der Liste setze, der durch d andere vorangegangen wird, und entfernen Sie dieses Element von der Liste. Um eine Inversionstabelle d, d..., d, d in die entsprechende Versetzung umzuwandeln, kann man die Zahlen von d bis d überqueren, während man die Elemente von S vom größten bis kleinsten in eine am Anfang leere Folge einfügt; am Schritt mit der Nummer d vom Inversionstisch hat das Element von S in die Folge am Punkt eingefügt, wo ihm durch d Elemente vorangegangen wird, bereits präsentieren. Wechselweise konnte man die Zahlen vom Inversionstisch bearbeiten, und die Elemente von S sowohl in der entgegengesetzten Ordnung, mit einer Reihe von n leeren Ablagefächern, als auch an jedem Schritt anfangend, legen das Element von S ins leere Ablagefach, dem durch d andere leere Ablagefächer vorangegangen wird.

Das Umwandeln aufeinander folgender natürlicher Zahlen zum factorial Zahl-System erzeugt jene Folgen in der lexikografischen Ordnung (wie mit jedem Mischbasis-Zahl-System der Fall ist), und das weitere Umwandeln von ihnen zu Versetzungen die lexikografische Einrichtung bewahrt, vorausgesetzt dass die Codeinterpretation von Lehmer verwendet wird (das Verwenden von Inversionstischen, bekommt man eine verschiedene Einrichtung, wo man anfängt, indem man Versetzungen durch den Platz ihrer Einträge 1 aber nicht durch den Wert ihrer ersten Einträge vergleicht). Die Summe der Zahlen in der factorial Zahl-Systemdarstellung gibt die Zahl von Inversionen der Versetzung, und die Gleichheit dieser Summe gibt die Unterschrift der Versetzung. Außerdem geben die Positionen des zeroes im Inversionstisch die Werte von zum Recht nach links Maxima der Versetzung (im Beispiel 6, 8, 9), während die Positionen des zeroes im Code von Lehmer die Positionen der Minima des Rechts-zu-link (in den Beispiel-Positionen die 4, 8, 9 der Werte 1, 2, 5) sind; das erlaubt, den Vertrieb solchen extrema unter allen Versetzungen zu schätzen. Eine Versetzung mit dem Code d, d von Lehmer..., d, d hat einen Aufstieg wenn und nur wenn.

Algorithmen, um Versetzungen zu erzeugen

In der Computerwissenschaft kann davon erforderlich sein, Versetzungen einer gegebenen Folge von Werten zu erzeugen. Die Methoden haben sich am besten angepasst, um zu tun, das hängt ab, ob man einige zufällig gewählte Versetzungen oder alle Versetzungen, und im letzten Fall will, wenn eine spezifische Einrichtung erforderlich ist. Eine andere Frage besteht darin, ob die mögliche Gleichheit unter Einträgen in der gegebenen Folge in Betracht gezogen werden soll; wenn so, man sollte nur verschiedene Mehrsatz-Versetzungen der Folge erzeugen.

Eine offensichtliche Weise, Versetzungen von n zu erzeugen, soll Werte für den Code von Lehmer erzeugen (vielleicht die factorial Zahl-Systemdarstellung von ganzen Zahlen bis zu n verwendend!) Und wandeln Sie diejenigen in die entsprechenden Versetzungen um. Jedoch ist der letzte Schritt, während aufrichtig, hart, effizient durchzuführen, weil er n Operationen jede der Auswahl von einer Folge und des Auswischens davon an einer willkürlichen Position verlangt; der offensichtlichen Darstellungen der Folge als eine Reihe oder eine verbundene Liste verlangen beide (aus verschiedenen Gründen) über n/4 Operationen, um die Konvertierung durchzuführen. Mit n, um wahrscheinlich (besonders ziemlich klein zu sein, wenn die Generation aller Versetzungen erforderlich ist), der nicht zu viel von einem Problem ist, aber stellt es sich heraus, dass sowohl für den zufälligen als auch für die systematische Generation es einfache Alternativen gibt, die beträchtlich besser tun. Aus diesem Grund scheint es nützlich, obwohl sicher möglich, nicht, eine spezielle Datenstruktur zu verwenden, die erlauben würde zu leisten, die Konvertierung vom Code von Lehmer bis Versetzung in O (n loggen n) Zeit.

Zufällige Generation von Versetzungen

Um zufällige Versetzungen einer gegebenen Folge von N-Werten zu erzeugen, macht es keinen Unterschied, ob man vorhat, wenden eine zufällig ausgewählte Versetzung von n zur Folge an, oder wählen ein zufälliges Element aus dem Satz von verschiedenen (Mehrsatz) Versetzungen der Folge. Das ist, weil, wenn auch im Falle wiederholter Werte es viele verschiedene Versetzungen von n geben kann, die auf dieselbe permutierte Folge hinauslaufen, die Zahl solcher Versetzungen dasselbe für jedes mögliche Ergebnis ist. Unterschiedlich für die systematische Generation, die unausführbar für den großen n wegen des Wachstums der Nummer n wird!, es gibt keinen Grund anzunehmen, dass n für die zufällige Generation klein sein wird.

Die Grundidee, eine zufällige Versetzung zu erzeugen, soll aufs Geratewohl einen der n erzeugen! Folgen von ganzen Zahlen d, d..., d befriedigend (da d immer Null ist, kann es weggelassen werden), und es zu einer Versetzung durch eine bijektive Ähnlichkeit umzuwandeln. Für die letzte Ähnlichkeit konnte man die (rück)-Folge als ein Code von Lehmer interpretieren, und das gibt eine Generationsmethode zuerst veröffentlicht 1938 von Ronald A. Fisher und Frank Yates.

Während am Zeitcomputer die Durchführung nicht ein Problem war, leidet diese Methode unter der Schwierigkeit, die oben kurz gefasst ist, um sich vom Code von Lehmer bis Versetzung effizient umzuwandeln. Das kann durch das Verwenden einer verschiedenen bijektiven Ähnlichkeit behoben werden: Nach dem Verwenden d, um ein Element unter mir auszuwählen, Elemente der Folge bleibend (um Werte von i zu vermindern), anstatt das Element zu entfernen und die Folge zusammenzupressen, indem man unten weitere Elemente ein Platz auswechselt, tauscht man das Element mit dem restlichen Endelement. So bilden die Elemente, die für die Auswahl bleiben, eine Konsekutivreihe an jedem Punkt rechtzeitig, wenn auch sie in derselben Ordnung nicht vorkommen können, wie sie in der ursprünglichen Folge getan haben. Von der Folge von ganzen Zahlen zu Versetzungen kartografisch darzustellen, wird etwas kompliziert, aber, wie man sehen kann, erzeugt es jede Versetzung auf genau eine Weise durch eine unmittelbare Induktion. Wenn das ausgewählte Element zufällig das restliche Endelement ist, kann die Tausch-Operation weggelassen werden. Das kommt genug häufig nicht vor, um Prüfung für die Bedingung zu bevollmächtigen, aber das Endelement muss unter den Kandidaten der Auswahl eingeschlossen werden, um zu versichern, dass alle Versetzungen erzeugt werden können.

Der resultierende Algorithmus, für eine zufällige Versetzung [0], [1]..., [n  1] zu erzeugen, kann wie folgt im Pseudocode beschrieben werden:

:for i von n downto 2

:do d  zufälliges Element {0..., ich  1 }\

:: tauschen Sie [d] und [ich  1]

Das kann mit der Initialisierung der Reihe [ich] = ich wie folgt verbunden werden:

:for i von 0 bis n1

:do d  zufälliges Element {0..., ich }\

:: [ich]  [d]

:: [d]  i

Wenn d = ich, die erste Anweisung einen uninitialisierten Wert kopieren wird, aber das zweite wird es mit dem richtigen Wert i überschreiben.

Generation in der lexikografischen Ordnung

Es gibt viele Weisen, alle Versetzungen einer gegebenen Folge systematisch zu erzeugen. Ein klassischer Algorithmus, der sowohl einfach als auch flexibel ist, basiert auf der Entdeckung der folgenden Versetzung in der lexikografischen Einrichtung, wenn es besteht. Es kann wiederholte Werte behandeln, für den Fall es die verschiedenen Mehrsatz-Versetzungen jeder einmal erzeugt. Sogar für gewöhnliche Versetzungen ist es bedeutsam effizienter als das Erzeugen von Werten für den Code von Lehmer in der lexikografischen Ordnung (vielleicht das factorial Zahl-System verwendend) und diejenigen zu Versetzungen umwandelnd. Um es zu verwenden, fängt man an, indem man die Folge in (der schwach) zunehmenden Ordnung sortiert (der seine lexikografisch minimale Versetzung gibt), und dann das Vorrücken zur folgenden Versetzung wiederholt, so lange einer gefunden wird. Die Methode geht zu Narayana Pandita im 14. Jahrhundert Indien zurück, und ist oft seitdem wieder entdeckt worden.

Der folgende Algorithmus erzeugt die folgende Versetzung lexikografisch nach einer gegebenen Versetzung. Es ändert die gegebene Versetzung im Platz.

1. Finden Sie den größten Index k solch dass. Wenn kein solcher Index besteht, ist die Versetzung die letzte Versetzung.
2. Finden Sie den größten Index l solch dass. Seitdem ist solch ein Index, l wird gut definiert und befriedigt.
3. Tauschen Sie [k] mit [l].
4. Kehren Sie die Folge von [] bis zu und einschließlich des Endelements [n] um.

Nach dem Schritt 1 weiß man, dass alle Elemente ausschließlich nach der Position k eine schwach abnehmende Folge bilden, so wird keine Versetzung dieser Elemente es in der lexikografischen Ordnung vorwärts gehen lassen; um vorwärts zu gehen, muss man [k] zunehmen. Schritt 2 findet, dass der kleinste Wert [l] [k] dadurch ersetzt, und das Tauschen von ihnen im Schritt 3 verlässt die Folge nach der Position k in der schwach abnehmenden Ordnung. Das Umkehren dieser Folge im Schritt 4 erzeugt dann seine lexikografisch minimale Versetzung und den lexikografischen Nachfolger des anfänglichen Staates für die ganze Folge.

Generation mit minimalen Änderungen

Eine Alternative zum obengenannten Algorithmus, dem Steinhaus-Johnson-Trotter Algorithmus, erzeugt eine Einrichtung auf allen Versetzungen einer gegebenen Folge mit dem Eigentum, dass sich irgendwelche zwei Konsekutivversetzungen in seiner Produktion durch das Tauschen zwei angrenzender Werte unterscheiden. Diese Einrichtung auf den Versetzungen war der englischen Glocke des 17. Jahrhunderts ringers bekannt, unter wem es als "einfache Änderungen" bekannt war. Ein Vorteil dieser Methode besteht darin, dass der kleine Betrag der Änderung von einer Versetzung bis das folgende der Methode erlaubt, in der unveränderlichen Zeit pro Versetzung durchgeführt zu werden. Dasselbe kann auch die Teilmenge von sogar Versetzungen, wieder in der unveränderlichen Zeit pro Versetzung, durch das Auslassen jeder anderen Produktionsversetzung leicht erzeugen.

Softwaredurchführungen

Rechenmaschine-Funktionen

Viele wissenschaftliche Rechenmaschinen und Rechensoftware haben eine eingebaute Funktion, für die Zahl von K-Versetzungen von n zu berechnen.

• Casio und Rechenmaschinen von TI: nPr
• HP-Rechenmaschinen: DAUERWELLE
• Mathematica: FallingFactorial

Spreadsheet-Funktionen

Der grösste Teil der Spreadsheet-Software stellt auch eine eingebaute Funktion zur Verfügung, für die Zahl von K-Versetzungen von n, genannt PERMUT in vielen populären Spreadsheets zu berechnen.

Anwendungen

Versetzungen werden im interleaver Bestandteil der Fehlerentdeckungs- und Korrektur-Algorithmen, wie Turbocodes, verwendet

zum Beispiel 3GPP Langfristige Evolution verwendet beweglicher Fernmeldestandard diese Ideen (sieh 3GPP technische Spezifizierung 36.212).

Solche Anwendungen bringen die Frage der schnellen Generation der Versetzung auf, die bestimmte wünschenswerte Eigenschaften befriedigt. Eine der Methoden basiert auf den Versetzungspolynomen.

Siehe auch

• Wechselversetzung
• Binomischer Koeffizient
• Kombination
• Combinatorics
• Gehirnwindung
• Zyklische Ordnung
• Zyklische Versetzung
• Sogar und sonderbare Versetzungen
• Zahl-System von Factorial
• Supermuster
• Versetzung von Josephus
• Liste von Versetzungsthemen
• Symbol von Levi-Civita
• Versetzungsgruppe
• Versetzungsmuster
• Versetzungspolynom
• Wahrscheinlichkeit
• Zufällige Versetzung
• Zahlen von Rencontres
• Das Sortieren des Netzes
• Ersatz-Ziffer
• Symmetrische Gruppe
• Twelvefold Weg
• Schwache Ordnung von Versetzungen

Zeichen

• Miklos Bona. "Combinatorics von Versetzungen", Hausierer-Saal-CRC, 2004. Internationale Standardbuchnummer 1-58488-434-7.
• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 4: Alle Tupel und Versetzungen, Bündel 2 erzeugend, zuerst druckend. Addison-Wesley, 2005. Internationale Standardbuchnummer 0-201-85393-0.
• Donald Knuth. Die Kunst der Computerprogrammierung, Bands 3: Das Sortieren und die Suche, die Zweite Ausgabe. Addison-Wesley, 1998. Internationale Standardbuchnummer 0-201-89685-0. Abschnitt 5.1: Kombinatorische Eigenschaften von Versetzungen, Seiten 11-72.
• Humphreys, J. F. Ein Kurs in der Gruppentheorie. Presse der Universität Oxford, 1996. Internationale Standardbuchnummer 978-0-19-853459-4