1.5: Числа дзвонів

Почнемо з визначення:

Визначення\(\PageIndex{1}\): Partition

Розділ множини\(S\) - це збірка непорожніх підмножин\(A_i\subseteq S\),\(1\le i\le k\) (частин розділу), таких, що\(\bigcup_{i=1}^k A_i=S\) і для кожного\(i\not=j\),\(A_i\cap A_j=\emptyset\).

Приклад\(\PageIndex{1}\):

Перегородками набору\(\{a,b,c\}\) є\(\{\{a\},\{b\},\{c\}\}\),\(\{\{a,b\},\{c\}\}\),\(\{\{a,c\},\{b\}\}\),\(\{\{b,c\},\{a\}\}\), і\(\{\{a,b,c\}\}\).

Перегородки виникають в ряді областей математики. Наприклад, якщо\(\equiv\) є співвідношенням еквівалентності на\(S\) множині, класи еквівалентності\(\equiv\) утворюють розділ\(S\). Тут ми розглянемо кількість розділів скінченної множини\(S\), які ми могли б також прийняти, щоб бути\([n]=\{1,2,3,\ldots,n\}\), якщо якийсь інший набір не представляє інтересу. Позначимо кількість розділів\(n\) -елемента, встановленого\(B_n\); ці числа є числами Белла. З наведеного вище прикладу ми бачимо, що\(B_3=5\). Для зручності пускаємо\(B_0=1\). Це досить легко помітити, що\(B_1=1\) і\(B_2=2\).

Не існує відомих простих формул для\(B_n\), тому ми задовольняємося рекуррентним співвідношенням.

Теорема \(\PageIndex{1}\): Bell Numbers

Числа Белла задовольняють\[ B_{n+1} = \sum_{k=0}^n {n\choose k} B_k.\nonumber \]

Доказ

Розглянемо перегородку з\(S=\{1,2,\ldots,n+1\}\),\(A_1\),...,\(A_m\). Ми можемо припустити, що\(n+1\) є в\(A_1\), і що\(|A_1|=k+1\), для деяких\(k\),\(0\le k\le n\). Потім\(A_2\),...,\(A_{m}\) формують перегородку з інших\(n-k\) елементів\(S\), тобто з\(S\backslash A_1\). Є\(B_{n-k}\) перегородки цього набору, тому є\(B_{n-k}\) перегородки,\(S\) в яких одна частина - набір\(A_1\). Існують\({n\choose k}\) набори розміру\(n+1\),\(k+1\) що містять, тому загальна кількість розділів\(S\) в яких\(n+1\) знаходиться в наборі розміру\(k+1\) дорівнює\({n\choose k}B_{n-k}\). Складання над усіма можливими значеннями\(k\), це означає\[\label{eq:1} \eqalignno{ B_{n+1} &= \sum_{k=0}^n {n\choose k} B_{n-k}. }\]

Ми можемо переписати це, використовуючи теорему 1.4.2,\[B_{n+1} = \sum_{k=0}^n {n\choose n-k} B_{n-k},\nonumber\] а потім помітити, що це те саме, що сума\[B_{n+1} = \sum_{k=0}^n {n\choose k} B_k,\nonumber\] записана назад.

Приклад\(\PageIndex{2}\)

Ми застосовуємо повторення для обчислення перших кількох чисел Белла:

\[ \eqalign{ B_1&=\sum_{k=0}^0 {0\choose 0}B_0 = 1\cdot 1 = 1\cr B_2&=\sum_{k=0}^1 {1\choose k}B_k = {1\choose 0}B_0 + {1\choose 1}B_1 = 1\cdot 1+1\cdot 1 =1+1 =2\cr B_3&=\sum_{k=0}^2 {2\choose k}B_k = 1\cdot 1 + 2\cdot 1 + 1\cdot 2 = 5\cr B_4&=\sum_{k=0}^3 {3\choose k}B_k = 1\cdot 1 + 3\cdot 1 + 3\cdot 2 + 1\cdot 5 = 15\cr }\nonumber \]

Числа Белла зростають експоненціально швидко; перші кілька: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437.

Числа Белла з'являються у багатьох інших проблемах; ось цікавий приклад. Загальною потребою в деяких комп'ютерних програмах є генерація випадкової перестановки\(1,2,3,\ldots,n\), яку ми можемо думати як перетасування чисел, візуалізованих як пронумеровані карти в колоді. Ось привабливий метод, який легко програмувати: Почніть з чисел по порядку, потім на кожному кроці видаліть одне число навмання (це легко в більшості мов програмування) і поставте його перед списком чисел. (Розглядається як перетасування колоди карт, це відповідає видаленню карти та покладенню її на верхню частину колоди.) Скільки разів ми повинні це робити? Магічного числа немає, але воно звичайно не повинно бути маленьким щодо розміру\(n\). Давайте виберемо в\(n\) якості кількості кроків.

Ми можемо написати такий shuffle як список\(n\) цілих чисел,\((m_1,m_2,\ldots,m_n)\). Це говорить про те\(i\), що на кроці число\(m_i\) переміщується спереду.

Приклад\(\PageIndex{3}\)

Давайте слідувати перетасуванню\((3,2,2,4,1)\):\[ \eqalign{ (3)&:\quad 3 1 2 4 5\cr (2)&:\quad 2 3 1 4 5\cr (2)&:\quad 2 3 1 4 5\cr (4)&:\quad 4 2 3 1 5\cr (1)&:\quad 1 4 2 3 5\cr } \nonumber\]

Рішення

Зверніть увагу, що ми дозволяємо «нічого не робити» рухається, видаляючи верхню карту, а потім розміщуючи її зверху. Кількість можливих перетасовок потім легко підрахувати: є\(n\) варіанти для вилучення картки, і це повторюється\(n\) раз, тому загальна кількість є\(n^n\). (Якщо ми продовжимо перетасування для\(m\) кроків, кількість перетасовок дорівнює\(n^m\).) Оскільки існують тільки\(n!\) різні перестановки\(1,2,\ldots,n\), це означає, що багато перетасовок дають однаковий остаточний порядок.

Приклад\(\PageIndex{4}\)

Ось наше питання: скільки перетасовок виходить в початковому порядку?

Рішення

Ці перетасовки повертаються до початкового порядку:\((1,1,1,1,1)\),\((5,4,3,2,1)\),\((4,1,3,2,1)\).

Теорема \(\PageIndex{2}\)

Кількість перетасовок\([n]\) цього результату в початковому відсортованому порядку дорівнює\(B_n\).

Доказ

Оскільки ми знаємо, що\(B_n\) підраховує кількість розділів\(\{1,2,3,\ldots,n\}\), ми можемо довести теорему, встановивши відповідність 1—1 між перетасовками, які залишають колоду відсортованою та перегородками. З огляду на\((m_1,m_2,\ldots,m_n)\) перетасування, ми ставимо в єдиний набір все\(i\) таке, що\(m_i\) має єдине значення. Наприклад, використовуючи shuffle\((4,1,3,2,1)\), так як\(m_2=m_5\), один набір є\(\{2,5\}\). Всі інші значення є різними, тому інші набори в розділі є\(\{1\}\)\(\{3\}\), і\(\{4\}\).

Зверніть увагу, що кожне перетасування, незалежно від того, який кінцевий порядок, виробляє перегородку цим методом. Нас цікавлять тільки перетасовки, які залишають колоду відсортованими. Що нам зараз потрібно, це показати, що кожен розділ є результатом саме одного такого перетасування.

Припустимо, у нас є перегородка з\(k\) деталями. Якщо перетасування залишає колоду відсортованою\(m_n\), останній запис має бути 1. Якщо частина, що містить\(n\) є\(A_1\), то вона повинна бути, що\(m_i=1\) якщо і тільки якщо\(i\in A_1\). Якщо\(k=1\), то єдина частина містить всі\(\{1,2,\ldots,n\}\), і перетасувати треба\((1,1,1,\ldots,1)\).

Якщо останній хід\(k>1\), який не є 1, повинен бути 2, оскільки 2 повинен закінчитися відразу після 1. Таким чином, якщо\(j_2\) найбільший індекс такий\(j_2\notin A_1\), що, нехай\(A_2\) буде частина\(j_2\), що містить, і це повинно бути, що\(m_i=2\) якщо і тільки якщо\(i\in A_2\). Ми продовжуємо таким чином: Після того, як ми виявили, які з\(m_i\) повинні мати значення\(1,2,\ldots,p\), нехай\(j_{p+1}\) найбільший індекс такий\(j_{p+1}\notin A_1\cup\cdots\cup A_p\), що, нехай\(A_{p+1}\) буде частина\(j_{p+1}\), що містить, а потім,\(m_i=p+1\) якщо і тільки якщо\(i\in A_{p+1}\). Коли\(p=k\), всі значення\(m_i\) були визначені, і це унікальна перетасовка, яка відповідає розділу.

Приклад\(\PageIndex{5}\)

Розглянемо перегородку\(\{\{1,5\},\{2,3,6\},\{4,7\}\}\). Ми повинні мати\(m_7=m_4=1\), і\(m_6=m_3=m_2=2\), таким чином\(m_5=m_1=3\), перетасувати є\((3,2,2,1,3,2,1)\).

Повертаючись до проблеми написання комп'ютерної програми для генерації розділу: чи хороший це метод? Коли ми говоримо, що хочемо випадкової перестановки, ми маємо на увазі, що ми хочемо, щоб кожна перестановка відбувалася з однаковою ймовірністю, а саме,\(1/n!\). Оскільки початковий порядок є однією з перестановок, ми хочемо, щоб кількість перетасовок, які його виробляють\(n^n/n!\), було точно, але\(n!\) не\(n^n\) ділиться, тому це неможливо. Імовірність отримання первісної перестановки є\(B_n/n^n\), і це виявляється зовсім трохи більше, ніж\(1/n!\). Таким чином, це не підходящий метод для генерації випадкових перестановок.

Відношення повторення вище є дещо громіздким способом обчислення чисел Белла. Інший спосіб їх обчислення - з різним повторенням, вираженим у трикутнику Белла, конструкція якого схожа на конструкцію трикутника Паскаля:\[\matrix{ A_{1,1}\cr A_{2,1}&A_{2,2}\cr A_{3,1}&A_{3,2}&A_{3,3}\cr A_{4,1}&A_{4,2}&A_{4,3}&A_{4,4}\cr} \qquad\matrix{ 1\cr 1&2\cr 2&3&5\cr 5&7&10&15\cr}\nonumber\]

Правило побудови цього трикутника:\(A_{1,1}=1\); перший запис у кожному рядку - останній запис у попередньому рядку; інші записи: рядок\(n\) містить\(n\) записи.\(A_{n,k}=A_{n,k-1}+A_{n-1,k-1}\) І перший стовпець, і діагональ складаються з цифр Белла, з\(A_{n,1}=B_{n-1}\) і\(A_{n,n}=B_n\).

\(A_{n,k}\)може інтерпретуватися як кількість розділів,\(\{1,2,\ldots,n+1\}\) у яких\(\{k+1\}\) є одноелементний набір з найбільшим записом у розділі. Наприклад,\(A_{3,2}=3\); розділи\(3+1=4\) в яких\(2+1=3\) є найбільшим числом, що з'являється в однотонному наборі\(\{\{1\},\{2,4\},\{3\}\}\)\(\{\{2\},\{1,4\},\{3\}\}\), і\(\{\{1,2,4\},\{3\}\}\).

Щоб побачити, що це дійсно працює так, як рекламується, нам потрібно підтвердити кілька речей. Спочатку розглянемо\(A_{n,n}\), кількість розділів\(\{1,2,\ldots,n+1\}\) в яких\(\{n+1\}\) є одноелементним набором з найбільшим записом в розділ. Оскільки\(n+1\) є найбільшим елементом множини, то всі перегородки, що містять синглтон,\(\{n+1\}\) задовольняють вимозі, і тому\(B_n\) перегородки\(\{1,2,\ldots,n\}\) разом з\(\{n+1\}\) є саме цікавими перегородками, тобто\(A_{n,n}=B_n\).

Далі ми перевіряємо, що при бажаному тлумаченні це дійсно вірно, що\(A_{n,k}=A_{n,k-1}+A_{n-1,k-1}\) для\(k>1\). Розглянемо розділ, підрахований по\(A_{n,k-1}\). Це містить синглтон\(\{k\}\), а\(k+1\) елемент не в єдиному. Якщо ми обмінюємося\(k\) і\(k+1\), ми отримуємо синглтон\(\{k+1\}\), і не більший елемент знаходиться в одному. Це дає нам розділи, в яких\(\{k+1\}\) є\(\{k\}\) єдиним і ні. Тепер розглянемо розділ\(\{1,2,\ldots,n\}\) порахованих по\(A_{n-1,k-1}\). Замініть всі числа\(j>k\) на\(j+1\), і додайте одинарне значення\(\{k+1\}\). Це створює розділ, в якому обидва\(\{k+1\}\) і\(\{k\}\) з'являються. Насправді, ми описали, як зробити кожен розділ підраховується\(A_{n,k}\) рівно один раз, і так\(A_{n,k}=A_{n,k-1}+A_{n-1,k-1}\).

Нарешті, нам потрібно це перевірити\(A_{n,1}=B_{n-1}\). Ми це знаємо\(A_{1,1}=1=B_0\). Тепер ми стверджуємо, що для того\(n>1\),\[ A_{n,1}=\sum_{k=0}^{n-2}{n-2\choose k}A_{k+1,1}. \nonumber\]

У розділі, підрахованому\(A_{n,1}\), 2 є найбільшим елементом в одиночному,\(\{n+1\}\) тому немає в розділі. Виберіть будь-які\(k\ge 1\) елементи,\(\{3,4,\ldots,n\}\) щоб сформувати набір, що містить\(n+1\). Є\(A_{n-k-1,1}\) перегородки з інших\(n-k\) елементів, в яких 2 є найбільшим елементом в одиночному. Це враховує\({n-2\choose k}A_{n-k-1,1}\)\(\{1,2,\ldots,n+1\}\) розділи або над усіма\(k\):\[ \sum_{k=1}^{n-2}{n-2\choose k}A_{n-k-1,1}= \sum_{k=1}^{n-2}{n-2\choose n-k-2}A_{n-k-1,1}= \sum_{k=0}^{n-3} {n-2\choose k}A_{k+1,1}.\nonumber\]

Нам не вистачає тих розділів, в яких 1 знаходиться в частині, що містить\(n+1\). Ми можемо створити всі такі розділи, починаючи з розділу, підрахованого\(A_{n-1,1}\) і додаючи\(n+1\) до частини, що містить 1. Тепер у нас є\[A_{n,1} = A_{n-1,1}+\sum_{k=0}^{n-3} {n-2\choose k}A_{k+1,1}= \sum_{k=0}^{n-2} {n-2\choose k}A_{k+1,1}.\nonumber\]

Хоча трохи замаскований зміщеною індексацією\(A_{n,1}\), це те саме, що рекуррентне відношення для\(B_n\), і\(A_{n,1}=B_{n-1}\) так за бажанням.

Дописувачі та атрибуція

• Template:ContribGuichard