Verknüpfungen

Original: http://www.efgh.com/math/algebra/permutations.htm von Philip J. Erdelsky

1. Einführung

Eine Verknüpfung eines Sets ist eine Möglichkeit, die Elemente des Sets neu anzuordnen. Zum Beispiel sind {1,2} und {2,1} die beiden Permutationen der Menge {1,2}.

Die Menge {1,2,3} hat sechs Verknüpfungen: {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {2,3,1}, {3,1,2} und {3,2,1}.

Eine Permutation kann auch formeller definiert werden als eine Eins-zu-Eins-Korrespondenz einer Menge mit sich selbst, eine Funktion, die jedes Element der Menge in dasjenige trägt, das nach Anwendung der Permutation die gleiche Position einnimmt. Zum Beispiel ist die Permutation {1,3,2} die Funktion f:{1,2,3} ⟶ {1,2,3} mit f(1)=1, f(2)=3 und f(3)=2, oder die Menge {(1,1), (2,3), (3,2)}. Diese Denkweise von Permutationen ist besonders nützlich, wenn die Elemente einer Menge keine natürliche Ordnung haben.

Manchmal wird eine Permutation veranschaulicht, indem man den Satz vor und nach der Permutation mit einem Pfeil von jedem Element an seine neue Position zeigt. So können beispielsweise die Permutationen {1,3,2} und {2,1,3} wie folgt dargestellt werden:

Die Identitäts-Permutation einer Menge ist die Permutation, die die Menge unverändert lässt, oder die Funktion, die jedes Element auf sich selbst abbildet. In unserem Beispiel ist die Identitäts-Permutation {1,2,3}.

2. Zusammensetzung der Permutationen

Die Zusammensetzung von zwei Permutationen der gleichen Menge ist nur die Zusammensetzung der zugehörigen Funktionen. So können beispielsweise die Permutationen {1,3,2} und {2,1,3} zusammengesetzt werden, indem man das Ziel jedes Elements verfolgt.

Daher {1,3,2} ◌ {2,1,3} = {2,3,1}.

Ebenso kann gezeigt werden, dass {2,1,3} ◌ {1,3,2} = {3,1,2} = {3,1,2}.

Dieses einfache Beispiel zeigt, dass die Zusammensetzung nicht unbedingt kommutativ ist (aber sie ist assoziativ).

Die Vorgänge können grafisch übersichtlicher dargestellt werden:

Wenn I eine Identitätspermutation ist und P eine beliebige Permutation derselben Menge ist, dann ist es klar, dass I ◌ P = P ◌ I = P. Es gibt auch eine umgekehrte Permutation P-1, für die P-1 ◌ P = P ◌ P-1 = P-1 = I. Sie kann gefunden werden, indem man die funktionale Inverse nimmt, oder indem man jedes geordnete Paar in der Definition einer Funktion als eine Menge geordneter Paare umkehrt (und dann die geordneten Paare nach ihren neuen ersten Elementen sortiert).

Zum Beispiel ist der Umkehrschluss von {2,3,1} der Umkehrschluss von {(1,2), (2,3), (3,1)}, der {(2,1), (3,2), (1,3)} oder {(1,3), (2,1), (3,2)} oder {3,1,2} ist.

Obwohl die Zusammensetzung von Permutationen im Allgemeinen nicht kommutativ ist, ist sie kommutativ, wenn eine der Permutationen oder das Ergebnis die Identität ist.

3. Gerade und ungerade Permutationen

Sei p eine Permutation der Menge S = {1,2,3,….,n} (oder jede andere total geordnete endliche Menge). Betrachten Sie ein Paar (i,j) von Elementen in S, für die i<j. Wenn p(i) > p(j) dann soll die Permutation die Reihenfolge von (i,j) umkehren.

Die Anzahl solcher Paare, die durch eine Permutation invertiert werden, ist keine sehr nützliche Eigenschaft einer Permutation, aber ob die Zahl gerade oder ungerade ist, erweist sich als eine nützliche Eigenschaft, die als Parität der Permutation bezeichnet wird. Wenn die Permutation eine gerade Anzahl solcher Paare invertiert, gilt sie als gerade Permutation; wenn sie eine ungerade Anzahl solcher Paare invertiert, gilt sie als seltsame Permutation.

Die Identitätspermutation ist offensichtlich gerade; {2,1} ist ein Beispiel für eine seltsame Permutation.

Obwohl es den Anschein haben mag, dass die Definition von geraden und ungeraden Permutationen von der Reihenfolge der Menge abhängt, werden wir beweisen, dass dies nicht der Fall ist.

Ein Austausch ist eine Permutation, die zwei Elemente miteinander verbindet und alle anderen Elemente unbeweglich lässt.

Kurztitel 3.1. Die Transponierung von zwei Elementen einer Permutation einer endlichen Menge, die der Komposition mit einem Austausch entspricht, ändert eine gerade Permutation in eine ungerade Permutation und umgekehrt.

Beweis. Zuerst wird die Lemma für zwei benachbarte Elemente ermittelt.

Lassen Sie {p(1), p(2), …., p(n)} eine Permutation von {1,2,…,n} sein und lassen Sie k eine ganze Zahl zwischen 1 und n-1 sein, einschließlich. Dann ist die Permutation {p(1), p(2), …., p(k+1), p(k), p(k), …., p(n)} die Permutation mit zwei benachbarten Elementen p(k) und p(k+1) ausgetauscht.

Wenn wir in der neuen Permutation invertierte Paare zählen, sehen wir, dass alle Paare, die in der alten Permutation invertiert wurden, auch in der neuen Permutation invertiert werden und umgekehrt, mit Ausnahme des Paares (k, k+1), das von invertiert zu nicht invertiert wechselt, oder umgekehrt. Daher ist die Anzahl der invertierten Paare in der neuen Permutation 1 mehr oder weniger als die Anzahl in der alten Permutation. Dadurch wird die Lemma für benachbarte Paare festgelegt.

Nun sollten i und j zwei nicht aufeinanderfolgende ganze Zahlen zwischen 1 und n sein, einschließlich, wobei i < j, und die Permutation berücksichtigen, in der p(i) und p(j) ausgetauscht wurden. Wir können dies durch eine Reihe von Austauschen aufeinanderfolgender Elemente erreichen. Wir bewegen p(i) bis zur j-ten Position durch j-i Austausch von aufeinanderfolgenden Elementen. Zuerst tauschen wir p(i) mit p(i+1), dann tauschen wir p(i) (das sich jetzt in der (i+1)-ten Position befindet) mit p(i+2), und so weiter, bis p(i) die zuvor von p(j) eingenommene Position erreicht. Das folgende Beispiel, in dem i=5 und j=9, soll diesen Prozess verdeutlichen:

p(5), p(6), p(7), p(8), p(8), p(9)
———-
Austausch

p(6), p(5), p(7), p(8), p(8), p(9)
———-
Austausch

p(6), p(7), p(5), p(8), p(9)
———-
Austausch

p(6), p(7), p(8), p(5), p(9)
———-
Austausch

p(6), p(7), p(8), p(9), p(5)

Dann führen wir eine ähnliche Sequenz von j-i-1-Austauschen in die entgegengesetzte Richtung durch, um p(j) zu der Position zu bewegen, die früher von p(i) besetzt war. In unserem Beispiel:

p(6), p(7), p(8), p(9), p(5)
———-
Austausch

p(6), p(7), p(9), p(8), p(8), p(5)
———-
Austausch

p(6), p(9), p(7), p(8), p(8), p(5)
———-
Austausch

p(9), p(6), p(7), p(8), p(8), p(5)

Das Ergebnis ist die ursprüngliche Permutation mit dem Austausch von p(i) und p(j) und anderen Elementen in ihrer ursprünglichen Position. Die Anzahl der Austausche aufeinanderfolgender Elemente ist (j-i) + (j-i-1), was ungerade ist. Daher wurde die Permutation von gerade auf ungerade oder umgekehrt geändert. ?

Beachten Sie, dass diese Lemma nur gilt, wenn der Tausch nach der Permutation durchgeführt wird. Es ist jedoch klar, dass ein Austausch von i mit j vor einer Permutation p gleichbedeutend ist mit einem Austausch von p(i) und p(j) nach der Permutation. Daher gilt in beiden Fällen die Lemma.

Satz 3.2. Jede Permutation ist eine Zusammensetzung von Börsen und ist eine gerade Permutation, wenn, und nur wenn, die Anzahl der Börsen gerade ist.

Beweis. Lassen Sie {p(1), p(2)…., p(n)} eine Permutation sein. Beginnen Sie mit {1,2,….,n}. Wenn p(1) nicht 1 ist, dann bringt ein einziger Austausch es an die erste Position. Wenn p(2) nicht 2 ist, dann bringt ein einziger Austausch es an die zweite Position. Auf diese Weise können wir {p(1), p(2)…., p(n)} als eine Zusammensetzung von Austauschen produzieren. Der andere Teil ist eine Folge von Lemma 3.1. ?

Beachten Sie, dass diese Charakterisierung von ungeraden und geraden Permutationen nicht von der Reihenfolge der Elemente abhängt.

Folgerung 3.3. Die Zusammensetzung von zwei Permutationen endlicher Mengen ist gerade, wenn und nur wenn, die beiden Permutationen beide gerade oder beide ungerade sind.

Folgerung 3.4. Eine Permutation einer endlichen Menge und deren Umkehrung sind beide gerade oder beide ungerade.

Lehrsatz 3.5. Eine endliche Menge mit zwei oder mehr Elementen hat die gleiche Anzahl von geraden und ungeraden Permutationen.

Beweis. Für jede gerade Permutation können wir eine einzigartige ungerade Permutation erhalten, indem wir die ersten beiden Elemente transponieren. Dies definiert eine Eins-zu-Eins-Korrespondenz zwischen geraden und ungeraden Permutationen, so dass es jeweils gleich viele gibt. ?

Eine Permutation kann dazu führen, dass einige Elemente der Menge fixiert bleiben. Zum Beispiel ist {1,3,2,5,4} eine gerade Permutation, die das Element 1 fixiert. Wenn wir nur die Auswirkungen auf {2,3,4,5} betrachten, haben wir eine Permutation eines Vier-Elemente-Satzes, der ebenfalls gerade ist. Der folgende Satz gibt ein allgemeineres Ergebnis.

Satz 3.6. Wenn eine Permutation ein oder mehrere Elemente fixiert lässt, dann hat die auf andere Elemente beschränkte Permutation die gleiche Parität wie die ursprüngliche Permutation.

Beweis. Die eingeschränkte Permutation kann in eingeschränkte Börsen zerlegt werden. Diese Austausche, wenn sie auf den gesamten Satz ausgedehnt werden, ergeben die ursprüngliche Permutation. Daher sind beide Permutationen gerade oder ungerade. ? ?

4. Das Fünfzehn-Kachel-Puzzle

Ein beliebtes Puzzle besteht aus einem Satz von fünfzehn Schiebefliesen in einem 4 ⨯ 4 Quadrat:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15

Die sechzehnte Position ist leer. Die Fliesen können neu angeordnet werden, indem benachbarte Fliesen in den Rohling verschoben werden. Durch wiederholte Züge dieser Art können wir die Kacheln neu anordnen, wie in diesem Beispiel:

1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8
9 10 11 12 9 10 11 12 9 10 12
13 15 14 13 15 14 13 15 11 14

1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8
9 10 12 9 10 12 14
13 15 11 14 13 15 11

Angenommen, wir wollen das folgende Ergebnis erzielen:

1 2 3 4
5 6 7 8
9 10 11 12
13 15 14

Es ist leicht zu zeigen, dass dies unmöglich ist. Jede Anordnung ist eine Permutation von sechzehn Elementen, wobei das Leerzeichen als das sechzehnte Element betrachtet wird. Jeder Zug beinhaltet den Austausch einer Kachel mit dem Leerraum. Die Anzahl der Züge muss gerade sein, denn der Raum muss sich auf und ab bewegen, wenn er in seine ursprüngliche Position in der rechten unteren Ecke zurückgebracht werden soll.

Das gewünschte Ergebnis ist eine seltsame Permutation, da sie aus einem einzigen Austausch resultiert. Daher ist es nicht in der angegebenen Weise erreichbar.

Zur Akkuschrauber Homepage