7.2: Перестановки та комбінації

Цілі навчання

• Обговорюються основи комбінацій і перестановок, а також способи обчислення ймовірності певних подій, таких як 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$$

Вправа$\PageIndex{1}$

Які шанси виграти в лотерею? Припустімо, ви вибираєте 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$$

Вправа$\PageIndex{1}$

Що дорівнює сума біноміальних коефіцієнтів? Іншими словами, що таке

$$\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$$

Чи можете ви це довести?