WikiDer > Permutation

Es gibt sechs mögliche Permutationen von drei Objekten

Beispiel für eine Permutation, die ist zusammengesetzt aus zyklischen Permutationen disjunkter Teile

EIN Permutation einer endlichen Menge (von z. B. Objekten oder Zahlen) ist eine Neuanordnung derselben, d. h. das Ausführen von null oder mehr Austauschvorgängen. Ausgehend von einer bestimmten Anfangsreihenfolge kann man eine Permutation erhalten, indem man wählt, welche zuerst genommen werden soll, dann welche der anderen als zweites und so weiter, bis alle ausgewählt sind. Liegt eine Standardreihenfolge vor, wie bei der Menge {1, 2, 3, 4}, wird diese implizit als Startreihenfolge genommen, so dass die Permutationen den möglichen Reihenfolgen entsprechen.

Permutationen sind unter anderem in der Wahrscheinlichkeitstheorie, Statistik und Kombinatorik wichtig.

Der Begriff kann auch für eine unendliche Menge definiert werden.

Definition

EIN Permutation einer Sammlung ist a bijektion von diesen Sammlung allein.

Bemerkungen

wenn ${displaystyle b_{0}:X oder Y}$ ein bijektion gehört zu a Sammlung${Anzeigestil X}$ auf einer Sammlung ${Anzeigestil Y}$, dann ist ${displaystyle b=b_{0}circ p}$ eine Eins-zu-Eins-Entsprechung zwischen den Permutationen ${displaystyle p}$ von ${Anzeigestil X}$ und die bijektionen ${displaystyle b}$ von ${Anzeigestil X}$ auf ${Anzeigestil Y}$.

Wenn beispielsweise drei Objekte mit den Nummern 1, 2 und 3 und drei Positionen, ebenfalls mit den Nummern 1, 2 und 3, vorhanden sind, bestimmt diese Nummerierung eine Bijektion, die jedem Objekt die Position derselben Nummer hinzufügt. Man kann nun die Platzierung der Objekte in den Positionen (ein Objekt pro Position, eine Bijektion) über die Permutation der Menge { 1, 2, 3 } beschreiben, die die Objektnummer pro Positionsnummer angibt, zum Beispiel ( 2, 3, 1 ), in Zyklusnotation (1 2 3), oder die Permutation, die die Positionsnummer pro Objektnummer angibt, in diesem Fall ( 3, 1, 2 ), in Zyklenschreibweise (3 2 1). Diese Bijektionen sind jeweils umgekehrt.

Wenn die Objekte zunächst keine Nummer haben und Sie eine Verschiebung beschreiben möchten, können Sie die Objekte anhand der ursprünglichen Position nummerieren. Umgekehrt, wenn die Orte zunächst keine Nummer haben und Sie eine Bewegung beschreiben möchten, können Sie die Orte basierend auf dem Objekt nummerieren, das sich ursprünglich an dieser Stelle befindet. Wenn die Orte jedoch in einer Reihe sind, ist die Nummerierung basierend auf dem Platz in der Reihe offensichtlicher.

Die Permutationen von a total bestellt Satz entspricht eins zu eins den möglichen Gesamtbestellungen dieses Satzes.

Beispiel mit 4 Murmeln, eine rote, eine gelbe, eine grüne und eine blaue: Unter einer bestimmten Reihenfolge (zB die genannten) sind die 4! = 4 x 3 x 2 x 1 = 24 Permutationen in allen 24 Ordnungen, z.B. "Rot, Gelb, Grün, Blau" und "Rot, Grün, Gelb, Blau".

Spezielle Permutationen

Das identische Permutation ist der identisches Bild: die Bijektion, die jedes Element auf sich selbst abbildet.

EIN (Paar)tausch (Umsetzung) ist eine Permutation, die sich von der identischen Permutation nur in zwei Elementen unterscheidet (die einander ersetzen).

EIN zyklische Permutation beinhaltet, mit einem beliebigen Gegenstand zu beginnen, dann den nächsten zu nehmen, den ersten nach dem letzten zu nehmen und dann den nächsten zu nehmen, bis Sie alle haben. Beispiel: Die Reihenfolge (1, 2, 3, 4, 5) wird zu (3, 4, 5, 1, 2).

Notation

Unter der Annahme der Standardreihenfolge (1, 2, 3, 4, 5) kann das letzte Beispiel einfach als (3, 4, 5, 1, 2) geschrieben werden. Eine andere Möglichkeit ist die Zyklusnotation, in diesem Fall (1 3 5 2 4), ohne Kommas.

Anzahl möglicher Permutationen

Die Anzahl der möglichen Permutationen von ${displaystyle n}$ verschiedene Elemente werden notiert als ${displaystyle n!}$ (lies: nein Fakultät).Verwenden der Rekursionsbeziehung

${Anzeigestil n!=n(n-1)!}$

und

${Anzeigestil 1!=1}$

können ${displaystyle n!}$ für beliebig viele Elemente berechnet werden ${displaystyle n}$. Obwohl es nicht offensichtlich ist, über die Anzahl der Permutationen von 0 Elementen zu sprechen, ist es eine Übereinstimmung, dass

${Anzeigestil 0!=1}$,

was der Tatsache entspricht, dass es formal eine Abbildung der leeren Menge auf sich selbst gibt, und dass es sich um eine Bijektion handelt.

Manchmal a Variation als Permutation bezeichnet.

Permutationsgruppe

sehen Permutationsgruppe für den Hauptartikel zu diesem Thema.

Zwei Permutationen ${displaystyle pi_{1}}$ und ${displaystyle pi_{2}}$ auf einer Sammlung ${Anzeigestil A}$ könnte sein zusammengesetzt. Das Komposition${displaystyle pi _{2}circ pi _{1}}$ ist wieder eine Permutation, so dass die Operation "${Displaystil-Zirkel}$" der Sammlung ${displaystyle {mathcal {S}}(A)}$ aller Permutationen von ${Anzeigestil A}$ ein Gruppe macht. Insbesondere wird darauf hingewiesen ${displaystyle {mathcal {S}}_{n}}$ für die Gruppe aller Permutationen der Menge ${displaystyle {1,2,ldots,n}}$. wenn ${Anzeigestil A}$ enthält mindestens drei Elemente, diese Gruppe ist nicht abels.

Eine Permutationsgruppe ist eine Untergruppe der Gruppe aller Permutationen einer gegebenen Menge. Beliebige Gruppe ${Anzeigestil G}$ isomorph zu einer Permutationsgruppe auf der Menge ${Anzeigestil G}$. Verknüpfen Sie dazu das Gruppenelement ${displaystyle g}$ mit der Permutation ${displaystyle pi_{g}}$ dass jedes Element ${Anzeigestil hin G}$ wird dem Gruppenelement zugeordnet ${displaystyle gcirc h}$

Gerade und ungerade Permutationen

Jede Permutation von a endliche Menge kann geschrieben werden als Komposition von a endlich Anzahl der Vertauschungen, z.B. durch Vertauschen des erstplatzierten Elements mit dem erstplatzierten Element (sofern es nicht bereits an erster Stelle steht), dann Tausch des zweitplatzierten Elements mit dem (jetzt) ​​an zweiter Stelle stehenden Element, und so weiter . Bei der Permutation von (1, 2, 3, 4) in die Ordnung (2, 3, 4, 1), mit Zyklusnotation (1 2 3 4), gibt (1 4) (1 3) (1 2), diese drei Swaps von rechts nach links. Diese Zusammensetzung ist nicht einzigartig, eine andere ist beispielsweise (1 2) (2 4) (2 3). Das Parität die Anzahl der Austauschvorgänge ist jedoch unveränderlich. EIN Ein bisschen Permutation ist eine Zusammensetzung einer geraden Anzahl von Permutationen, a seltsam Permutation setzt sich aus einer ungeraden Anzahl von Permutationen zusammen, also ist (1 2 3 4) eine ungerade Permutation.

Eine Eigenschaft (und äquivalente Definition) ist, dass eine Permutation von ${Anzeigestil (1,2,3,ldots,n)}$ zu der Bestellung ${displaystyle (c_{1},c_{2},c_{3},ldots ,c_{n})}$ gleich bzw. ungerade wie die Anzahl der Paare ${Anzeigestil (i, j)}$ mit ${Anzeigestil i$ wofür in der neuen Reihenfolge die ${Anzeigestil i}$ an jedem Ort nach dem ${Anzeigestil j}$ kommt, also nicht in der ursprünglichen gegenseitigen Reihenfolge, auch resp. seltsam. Im Beispiel sind dies die Paare {1,2}, {1,3}, {1,4}. Ob eine Permutation gerade oder ungerade ist, hängt bei der ersten Definition nicht von einer gewählten Reihenfolge/Nummerierung der Elemente ab.

Die identische Permutation ist gerade, jede Permutation ist ungerade. Von jeder Menge mit mindestens zwei Elementen ist die Hälfte der Permutationen gerade.

Das alternierende Gruppe auf ${displaystyle n}$ Elemente, bemerkt ${displaystyle {mathcal {A}}_{n}}$, ist der Untergruppe von ${displaystyle {mathcal {S}}_{n}}$ die aus den geraden Permutationen besteht.

EIN Zyklus von mindestens der Länge 2 ist eine gerade Permutation, wenn die Länge ungerade ist und umgekehrt.

Es Schild einer Permutation ist 1, wenn sie gerade ist, und -1, wenn sie ungerade ist, was einer ungeraden oder geraden Potenz von -1 entspricht. Das Vorzeichen der Zusammensetzung der Permutationen ist das Produkt der Vorzeichen der einzelnen Permutationen. Außerdem entspricht eine gerade oder ungerade Zusammensetzung der Permutationen einer geraden oder ungeraden Summe der Zahlen, die gemäß den Komponentenpermutationen gerade oder ungerade sind; zum Beispiel ist die Zusammensetzung zweier ungerader Permutationen gerade, so wie die Summe zweier ungerader Zahlen gerade ist.

Beispiel:

Aus der Kollektion ${Anzeigestil {1,2,3,4}}$ sind die geraden Permutationen

${displaystyle(),}$

${Anzeigestil (123),;(132),;(124),;(142),;(134),;(143),;(234),;(243)}$

${Anzeigestil (12)(34),;(13)(24),;(14)(23)}$

und die ungeraden Permutationen

${Anzeigestil (12),;(13),;(14),;(23),;(24),;(34)}$

${Anzeigestil (1234),;(1243),;(1324),;(1342),;(1423),;(1432)}$

Abwechselnde Permutationen

EIN alternierende Permutation von ${Anzeigestil (1,2,3,ldots,n)}$ ist eine Permutation der Ordnung ${displaystyle (c_{1},c_{2},c_{3},ldots ,c_{n})}$ so dass:

• ${displaystyle c_{1}$
• ${displaystyle c_{i-1}>c_{i}$ wenn ${Anzeigestil i}$ ist ungerade
• ${displaystyle c_{i-1}c_{i 1}}$ wenn ${Anzeigestil i}$ sogar ist

In der permutierten Folge folgt also auf die erste Zahl eine größere Zahl, auf die dann eine kleinere Zahl folgt, wieder eine größere Zahl und so weiter. Jede ungerade Zahl in der Reihe liegt zwischen zwei größeren Zahlen und jede gerade Zahl zwischen zwei kleineren Zahlen.

Alternierende Permutationen sollten nicht mit der alternierenden Gruppe verwechselt werden.

Die fünf abwechselnden Permutationen von {1, 2, 3, 4} sind:

• ${displaystyle(1,3,2,4)quad }$ weil ${Displaystil-Quad 1<3>2<4}$
• ${Displaystil (1,4,2,3)Quad }$ weil ${Displaystil-Quad 1<4>2<3}$
• ${displaystyle(2,3,1,4)Quad }$ weil ${Displaystil-Quad 2<3>1<4}$
• ${displaystyle(2,4,1,3)Quad }$ weil ${Displaystil-Quad 2<4>1<3}$
• ${displaystyle(3,4,1,2)quad}$ weil ${Displaystil-Quad 3<4>1<2}$

Diese Permutationen heißen auch Up-Down-Permutationen. Verlangt man, dass die erste Zahl größer als die zweite sein muss, spricht man von a Down-Up-Permutation. Wegen der Symmetrie gibt es so viele Auf-Ab-Permutationen wie Ab-Auf-Permutationen einer gegebenen Länge. Ihre Anzahl ist in dieser Tabelle für Permutationen bis Länge 7 aufgeführt:

Anzahl der Up-Down-Permutationen von ${displaystyle n}$ Zahlen, die mit der Zahl ${displaystyle k}$ anfangen

${displaystyle {}_{n}!diagdown !!{}^{k}}$	1	2	3	4	5	6	7	Gesamt
2	1	0						1
3	1	1	0					2
4	2	2	1	0				5
5	5	5	4	2	0			16
6	16	16	14	10	5	0		61
7	61	61	56	46	32	16	0	272

Die Summen in der letzten Spalte sind für ungerade ${displaystyle n}$, das Euler-Zahlen die als Koeffizienten in der Entwicklung der Maclaurin-Serie des Tangensfunktion:

${displaystyle { egin{aligned} an(x)&=x { frac {1}{3}}x^{3} { frac {2}{15}}x^{5} { frac {17}{315} }x^{7} ldots /&=x { frac {2}{3!}}x^{3} { frac {16}{5!}}x^{5} { frac {272}{7!} }x^{7} ldots end{ausgerichtet}}}$

Sie sind durch die folgende geschlossene Formel gegeben:

${displaystyle A_{2n 1}=Summe _{j=1}^{n}Summe _{k=j}^{n}(-1)^{jn}{ inom {2k}{kj}}(k 1 ){frac {j^{2n}}{2^{k-1}}}}$

Die Zahlen für eine Weile ${displaystyle n}$ sind die Euler-Zahlen, die die Koeffizienten in der Maclaurin-Reihenentwicklung der Sekantenfunktion:

${displaystyle sec(x)=1 { frac {1}{2!}}x^{2} { frac {5}{4!}}x^{4} { frac {61}{6!}}x^ {6} lPunkte }$

Sie sind durch diese Formel gegeben:

${displaystyle A_{2n}=Summe _{j=1}^{n}Summe _{k=j}^{n}(-1)^{jn}{ inom {2k}{kj}}{frac {j ^{2n}}{2^{k-1}}}}$

Zusammen ergibt dies die nächste Zeile für die Anzahl der Abwärts-Aufwärts- oder Aufwärts-Abwärts-Permutationen der ersten ${Anzeigestil n=1,2,3,ldots}$ ganze Zahlen:

${displaystyle 1,1,2,5,16,61,272,1385,7936,ldots}$  ^[1]

Dies ist auch die erste Spalte in der obigen Tabelle: die Anzahl der abwechselnden Auf-Ab-Permutationen von ${displaystyle n}$ Zahlen ist gleich der Anzahl alternierender Auf-Ab-Permutationen von ${displaystyle n1}$ Zahlen, die mit 1 beginnen (oder die Anzahl der Abwärts-Aufwärts-Permutationen von ${displaystyle n2}$ Zahlen beginnend mit 2).

Diese Permutationen wurden im neunzehnten Jahrhundert von dem französischen Mathematiker untersucht Wunsch André.^[2][3]

Superpermutation

Eine Superpermutation von ${displaystyle n}$ Zeichen ist ein Schnur die alle Permutationen (in der oben genannten Notation, aber ohne Klammern und Kommas) als Teilzeichenkette enthält (${displaystyle n}$ aufeinanderfolgende Zeichen in der Reihenfolge).^[4]

Vor dem ${displaystyle 1leq nleq 5}$ die kürzeste dieser Saiten hat eine Länge ${Anzeigestil 1! 2! lPunkte n!}$, also 1, 3, 9, 33 und 153:

• 1
• 121
• 123121321
• 123412314231243121342132413214321
• 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321

In den ersten vier Fällen ist die kürzeste Sequenz außer der Neunummerierung eindeutig, und a Palindrom. Bei 5 Zeichen gibt es außer der Umnummerierung 8 kürzeste Sequenzen.

Für allgemeines ${displaystyle ngeq 2}$ ist mindestens die kürzeste Länge ${displaystyle n! (n-1)! (n-2)! n-3}$ und höchstens ${displaystyle n! (n-1)! (n-2)! (n-3)! n-3}$. Zum Beispiel für ${Anzeigestil n=6}$ die kürzeste Länge beträgt daher mindestens 870 und höchstens 873. Es wurde jedoch eine Reihe der Länge 872 gefunden, so dass die kürzeste Länge höchstens diese Zahl ist.

Siehe auch

• Kombination (Mathematik)
• Störung