Головна

Теорема 1. Для всіх n, kIN

  1. Б) (II теорема еренфеста).
  2. Бокс 3.4. Теорема Модільяні-Міллера
  3. Булеві функції. Повнота і замкнутість. Теорема Поста про повноту.
  4. Вектор електричного зміщення. Теорема Остроградського-Гаусса для електричного поля в діелектрику.
  5. Зовнішні ефекти і теорема Коуза
  6. Зовнішні ефекти і теорема Коуза.
  7. Зовнішні ефекти. теорема Коуза

 . (1)

Доведення. нехай U= {  } є n+1 Елементне безліч. Розглянемо всі розбиття множини U на k блоків.

Число всіх тих розбиття безлічі U на k блоків у яких є блок

{  } дорівнює .

Підрахуємо число всіх тих розбиття безлічі U на k блоків в яких елемент  лежить в деякому блоці потужності> 1. Кожне таке розбиття можна отримати з розбиття множини {  } на k блоків додаючи елемент  в один з k блоків. Тому число всіх розбиття безлічі U на k блоків в яких елемент  лежить в деякому блоці потужності> 1 одно .

З вище доведеного слід (1). n

Рівність (1) дає зручний рекурентний спосіб обчислення чисел Стірлінга другого роду, аналогічний трикутнику Паскаля.

Таблиця чисел Стірлінга другого роду.

n = 1n = 2n = 3n = 4n = 5n = 6n = 7 r = 1 r = 2 r = 3 r = 4 r = 6 r = 7 r = 8
               

визначення. якщо  - Розбиття множини U, То кортеж (  називається впорядкованим розбивкою безлічі U на k блоків.

Число упорядкованих розбиття n елементного безлічі на k блоків одно .

Теорема 2. нехай A, B- Кінцеві безлічі, |A| = n, |B| = k. Тоді число всіх сюр'єкція f :A®B одно .

Доведення. Позначимо елементи безлічі B = {  }. сюр'єкція f :A®B задамо табличним способом

,

де кортеж  є впорядкованим розбивкою безлічі A на k блоків, це означає потрібне твердження. n

Властивості чисел Стірлінга другого роду.

1. Для всіх kIN , nIN справедливо рівність

 . (2)

Доведення. нехай k, nIN. Обчислимо двома способами P- Число всіх функцій f: {1, ...,n} ® {1, ...,k}.

За слідству 2 п.3, P = .

кожна функція f: {1, ...,n} ® {1, ...,k} Розбиває множину {1, ...,n} на r блоків  на яких функція f постійна, 1 ? r ? k. Тому функція f визначає ін'єкцію 'f : {  } ® {1, ...,k}, Де 'f (  ) = f(b) Для будь-якого bI  . Вірно і зворотна, кожна ін'єкція ' f : {  } ® {1, ...,k} Визначає функцію f: {1, ...,n} ® {1, ...,k}, Де f(b) = 'f(  ) для bI  . Тому

.

З вище доведеного випливає рівність (1). n

2. Для всіх nIN справедливо рівність многочленів

 . n

3. Для всіх n, kIN

 . (3)

Доведення. нехай n фіксоване. З властивості 1 випливає, що

, kIN .

Перепишемо це рівність у вигляді

, kIN .

Застосовуючи до останнього рівності биномиальное звернення з п. 8 отримаємо рівності (3). n

Число розбиття даного типу.

Визначення. Нехай p - розбиття n елементного безлічі U. Якщо p містить  блок потужності 1,  блоків потужності 2, ...,  блоків потужності n, То кортеж ( ,  , ...,  ) IN називається типом розбиття p.

якщо ( ,  , ...,  ) - Тип деякого розбиття n елементного безлічі, то .

Приклад 1.Тип розбиття p = 3 | 1,2 дорівнює (1,2,0). n

Позначення. позначимо  число всіх розбиття n елементного безлічі мають тип ( ,  , ...,  ).

теорема 3. Для всіх nIN, ( ,  , ...,  ) IN  таких, що

 , Справедливо рівність

 . (4)

 Доведення. Доведемо рівність (4) індукцією по числу n.

якщо n = 1, то рівність (4) очевидно виконано.

Припустимо, що рівність (4) доведено для числа n - 1 і доведемо його для числа n.

нехай U = {  } - n- Елементний безліч, ( ,  , ...,  ) IN ,  . маємо  або .

Доведемо рівність (4) для  . В цьому випадку  дорівнює числу розбиття безлічі U не мають блоку потужності n. Кожне таке розбиття можна отримати з розбиття безлічі  наступними способами.

1-й спосіб. До кожного розбиття безлічі V типу  додамо блок {  }. Легко бачити, з огляду на індукційне припущення, що число таких розбиття одно

.

2-й спосіб. У кожному розбитті безлічі V типу  додамо елемент  в один з блоків потужності 1. Легко бачити, з огляду на індукційне припущення, що число таких розбиття одно

.

І т.д.

(n-1) -й Спосіб. У кожному розбитті безлічі V типу  додамо елемент  в один з блоків потужності n - 2. Легко бачити, з огляду на індукційне припущення, що число таких розбиття одно

.

З вище доведеного слід

= =

= =

= =

= ,

що збігається з рівністю (4) при  = 0.

якщо  = 1, то  і рівність (4) очевидно виконано. n

 



П.10. Числа Стірлінга другого роду. | п.11. Числа Белла.

П.3. Правило твори. | Визначення. Кортеж (a, ..., a) I A називається k- вибіркою з безлічі A. Іноді k- вибірки називають розміщеннями з повтореннями. n | П.4. r- перестановки, перестановки. | П.5. r -елементние підмножини (r - поєднання). | Приклад 1. Кожен кортеж N, де, кодується k-елементним підмножиною множини. Тому, при фіксованому k, число всіх кортежів N, де, так само. n | П.6. Перестановки з повтореннями. | П.7. Мультимножини (поєднання з повтореннями). | Теорема 1. Для всіх k, n IN | П.8. Поліноміальна теорема. | П.9. Числа Стірлінга першого роду. |

© um.co.ua - учбові матеріали та реферати