Zrozumieć overcounting

Question

Próbuję zrozumieć, jak dostosować się do nadmiernego liczenia. Poniższy przykład jest dla mnie bardzo trudny do zrozumienia, tzn. Rozumiem wszystkie słowa i ich znaczenie, ale trudno mi się „przekonać”.

Pokazują, że:

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

Intuicyjne wyjaśnienie (poprzez opowieść) podane w podręczniku:

\ begin {tablica} {l} \ text {Pokażemy, że obie strony liczą liczbę sposobów na złamanie} 2 n \\ \ text {osób do} n \ text {partnerstwa. Weź} 2 n \ text {osób i nadaj im numery identyfikacyjne od} 1 \ text {to} \\ 2 n \ text {. Możemy tworzyć partnerstwa, ustawiając ludzi w pewnej kolejności, a następnie mówiąc:} \\ \ text {pierwsze dwa to para, następne dwa to para itd. To przekracza o czynnik} \\ \ text {of} n! \ cdot 2 ^ {n} \ text {ponieważ kolejność par nie ma znaczenia, podobnie jak kolejność w każdej z nich} \\ \ text {para. Alternatywnie, policz liczbę możliwości, zauważając, że są} 2 n-1 \\ \ text {wybory dla partnera osoby} 1, \ text {wtedy} 2 n-3 \ text {wybory dla osoby} 2 \ text {(lub osoba} 3, \ text {if} \\ \ text {osoba} 2 \ text {została już sparowana z osobą} 1 \ text {) i tak dalej. } \ end {tablica}

Czy ktoś może mi wyjaśnić 1), dlaczego tak jest $n! \cdot 2^n$ i 2) w jaki sposób wyprowadza się RHS?

Answer 1

Pierwsza część mówi, że jeśli powiemy ABCDEF, to (AB) (CD) (EF) = (BA) (CD) (EF), a także (AB) (CD) (EF) = (CD) (AB) ( EF), gdzie istnieje $2^n$ odmiany pierwszego typu i $n!$ wariacje drugiego.

Mamy też $A$ można nawiązać współpracę $BCDEF$, a następnie tajemnicza osoba $x$ może współpracować z pozostałymi $3$itp.

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