align="justify">=(4.4)
добуток увазі k (k - 1) ... 1 часто зустрічається як у комбінаторіці, так и в алгебрі, того для него уведена окрема назва k-ФАКТОРІАЛ, что позначається k !. (чітається k-ФАКТОРІАЛ).
4.4 Перестановки
Перестановки з повтореннями.
Розглянемо перестановки з повтореннями з k елементів, Специфікація якіх n=k1 + k2 + ... + kn, причому n=k. Через збіг Деяк елементів число таких перестановок віявляється меншим, чем k !, того что перестановка Однаково елементів Нічого НЕ змінює. Елементи j-го класу допускаються перестановку kj! способами, и в шкірному класі Такі операции здійснюються Незалежності. Тому відповідно до правила добутку можна здійсніті k1! k2! ... kn! перестановок, что НЕ змінюють Дану перестановку. Альо k чисел можна переставляті Одне з одним k! способами. Тому число розміщень з повторенням елементів, что мают склад (k1! K2! ... Kn!), У k1! k2! ... kn! менше, чем k!:
(4.5)
Если запас об'єктів k різніх тіпів НЕ ограниченной, шкірну місце в можна заповнити k різнімі способами. Тому, відповідно до правила добутку, число перестановок з НЕОБМЕЖЕНИЙ повторень дорівнює kn. Це співвідношення візначає Кількість різніх n-розрядно чисел, записаних у позіційній сістемі числення з основою системи числення k.
4.5 зотриманням (зелених сандалів)
Візначімо, скільки різніх складів могут мати кортежі довжина n iз k елементів.
За-ІНШОМУ Цю ж задачу можна сформулюваті так: назвемо дві кортежі еквівалентнімі, если смороду мают однаково склад. Звідсі формулювання: на скільки класів еквівалентності розбівається при цьом вся сукупність кортежів довжина n Із k елементів? Такі класи еквівалентності назіваються зотриманням з повторенням з k елементів по n, а їхнє число позначається.
Будь-який склад кортежу довжина n Із k елементів має вигляд, де - невід ємні цілі числа, сума якіх дорівнює n. Заміняючі Кожне з чисел. відповіднім числом одиниць и розділяючі нулями одиниці, что відповідають різнім числам, одержуємо кортеж з k - 1 нулів и n одиниць. При цьом шкірному складу відповідає одна и только одна Запис помощью нулів и одиниць, а КОЖЕН такий Запис задає одне и только один склад. Тому число різніх складів, что могут мати кортежі довжина n iз k елементів, дорівнює числу перестановок з повтореннями з k - 1 нулів и n одиниць, тобто.=Р (k - 1, n). Тоді
(4.6)
Покажемо, чому дорівнює Потужність n-підмножін у k-множінi Еk Такі підмножіні назіваються зотриманням з k елементів по n и позначаються.
Завдання про обчислення зводу до задачі про число розміщень без повторень з k елементів по n, что буде в n! (число розміщень Із k по n) разів менше, тобто
(4.7)
Справді, розставімо будь-як задані k елементів и зашіфруємо будь-який вибір, n елементів кортежем довжина k iз n одиниць по k - n нулів - если елемент вібірають, тo на его місце пишуть 1, а если ні, - тo 0.
например, вибір елементів а, c iз елементів a, b, c, d, e запісується кортежем 10100. Кожному кортежу відповідає свой способ вібоpу елементів. Тому число n-підмножін у k-множінi дорівнює числу перестановок iз повторень Із k -n п нулів in одиниць, тобто дорівнює P (kn, n) Із (4.7).
виходим
(4.8)
Наслідок. Рівності (4.6) і (4.7) показують, что
== (4.8)
Розглянуті способи доведення формул и базуються на заміні однієї множини іншою, елементи якіх є у взаємнооднозначній відповідності І, отже, їхнє число в ціх множини однакове.
Властивості зотриманням.
Оскількі числа показують, скільки n-підмножін містіться в даній k-множінi, то между ними існує цілий ряд залежних, что відбівають Різні залежності между підмножінамі.
ЦІ залежності можна доводіті різнімі способами. У Деяк випадка найзручніше прямо скористати формулою (4.7) для числа зотриманням. Проти більш красивим и змістовнішім є Інший способ, Заснований на комбінаторніх засідках. Спочатку підраховуємо число підмножін Деяк увазі и розбіваємо сукупність усіх таких підмножін на класи так, щоб Жодна підмножіна НЕ попала в два різніх класи. После цього знаходімо, скільки підмножін входити У кожен клас. Складаючі отрімані числа, знову одержуємо Кількість підмножіні обраності увазі. Це и дает шукане співвідношення.
Властівість 1. Найбільш пробачимо є співвідношення
=(4.9)
Пож...
