Memahami overcounting

Question

Saya mencoba memahami cara menyesuaikan overcounting. Saya menemukan contoh berikut ini sangat sulit untuk dipahami, yaitu, saya memahami semua kata dan artinya, tetapi saya berjuang untuk merasa "diyakinkan".

Menunjukkan bahwa:

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

Penjelasan intuitif (melalui cerita) yang diberikan oleh buku teks:

\ begin {array} {l} \ text {Kami akan menunjukkan bahwa kedua sisi menghitung jumlah cara untuk memutuskan} 2 n \\ \ text {orang menjadi} n \ text {kemitraan. Ambil} 2 n \ text {orang, dan beri mereka nomor ID dari} 1 \ text {to} \\ 2 n \ text {. Kita bisa membentuk kemitraan dengan mengantre orang dalam beberapa urutan dan kemudian berkata} \\ \ text {dua yang pertama adalah pasangan, dua berikutnya adalah pasangan, dll. Ini dikalikan dengan faktor} \\ \ text {of} n! \ cdot 2 ^ {n} \ text {karena urutan pasangan tidak menjadi masalah, begitu pula urutan dalam setiap pasangan} \\ \ text {. Sebagai alternatif, hitung jumlah kemungkinan dengan mencatat bahwa ada} 2 n-1 \\ \ teks {pilihan untuk pasangan orang} 1, \ teks {lalu} 2 n-3 \ teks {pilihan untuk orang} 2 \ teks {(or person} 3, \ text {if} \\ \ text {person} 2 \ text {sudah dipasangkan dengan person} 1 \ text {), dan seterusnya. } \ end {array}

Adakah yang bisa menjelaskan kepada saya 1) mengapa faktornya $n! \cdot 2^n$ dan 2) bagaimana RHS diturunkan?

Answer 1

Bagian pertama mengatakan jika kita mengatakan ABCDEF, maka (AB) (CD) (EF) = (BA) (CD) (EF), dan juga (AB) (CD) (EF) = (CD) (AB) ( EF), dengan adanya $2^n$ variasi jenis pertama, dan $n!$ variasi kedua.

Lalu kami juga punya $A$ dapat bermitra dengan $BCDEF$, lalu orang misterius $x$ dapat bermitra dengan yang tersisa $3$, dll.

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