In der kombinatorischen Mathematik ist ein Durcheinander eine Versetzung der Elemente eines solchen Satzes, dass keines der Elemente in ihrer ursprünglichen Position erscheint.

Die Zahlen des Durcheinanders! n für Sätze der Größe werden n "Zahlen von de Montmort" oder "Durcheinander-Zahlen" genannt (und kann zu rencontres Zahlen verallgemeinert werden); die Subfactorial-Funktion (um mit dem factorial n nicht verwirrt zu sein!) stellt n dazu kartografisch dar! n. Keine Standardnotation für subfactorials ist vereinbart, und n¡ wird manchmal statt verwendet! n.

Das Problem des Zählens des Durcheinanders wurde zuerst von Pierre Raymond de Montmort 1708 betrachtet; er hat es 1713 gelöst, wie Nicholas Bernoulli in ungefähr derselben Zeit getan hat.

Beispiel

Nehmen Sie an, dass ein Professor 4 Tests auf 4 Studenten - Student A, Student B, Student C und Student D. However sortiert hat, hat der Professor die Tests verwechselt, als er sie zurückgegeben hat, und jetzt hat keiner der Studenten den richtigen Test. Wie viele Wege könnte der Professor sie alle auf diese Weise gemischt haben? Aus, für die Tests zurückzugeben, gibt es nur 9 Durcheinander:

:BADC, BCDA, BDAC,

:CADB, CDAB, CDBA,

:DABC, DCAB, DCBA.

In jeder anderen Versetzung dieses 4-Mitglieder-Satzes bekommt mindestens ein Student den richtigen Test.

Eine andere Version des Problems entsteht, wenn wir um die Zahl von Wegen n Briefe bitten, jeder, der an eine verschiedene Person angeredet ist, kann in vorgerichtete Umschläge von n gelegt werden, so dass kein Brief im richtig gerichteten Umschlag erscheint.

Das Aufzählen des Durcheinanders

Nehmen Sie an, dass es n Personen gezählt 1, 2..., n gibt. Lassen Sie dort, n Hüte zu sein, auch hat 1, 2..., n numeriert. Wir müssen die Zahl von Wegen finden, auf die keiner den Hut bekommt, der dieselbe Zahl wie seine/ihre Zahl hat. Lassen Sie uns annehmen, dass die erste Person den Hut i nimmt. Es gibt n − 1 Wege für die erste Person, um die Nummer i zu wählen. Jetzt gibt es 2 Optionen:

1. Person nehme ich den Hut 1 nicht. Dieser Fall ist zum Beheben des Problems mit n &minus gleichwertig; 1 Personen n − 1 Hüte: jeder der restlichen n − 1 Menschen haben genau 1 verbotene Wahl aus der Zahl vom restlichen n − 1 Hüte (habe ich Wahl verboten ist Hut 1).
2. Person i nimmt den Hut 1. Jetzt nimmt das Problem zu n &minus ab; 2 Personen und n − 2 Hüte.

Davon wird die folgende Beziehung abgeleitet:

Bemerken Sie, dass diese dieselbe Wiederauftreten-Formel auch für factorials mit verschiedenen Startwerten arbeitet. Das ist 0! = 1, 1! = 1 und

der im Beweis der Grenze-Beziehung mit e unten nützlich ist.

Außerdem sind die folgenden Formeln bekannt:

wo die Fußboden-Funktion ist. Mit n = 0 anfangend, sind die Zahlen des Durcheinanders von n:

:1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932....

Diese Zahlen werden auch subfactorial oder rencontres Zahlen genannt.

Vielleicht verwendet eine wohl bekanntere Methode, Durcheinander aufzuzählen, den Einschließungsausschluss-Grundsatz.

Grenze als n nähert sich ∞

Mit diesem Wiederauftreten kann es dass, in der Grenze, gezeigt werden

Das ist die Grenze der Wahrscheinlichkeit p = d/n! dass eine zufällig ausgewählte Versetzung ein Durcheinander ist. Die Wahrscheinlichkeit nähert sich dieser Grenze ganz schnell.

Mehr Information über diese Berechnung und die obengenannte Grenze kann auf der Seite auf dem gefunden werden

Statistik von zufälligen Versetzungen.

Generalisationen

Der problème des rencontres fragt, wie viele Versetzungen eines Satzes der Größe-n genau k befestigte Punkte haben.

Durcheinander ist ein Beispiel des breiteren Feldes von gezwungenen Versetzungen. Zum Beispiel fragt das ménage Problem, ob n Ehepaare "Junge-Mädchen-Junge-Mädchen"... um einen Rundtisch gesetzt werden, wie viele Wege können sie gesetzt werden, so dass kein Mann neben seiner Frau gesetzt wird?

Mehr formell, gegeben Sätze A und S, und einige Sätze U und V von Surjektionen → S möchten wir häufig die Zahl von Paaren von Funktionen (f, g) solch wissen, dass f in U ist und g in V, und für alle in A, f (a) &ne ist; g (a); mit anderen Worten, wo für jeden f und g, dort ein Durcheinander &phi besteht; solchen S dass f (a) = φ (g (a)).

Eine andere Generalisation ist das folgende Problem:

:How viele Anagramme ohne feste Briefe eines gegebenen Wortes sind dort?

Zum Beispiel, für ein aus nur zwei verschiedenen Briefen gemachtes Wort, sagen Sie n Briefe A und M Briefe B, die Antwort, ist natürlich, 1 oder 0 gemäß, ob n = M oder nicht, für die einzige Weise, ein Anagramm ohne feste Briefe zu bilden, ganz mit B wert sein soll, der wenn und nur wenn n = M möglich ist. Im allgemeinen Fall, für ein Wort mit n Briefen der Briefe X, n X..., n Briefe X erweist es sich (nach einem richtigen Gebrauch der Einschließungsausschluss-Formel), dass die Antwort die Form hat:

für eine bestimmte Folge von Polynomen P, wo P Grad n hat. Aber die obengenannte Antwort für den Fall r = 2 gibt eine orthogonality Beziehung, woher Ps sind die Polynome von Laguerre (bis zu einem Zeichen, das leicht entschieden wird).

Außenverbindungen