назіваються компонентами, чі координатами, кортежу.
Два кортежі назіваються рівнімі в тому и только у тому випадка, коли смороду мают однаково Довжину, а на відповідніх місцях розташовані ті самі елементи. У кортежі координати могут повторюватіся. Например, кортеж может мати такий вигляд: (1, 2, 3, 4, 4, 6). Чи не вилучений І такий випадок, коли всі множини Х1, Х2, ..., Хk збігаються.
4.1 Правило добутку
Візьмемо кілька скінченних множини Х1, Х2, ..., Хk, что складаються з n1, n2, ..., nk елементів, и Знайдемо, скільки кортежів довжина k можна Скласти з елементів ціх множини. Спочатку Знайдемо число кортежів довжина 1, Складення з елементів множини X1. Ясно, что їхнє число дорівнює n1. Візьмемо тепер один Із ціх кортежів (а1) i пріпішемо до елемента а1 праворуч по черзі всі елементи множини Х2. Отрімаємо n2 кортежів довжина 2, у якіх перша координата дорівнює а1. Альо вместо а1 можна Було б узяті будь-який Інший елемент Із Х1. Тому одержуємо n1 раз по n2 кортежу, а Усього n1, n2 кортежів довжина 2. Із кожної подобной парі одержимо n3 трійок, приписавши до неї по черзі всі елементи множини Х3, а Усього n1 n2 n3 трійок.
Продовжуючи цею процес, зрештою одержуємо n1 n2 ... nk кортежів довжина k, Складення Із елементів множини Х1, Х2, ..., Хk.
Даній результат є одним з найважлівішіх у комбінаторному аналізі. На ньом базується вивід багатьох формул цієї ї других наук.
Оскількі для підрахунку числа всілякіх кортежів доводитися перемножаті числа n1 n2 ... nk, то отриманий результат назівається такоже правилом добутку. Сформулюємо це правило так:
Если елемент а1 можна вібрато n1 способами, то после шкірного Вибори цього елемента Наступний за ним а2; можна вібрато n1 n2 способами. Если елемент аk вібірається nk способами, то кортеж (а1, а2, ... аk) можна вібрато n1 n2 ... nk способами.
Підрахуємо, например, число різніх наборів для випадка, коли. У цьом випадка на перше місце в нас k кандидатів, но после того як? 1 вібрать,? 2 можна вібрато такоже k способами ТОЩО. Оскількі число Місць дорівнює n, то одержуємо k? k?...? k - n разів, тобто kn.
4.2 Правило суми
Если елемент, а елемент и при цьом елемент Х1 может буті избран n способами, а елемент Х2 - іншімі m способами, то вибір чі то Х1, чі то Х2 может буті здійсненій n + m способами. Варто мати на увазі, что вибiр Х1, чі то Х2 є тут взаємовіключнімі. Інакше Кажучи, необходимо стежіті, щоб жоден зі способів Вибори про єкта Х1 НЕ збігся з Яким-небудь способом Вибори про єкта Х2. При наявності таких збігів правило суми незастосовне и результат дорівнює m + n - р, де р - число збігів.
4.3 Розміщення
4.3.1 Розміщення з повтореннями
множини Х1, Х2, ..., Xk, що Із елементів якіх складаються кортежі, могут мати Спільні елементи. Зокрема, усі смороду могут збігатіся з тією ж самою множини Еk, что містіть k елементів. Кортежі довжина n, складені з елементів k множини Еkk, назіваються розміщеннямі з повторенням з k елементів по n, а їхнє число (A Із k по n); А - від слова arrangement - размещения. Ризику ставитися, щоб відрізніті їх від розміщень без повторень, про Які мова йтіме далі. З Огляду на приклад направила добутку, відразу одержуємо, что число розміщень с. повтореннями з k елементів по n дорівнює kn. Отже, доведена формула
=kn. (4.1)
4.3.2 Розміщення без повторень
наявний множини Еk, что складається з k елементів. Візначіті, скільки кортежів заданої довжина n можна Скласти з елементів цієї множини, если всі елементи шкірного кортежу повінні буті різнімі. Кортежі, что підпорядковані Цій умові, назіваються розміщеннямі без повторень Із k елементів по n, а їхнє число позначається.
Щоб обчісліті, міркуємо так: на перше місце в нас k кандидатів. После того як воно Заповнено, на другу місце залішається k - 1 кандидатів, на Третє k - 2 і т.д. На п-і місце наявні k - n + 1 кандидатів (после того як ми вібрать n - 1 елемент, залішається k- (n - 1)=k - n +1 елементів). Застосовуючі правило добутків, одержуємо
=k (k - l) ... (k-n + 1). (4.2)
Розміщення без повторень Із k елементів по k складаються з тихий самих елементів, розташованіх у різному порядку.
Такі размещения назіваються перестановками з k-елементів и позначаються Рk.
Тоді за формулою (4.2) візначаємо
(4.3)
Тепер, вікорістовуючі вирази (4.3) та (4.2) можна переписати в такому віді:
