7.2: Перестановки та комбінації
- Page ID
- 32759
- Обговорюються основи комбінацій і перестановок, а також способи обчислення ймовірності певних подій, таких як n-бітові помилки в кодовому слові.
Лотерея «гра» складається з підбору
Відповісти на такі питання зустрічається в багатьох додатках поза іграми. Наприклад, у цифрових комунікаціях ви можете запитати, скільки можливих двобітових помилок може виникнути в кодовому слові. Нумерація бітових позицій від 1 до N, відповідь така ж, як і проблема лотереї з k = 6. Рішення такого роду проблем зводиться до розуміння перестановок - кількість способів вибору речей, коли порядок має значення, як в бейсбольних складах - і комбінацій - кількість способів вибору речей, коли порядок не має значення, як в лотереях і бітові помилки.
Обчислення перестановок найпростіше. Якщо ми збираємося вибрати k чисел з пулу n, у нас є n варіантів для першого. Для другого вибору ми маємо n-1. Отже, кількість впорядкованих послідовностей довжини дорівнює n (n-1). Продовжуючи вибирати, поки ми не зробимо вибір k означає, що кількість перестановок дорівнює
\[n(n-1)(n-2)...(n-k+1) \nonumber \]
Цей результат можна записати в терміні факторіалів як
\[\frac{n!}{(n-k)!} \nonumber \]
із
\[n!=n(n-1)(n-2)...1 \nonumber \]
Для математичної зручності визначаємо 0! =1.
Коли порядок не має значення, кількість комбінацій дорівнює кількості перестановок, поділених на кількість замовлень. Кількість способів, якими можна замовити пул k речей дорівнює k! . Таким чином, як тільки ми виберемо дев'ять стартерів для нашої гри в бейсбол, ми маємо
\[9!=362,880 \nonumber \]
різні склади! Символ для поєднання k речей, витягнутих з басейну n є
\[\binom{n}{k} \nonumber \]
і дорівнює
\[\frac{n!}{(n-k)!k!} \nonumber \]
Які шанси виграти в лотерею? Припустімо, ви вибираєте 6 номерів з чисел 1-60.
Рішення
\[\binom{60}{6}=\frac{60!}{54!6!}=50,063,860 \nonumber \]
Комбінаторії відбуваються в цікавих місцях. Наприклад, Ньютон вивів, що n -а сила суми підпорядковується формулі
\[(x+y)^{n}=\binom{n}{0}x^{n}+\binom{n}{1}x^{n-1}y+\binom{n}{2}x^{n-2}y^{2}+...+\binom{n}{n}y^{n} \nonumber \]
Що дорівнює сума біноміальних коефіцієнтів? Іншими словами, що таке
\[\sum_{k=0}^{n}\binom{n}{k} \nonumber \]
Рішення
Через біноміальну теорему Ньютона сума дорівнює
\[(1+1)^{n}=2^{n} \nonumber \]
Пов'язана проблема обчислення ймовірності того, що будь-які два біти помиляються в length-
\[p^{2}(1-p)^{n-2} \nonumber \]
Імовірність виникнення двобітної помилки в будь-якому місці дорівнює цій ймовірності, що помножується на кількість комбінацій:
\[\binom{n}{2}p^{2}(1-p)^{n-2} \nonumber \]
Зверніть увагу, що ймовірність того, що нуль або один-два і т.д. помилки виникають, повинна бути одна; іншими словами, щось має статися з кодовим словом! Це означає, що ми повинні мати
\[\binom{n}{0}(1-p)^{n}+\binom{n}{1}(1-p)^{n-1}+\binom{n}{2}p^{2}(1-p)^{n-2}+...+\binom{n}{n}p^{n}=1 \nonumber \]
Чи можете ви це довести?