2.2: Перестановки заборонених позицій
- Page ID
- 64365
Припустимо, ми перетасуємо колоду карт; яка ймовірність того, що жодна карта не знаходиться в первісному місці? У загальному плані, скільки перестановок не\([n]=\{1,2,3,\ldots,n\}\) мають жодного з цілих чисел у своїх «правильних» місцях? Тобто 1 не перший, 2 - не другий і так далі. Така перестановка називається розбіжністю\([n]\).
\(S\)Дозволяти бути набір всіх перестановок\([n]\) і\(A_i\) бути перестановками\([n]\) в яких\(i\) знаходиться в правильному місці. Тоді ми хочемо знати\(|\bigcap_{i=1}^n A_i^c|\).
Для any\(i\),\(|A_i|=(n-1)!\): один раз\(i\) фіксується в положенні\(i\), решта\(n-1\) цілих чисел можна розмістити в будь-яких місцях.
А як щодо\(|A_i\cap A_j|\)? Якщо обидва\(i\) і\(j\) знаходяться в правильному положенні, решта\(n-2\) цілих чисел можна розмістити в будь-якому місці, так що\(|A_i\cap A_j|=(n-2)!\).
Таким же чином ми це бачимо\(|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|=(n-k)!\). Таким чином, за формулою включення-виключення, у вигляді Рівняння 2.1.1,
\[\eqalign{ |\bigcap_{i=1}^n A_i^c|&=|S|+\sum_{k=1}^n (-1)^k{n\choose k}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!(n-k)!}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!}\cr &=n!+n!\sum_{k=1}^n (-1)^k{1\over k!}\cr &=n!\,\Bigl(1+\sum_{k=1}^n (-1)^k{1\over k!}\Bigr)\cr &=n!\,\sum_{k=0}^n (-1)^k{1\over k!}.\cr }\nonumber\]
Остання сума повинна виглядати знайомою\[e^x=\sum_{k=0}^\infty {1\over k!}x^k.\nonumber\]: Заміна\(x=-1\) дає\[e^{-1} = \sum_{k=0}^\infty {1\over k!}(-1)^k.\nonumber\] Імовірність отримання розбіжності випадково\(n\) є тоді,\[{1\over n!}n!\,\sum_{k=0}^n (-1)^k{1\over k!} =\sum_{k=0}^n (-1)^k{1\over k!},\nonumber\] а коли більше 6, це досить близько до\[e^{-1} \approx 0.3678.\nonumber\] Так що у випадку з колодою карт ймовірність розбіжності становить близько 37 %.
Нехай\(D_n=n!\,\sum_{k=0}^n (-1)^k{1\over k!}\). Ці номери розбіжності мають деякі цікаві властивості. Порушення\([n]\) можуть бути вироблені наступним чином: Для кожного\(i\in\{2,3,\ldots,n\}\) поставте\(i\) в положення 1 і 1 в положення\(i\). Потім перемкніть цифри\(\{2,3,\ldots,i-1,i+1,\ldots n\}\) всіма можливими способами, щоб жоден з цих\(n-2\) чисел не знаходився в правильному місці. Для цього є\(D_{n-2}\) способи. Потім, утримуючи 1 в положенні\(i\), derange числа\(\{i,2,3,\ldots,i-1,i+1,\ldots n\}\), при цьому «правильне» положення\(i\) тепер вважається позицією 1. Для цього є\(D_{n-1}\) способи. Таким чином,\(D_n=(n-1)(D_{n-1}+D_{n-2})\).
Ми трохи досліджуємо це відношення повторення:
\[\eqalignno{ D_n&=nD_{n-1}-D_{n-1}+(n-1)D_{n-2}&(*)\cr &=nD_{n-1}-(n-2)(D_{n-2}+D_{n-3})+(n-1)D_{n-2}\cr &=nD_{n-1}-(n-2)D_{n-2}-(n-2)D_{n-3}+(n-1)D_{n-2}\cr &=nD_{n-1}+D_{n-2}-(n-2)D_{n-3}&(*)\cr &=nD_{n-1}+(n-3)(D_{n-3}+D_{n-4})-(n-2)D_{n-3}\cr &=nD_{n-1}+(n-3)D_{n-3}+(n-3)D_{n-4}-(n-2)D_{n-3}\cr &=nD_{n-1}-D_{n-3}+(n-3)D_{n-4}&(*)\cr &=nD_{n-1}-(n-4)(D_{n-4}+D_{n-5})+(n-3)D_{n-4}\cr &=nD_{n-1}-(n-4)D_{n-4}-(n-4)D_{n-5}+(n-3)D_{n-4}\cr &=nD_{n-1}+D_{n-4}-(n-4)D_{n-5}.&(*)\cr }\nonumber\]
З зіркових рядків з'являється, що візерунок тут полягає в тому, що\[D_n=nD_{n-1}+(-1)^kD_{n-k}+(-1)^{k+1}(n-k)D_{n-k-1}.\nonumber\] Якщо це продовжується, ми повинні дістатися до\[D_n=nD_{n-1}+(-1)^{n-2}D_{2}+(-1)^{n-1}(2)D_{1}.\nonumber\] Оскільки\(D_2=1\) і\(D_1=0\), це дасть\[D_n=nD_{n-1}+(-1)^n,\nonumber\] з тих пір\( (-1)^n=(-1)^{n-2}\). Дійсно, це правда, і може бути доведено індукцією. Це дає дещо простіший зв'язок повторення, що робить його досить легким для обчислення\(D_n\).
\[\bullet\quad\bullet\quad\bullet\nonumber\]
Подібних проблем багато.
Приклад \(\PageIndex{1}\)
Скільки перестановок\([n]\) містять жодного екземпляра, за\(i\) яким слідують\(i+1\)?
Рішення
Аналогічним використанням формули включення-виключення виходить, що це\[Q_n=n!\,\sum_{k=0}^{n-1} (-1)^k{1\over k!}+ (n-1)!\,\sum_{k=1}^{n-1} (-1)^{k-1} {1\over (k-1)!}. \nonumber\] Зверніть увагу, що обмеження на дві суми не однакові.