Комбінаторика: перестановки, комбінації, теорема Рамсея

1. Правила суми та добутку

Два фундаментальних принципи, з яких будується вся комбінаторика.

Правило суми: Якщо A і B — несумісні події (|A∩B|=∅), то кількість способів = |A| + |B| Правило добутку: Якщо вибір складається з k незалежних кроків, на i-му кроці є nᵢ варіантів, то: всього способів = n₁ · n₂ · … · nₖ

Приклад
Скільки різних паролів довжиною 4 з літер (26) і цифр (10)?
26⁴ (лише літери) + 10⁴ (лише цифри) = 456 976 + 10 000 = 466 976

2. Перестановки і розміщення

Перестановки n елементів: P(n) = n! (порядок важливий, всі елементи) Розміщення: вибрати k із n (порядок важливий): A(n,k) = P(n,k) = n!/(n-k)! = n·(n-1)·…·(n-k+1) Приклади: P(5) = 5! = 120 (розклад 5 книг на полиці) A(10,3) = 10·9·8 = 720 (3 призи для 10 учасників)

3. Комбінації

C(n,k) = n! / (k! · (n-k)!) = A(n,k) / k! (порядок НЕ важливий) Властивості: C(n,k) = C(n, n-k) (симетрія) C(n,k) = C(n-1,k-1)+C(n-1,k) (трикутник Паскаля) ∑ₖ C(n,k) = 2ⁿ (сума рядка = 2ⁿ) Приклад: лото 6/49 C(49,6) = 49!/(6!·43!) = 13 983 816

4. Бінома Ньютона

(x + y)ⁿ = ∑ₖ₌₀ⁿ C(n,k) · xⁿ⁻ᵏ · yᵏ Часткові випадки: (1+x)ⁿ = C(n,0)+C(n,1)x+…+C(n,n)xⁿ (x+y)³ = x³ + 3x²y + 3xy² + y³ Мультиноміальна теорема: (x₁+…+xₘ)ⁿ = ∑ C(n; k₁,…,kₘ) · x₁ᵏ¹·…·xₘᵏᵐ де C(n; k₁,…,kₘ) = n!/(k₁!·k₂!·…·kₘ!) (k₁+…+kₘ=n)

5. Принцип Дирихле (принцип скриньок)

«Якщо n+1 предмет розкласти по n скриньках, то хоча б одна скринька містить не менше двох предметів.»

Сильна форма: n предметів у m скриньок ⟹ хоча б в одній скриньці ≥ ⌈n/m⌉ предметів Класичний приклад: У групі 13 осіб знайдуться двоє, що народились в один місяць (13 людей, 12 місяців ⟹ ⌈13/12⌉=2)

Задача
Доведіть: серед будь-яких 5 чисел від 1 до 8 є два, що дають суму 9.
Пари: {1,8},{2,7},{3,6},{4,5} — 4 пари, 5 чисел → Дирихле!

6. Принцип включень-виключень

|A ∪ B| = |A| + |B| - |A ∩ B| |A ∪ B ∪ C| = |A|+|B|+|C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| Загальна форма: |A₁∪…∪Aₙ| = ∑|Aᵢ| - ∑|Aᵢ∩Aⱼ| + ∑|Aᵢ∩Aⱼ∩Aₖ| - … Кількість безладів (derangements) D(n): D(n) = n! · ∑ₖ₌₀ⁿ (-1)ᵏ/k! ≈ n!/e D(1)=0, D(2)=1, D(3)=2, D(4)=9, D(5)=44

7. Числа Каталана

Cₙ = C(2n,n) / (n+1) = C(2n,n) - C(2n, n+1) C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, … Рекурентність: Cₙ = ∑ᵢ₌₀ⁿ⁻¹ Cᵢ · Cₙ₋₁₋ᵢ Твірна функція: C(x) = (1 - √(1-4x)) / (2x) Застосування (однакова кількість): • Правильних дужок довжини 2n • Тріангуляцій (n+2)-кутника • Шляхів в сітці, що не перетинають діагональ • Бінарних дерев з n+1 листком

8. Числа Стірлінга

Числа Стірлінга 2-го роду: S(n,k) = кількість розбиттів n-елементної множини на k непорожніх підмножин Рекурентність: S(n,k) = k·S(n-1,k) + S(n-1,k-1) S(3,1)=1, S(3,2)=3, S(3,3)=1 S(4,2)=7, S(4,3)=6 xⁿ = ∑ₖ S(n,k) · x(x-1)…(x-k+1) (розклад через спадні факторіали) Числа Стірлінга 1-го роду: c(n,k) — перестановки n-елементів з рівно k циклами.

9. Теорема Рамсея

В будь-якому досить великому графі є впорядкована структура — клік або незалежна множина заданого розміру.

Теорема Рамсея: R(s,t) — мінімальне N таке, що будь-яке 2-фарбування K_N містить або K_s червоним, або K_t синім. R(3,3)=6: серед 6 осіб є або 3 спільних знайомих, або 3 попарно незнайомих. Доведення R(3,3)≤6: Один з 6 вершин з'єднаний ≥3 ребрами одного кольору (Дирихле: 5 ребер, 2 кольори → ≥3). Якщо 3 сусіди — жодне ребро між ними червоне → синій K₃. Інакше — червоний трикутник. Відомі значення: R(3,3)=6, R(3,4)=9, R(3,5)=14, R(4,4)=18, R(4,5)∈[25,35]

10. Твірні функції

Звичайна твірна функція (ЗТФ): F(x) = ∑ₙ₌₀∞ aₙ xⁿ (aₙ — шукана послідовність) Числа Фібоначчі: F(x) = x/(1-x-x²) Коефіцієнти = 0,1,1,2,3,5,8,13,21,… Показникова твірна функція (ПТФ): F(x) = ∑ₙ aₙ xⁿ/n! — для пересортованих структур Застосування: розбиття числа n на доданки ∑₁∞ pₙ xⁿ = ∏ₖ₌₁∞ 1/(1-xᵏ) p(5) = 7: 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1

Про цю статтю

Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.

Теорія ймовірностей кількісно описує невизначеність. Вона є основою статистики, машинного навчання, фінансів та криптографії.

Навіщо читати цю статтю

Після прочитання ви зможете впевнено пояснити тему, вирішувати практичні задачі та застосовувати знання у навчанні й роботі. Стаття охоплює теоретичне підґрунтя і числові приклади, що полегшують запам'ятовування матеріалу.

Часті запитання (FAQ)

Що таке Комбінаторика: мистецтво лічити способи і чому це важливо знати?

Комбінаторика: мистецтво лічити способи — ключова тема в математики та статистики. Розуміння її основ дає змогу вирішувати практичні задачі, успішно складати іспити та застосовувати знання в реальних ситуаціях. Стаття розкриває концепцію доступними словами з конкретними прикладами.

Які ключові формули та методи використовуються в комбінаторика: мистецтво лічити способи?

Основні формули та методи для комбінаторика: мистецтво лічити способи охоплюють як аналітичні підходи, так і числові алгоритми. У статті наведені всі ключові вирази з поясненням кожного позначення та вказівкою одиниць вимірювання.

Де в реальному житті застосовується комбінаторика: мистецтво лічити способи?

Сфери застосування комбінаторика: мистецтво лічити способи надзвичайно широкі: страхуванні та ризик-менеджменті, фінансах, телекомунікаціях, Machine Learning. Знання цієї теми відкриває кар'єрні можливості в інженерії, науці, фінансах та IT-галузі.

Як розрахувати комбінаторика: мистецтво лічити способи онлайн?

На calculator.party є безкоштовні онлайн-калькулятори з тематики 'Комбінаторика: мистецтво лічити способи'. Достатньо ввести вхідні дані — і ви миттєво отримаєте точний результат з покроковим поясненням. Це ідеально для перевірки ручних розрахунків.

Яка різниця між комбінаторика: мистецтво лічити способи та суміжними темами?

Стаття чітко описує межі тематики 'Комбінаторика: мистецтво лічити способи', порівнюючи її з близькими поняттями. Чітке розуміння відмінностей допомагає уникнути типових помилок та плутанини при розв'язанні задач.