Алексєєв-Дискретна математика-2 - Стор 2

Один із наслідків бінома Ньютона (властивість 7 з попередньої лекції) говорить, що

Приклад – завдання про заворушення. Нехай = (1, 2, …,) – перестановка елементів. Якщо = для деякого, то елемент називається нерухомою точкою перестановки. Перестановка, яка не має нерухомих точок, називається безладдям . Інакше кажучи, безладно жоден елемент не стоїть на своєму місці. Число заворушень з елементів позначимо через . Легко перевірити, наприклад, що є рівно два безлади з трьох елементів: (2,3,1) та (3,1,2), так що 3 = 2 . Застосуємо метод включення-виключення для підрахунку числа заворушень при довільному .

Позначимо через безліч таких перестановок елементів, які мають нерухомої точкою. Тоді 1 2 … – множина всіх перестановок, що мають нерухомі точки. Тому що всього є! перестановок з елементів, то

Для підрахунку потужності об'єднання множин використовуємо формулу включень-виключень:

, , … , . Кожне таке -перетин

складається з усіх

нерухомі. Число таких

перестановок дорівнює числу перестановок інших елементів,

доданків у цій сумі дорівнює числу -елементних підмножин множини з

елементів, тобто

і отримуємо формулу для числа заворушень:

=! − 1! ! + 2! ! − + (−1) ! ! =! ( 1 − 1! 1 + 2! 1 − + (−1) 1 ! ) .

3.13. Невпорядковані розбиття

Як ще одне застосування методу включень-виключень виведемо формулу для числа невпорядкованих розбиття.

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

нам відомо кількість розміщень і відомо, що їх у ! разів більше, ніж поєднань. Чи не можна використовувати цей прийом для підрахунку числа невпорядкованих розбиття? Ми знаємо, що число впорядкованих розбиття множини з елементів на частин дорівнює . Кожне впорядковане розбиття виходить з невпорядкованого розміщенням його частин у визначеному порядку. Є! способів упорядкувати елементів. Хіба не так?

Ні, не так, і це видно з такого прикладу. Розглянемо розбиття множини з 5 елементів на 4 частини:

Перша і четверта частини однакові і при їх перестановці виходить те саме впорядковане розбиття. Тому перестановкою частин цього розбиття можна отримати не чотири! = 24 , а лише 12 різних упорядкованих розбиття.

Зрозуміло, що в цьому прикладі вся річ у тому, що є дві однакові частини. Зрозуміло також, що однаковими можуть бути лише порожні частини. Якщо знайти число впорядкованих розбиття множини з елементів на непустих частин, то для підрахунку числа невпорядкованих розбиття достатньо буде розділити цей результат на ! .

Завдання. Скільки є впорядкованих розбиття безлічі елементів на непустих частин?

---