Überzählung verstehen

Question

Ich versuche zu verstehen, wie man sich auf Überzählungen einstellt. Ich finde das folgende Beispiel sehr schwer zu verstehen, dh ich verstehe alle Wörter und ihre Bedeutungen, aber ich habe Mühe, mich "überzeugt" zu fühlen.

Zeige, dass:

$$\frac{(2 n) !}{2^{n} \cdot n !}=(2 n-1)(2 n-3) \cdots 3 \cdot 1$$

Intuitive Erklärung (über eine Geschichte) aus dem Lehrbuch:

\ begin {array} {l} \ text {Wir werden zeigen, dass beide Seiten die Anzahl der Wege zählen, um} 2 n \\ \ text {Personen in} n \ text {Partnerschaften aufzubrechen. Nehmen Sie} 2 n \ text {Personen und geben Sie ihnen ID-Nummern von} 1 \ text {bis} \\ 2 n \ text {. Wir können Partnerschaften eingehen, indem wir die Leute in einer bestimmten Reihenfolge aneinanderreihen und dann sagen:} \\ \ text {die ersten beiden sind ein Paar, die nächsten beiden sind ein Paar usw. Dies überzählt um einen Faktor} \\ \ text {of} n! \ cdot 2 ^ {n} \ text {da die Reihenfolge der Paare keine Rolle spielt, spielt auch die Reihenfolge innerhalb der einzelnen} \\ \ text {Paare keine Rolle. Alternativ können Sie die Anzahl der Möglichkeiten zählen, indem Sie feststellen, dass} 2 n-1 \\ \ text {Auswahlmöglichkeiten für den Partner der Person} 1, \ text {dann} 2 n-3 \ text {Auswahlmöglichkeiten für die Person} 2 \ text vorhanden sind {(oder Person} 3, \ text {if} \\ \ text {person} 2 \ text {wurde bereits mit person} 1 \ text {) gepaart und so weiter. } \ end {array}

Kann mir jemand erklären 1) warum der Faktor ist $n! \cdot 2^n$ und 2) wie wird die RHS abgeleitet?

Answer 1

Der erste Teil sagt, wenn wir ABCDEF sagen, dann ist (AB) (CD) (EF) = (BA) (CD) (EF) und auch (AB) (CD) (EF) = (CD) (AB) ( EF), wobei es gibt $2^n$ Variationen des ersten Typs und $n!$ Variationen der Sekunde.

Dann haben wir auch $A$ kann mit zusammengearbeitet werden $BCDEF$, dann mysteriöse Person $x$ kann mit den übrigen zusammenarbeiten $3$, usw. .

Und $\frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{8\cdot3\cdot2\cdot1} = \frac{6\cdot5\cdot4\cdot3\cdot2\cdot1}{6\cdot4\cdot2} = 5\cdot3\cdot1$.