Комбінаторика: відповіді до задач

Відповіді до задач з комбінаторики

Дороговцев А.Я., Сільвестров Д.С., Скороход А.В., Ядренко М.Й.
Теорія мовірностей. Збірник задач.
За загальною редакцією члена-корреспондента АН УРСР Скорохода А.В.
— Київ, Вища школа, 1976, 384 с. Розділ 1, §2.

1. 4 ∙ 2 = 8 — обравши один з 4 можливих способів подорожі від Києва до Чернігова, маємо 2 можливих способи подорожування від Чернігова до Новгород-Сіверська.
3. 17 ∙ 16 ∙ 15 = 4 080.
7. 10 ∙ 9 ∙ 8 ∙ 7 ∙ 6 ∙ 5 = 151 200.
9. (m + 1) ∙ (n + 1).
11. n (n ‒ 3)/2.
13. Якщо не проведено жодної прямої, то число частин дорівнює 1. Для того щоб число частин було максимальним, потрібно, щоб ніякі три прямі не перетинались в одній точці і жодні дві прямі не були паралельними. Проводитимемо прямі поступово з додержанням вказаних вище умов. Після проведення кожної прямої число частин збільшується на 1 плюс число точок перетину, які з'являються. Тому після проведення n прямих число частин збільшиться на n плюс число точок перетину n прямих, яке дорівнюоє n (n ‒ 1)/2. Отже, число частин дорівнює $$1+n+{n(n-1)\over 2}= 1+{n(n+1)\over 2},$$ 14. Нехай A_n — шукане число частин. Використавши відповідь до попередньої задачі, довести: $A_{n+1} = A_n + n(n+1)/2 + 1$, і отримати $A_n = (n^3+5n+6)/6$.
16. Нехай A_n — шукане число частин. Довести, що $A_{n+1} = A_n + n^2 - n + 2$.
17. n₂ (n ‒ 1)₂.
21. a 30. b (k₁ + 1) ∙ (k₂ + 1) ∙ ... ∙ (k_n + 1).
23. Всі таблиці, які мають зазначену в умові задачі властивість, можна скласти так: всюди, крім останнього рядка і останнього стовпця, довільно виписати +1 і ‒1. Це можна зробити 2^{(m ‒ 1)(n ‒ 1)} способами. Нехай p — добуток усіх виписаних чисел. Після цього в кожному з перших m ‒ 1 рядків на перетні n-м стовпчиком писатимемо +1 або ‒1 так, щоб добуток чисел в усьому рядку дорівнював 1. Позначимо добуток чисел, які стоятимуть n-му стовпчику, через x. Тепер в кожному з перших n ‒ 1 стовпчиків на перетині з m-им рядком випишемо +1 або ‒1 так, щоб добуток у стовпчику дорівнював 1. Добуток чисел, які буде виписано в m-ий рядок, позначимо через y. Зауважимо, що x i y мають однаковий знак. Справді, рх = 1, py = 1, тому р²xy = 1, отже, ху > 0. Запишемо на перетині m-го рядка і n-го стовпика 1 з тим знаком, який мають x i y. Тоді добутки чисел і в n-му стовпчику, і в m-му рядку дорівнюватимуть 1.
27. $C^4_n$ — кожній точці перетину двох діагоналей взаємно однозначно відповідає множина 4 вершин n-кутника.
28. Кожний найкоротший шлях з точки (0, 0) до точки (m, n) складається з m + n відрізків, причому серед них є m горизонтальних і n вертикальних відрізків. Різні шляхи відрізняються лише порядком чергування горизонтальних і вертикальних відрізків. Тому загальне число шляхів дорівнює числу способів, якими з m + n відрізків можна вибрати n вертикальних відрізків, тобто $C^n_{m+n}$. Якщо розглядати число способів вибору m горизонтальних відрізків, ми отримали б тоді відповідь $C^m_{m+n}$. Отже, $C^n_{m+n} = C^m_{m+n}$.

29.

Розглянемо найкоротші шляхи з точки (0, 0) до точки (k, n ‒ k). Їх $C^k_n$. Поділимо всі такі шляхи на дві групи: шляхи, які проходять через точку (k ‒ 1, n ‒ k), і шляхи, які проходять через точку (k, n ‒ k ‒ 1). Їх відповідно $C^{k-1}_{n-1}$ і $C^{k}_{n-1}$.
Число найкоротших шляхів з точки О(0, 0) до точки А(n, n) дорівнює $C^n_{2n}$. Кожен такий шлях проходить через одну й лише одну з точок А_k(k, n ‒ k). Число шляхів з точки О до точки А_k, дорівнює $C^k_{k+n-k} = C^k_n$, а з точки А_k до точки А — $C^k_{n-k+k} = C^k_n$. Тому число шляхів з О до А, які проходять через А_k, дорівнює $C^k_n\cdot C^k_n = (C^k_n)^2$. Додавши кількість шляхів, які проходять через кожну з точок А_k (k = 0, 1, ..., n), отримаємо загальну кількість шляхів О до А, тобто $C^n_{2n}$.
Розглянемо всі найкоротші шляхи від точки (0, 0) до точки (n ‒ m + k + 1, m). Розіб'ємо всі такі шляхи на класи L₀, L₁, ..., L_m, віднісши до класу L_r всі ті шляхи, які перетинають пряму х = k + 1/2 у точці (k + 1/2, r). Кожний найкоротший шлях можна розбити на три частини:
- ламану, яка сполучає точки (0, 0) i (k, r);
- горизонтальний відрізок, що сполучає точки (k, r) і (k + 1, r);
- ламану, яка сполучає точки (k + 1, r) і (n ‒ m + k + 1, m)
Загальне число ламаних, з яких складається клас L_r, дорівнює $C^r_{k+r}C^{m-r}_{n-r}$, а загальна кількість всіх шляхів з точки (0,0) до точки (n ‒ m + k + 1, m) дорівнює $C^m_{n+k+1}$.
Розглянемо всі найкоротші ламані, які сполучають точку (0, 0) з точкою (r, n ‒ r). Число всіх таких ламаних дорівнює $C^r_n$. Віднесемо до класу B_k ті ламані, які перетинають пряму х = 1/2 у точці (1/2, k) (k = 0, 1, ..., n ‒ r). Клас B_k складається з $C^{r-1}_{n-k-1}$ ламаних. Тому $$ C^r_n = \sum\limits_{k=0}^{n-r} C^{r-1}_{n-k-1}.$$

30. $C^n_{n+m}-C^d_{n+m}$. Вказівка: розглянути симетрію відносно прямої CD.
31. Які б (m ‒ 1) членів комісії не зібрались, повинен знайтись замок, який вони не можуть відімкнути, але ключ до цього замка є у кожного з (n ‒ m + 1) інших членів комісії (поява будь-якого дає можливість відкрити сейф). Тому мінімальне число замків дорівнює $C^{m-1}_n$, а число ключів дорівнює $(n - m + 1)C^{m-1}_n$.
32. Якщо не проведено жодної діагоналі, то маємо одну частину. Проводитимемо поступово діагоналі. Після проведення кожної діагоналі число частин збільшується на одиницю плюс кількість точок перетину з тими діагоналями, які проведено раніше. Тому число частин, які утворяться після проведення всіх діагоналей, дорівнює 1 плюс число точок перетину, плюс число всіх діагоналей. Якщо жодні три діагоналі не перетинаються в одній точці, то число точок перетину дорівнює $C^4_n$. (див. задачу 27). Число діагоналей дорівнює n(n ‒ 3)/2. Остаточно маємо: $$1+ C^4_n + {n(n-3)\over 2} = {(n-1)(n-2)(n^2-3n+12)\over 24}.$$ 35. 17.
36. 26.
37. При 0 < k < p у дробі $C^k_p ={p!\over k!(p-k)!}$ всі множники знаменника взаємно прості з p. Тому добуток множників чисельника, відмінних від p, кратний знаменнику. Тому $C^k_p$ кратне p.
38. При a = 1 теорема справджується. Припустимо, що a^p ‒ a кратне p. доведемо, що тоді (a + 1)^p ‒ (a + 1) кратне p. Справді, значення виразу: $$ (a + 1)^p - (a + 1) = (a^p - a) + C^1_p a^{p-1} + C^2_p a^{p-2} + \cdots + C^{p-1}_p$$ кратне p, бо перший доданок кратний p згідно з припущенням, а множник $C^k_p$ у наступних доданках при 0 < k < p кратний p згідно з розв'язанням задачі 37.
41. $C^k_n$, 2ⁿ.
42. У точку (k, n ‒ k) прийде $C^k_n$ осіб.
43. $C^3_n-C^3_m$.
44. P₄ = 4! = 24.
45. Парні числа можна розставити на місцях з парними номерами (таких місць n) n! способами. Кожному способу розміщення парних чисел на місцях з парними номерами відповідає n! способів розташування непарних чисел на місцях з непарними номерами. Тому загальне число перестановок вказаного типу дорівнює (n!)².
46. Визначимо спочатку число перестановок, в яких дані два елементи a, b стоять поруч. Можуть бути такі 2 випадки: або a розташовано cпочатку, або b розташовано cпочатку. У кожному з цих випадків є (n ‒ 1)! розташувань n ‒ 1 елемента: упорядкована пара елементів a, b і решта n ‒ 2 елемента множини. Шукана кількість дорівнює n! ‒ 2 (n ‒ 1)! = (n ‒ 1)! (n ‒ 2).
47. При зазначеному розташуванні тур на кожній вертикалі і кожній горизонталі стоїть лише одна тура. Вибрати розташування означає для кожного з 8 вертикалей вказати одну горизонталь, що містить туру. Число шуканих розташувань тур дорівнює 8! = 40 320.
48. $A^4_{25}$ = 25 ∙ 24 ∙ 23 ∙ 22 = 303 600.
49. $A^4_8$ = 8 ∙ 7 ∙ 6 ∙ 5 = 1 680. Якщо відомо, що останній іспит буде складено на восьмий день, то число способів дорівнює 4 ∙ $A^3_7$ = 7 ∙ 6 ∙ 5 ∙ 4 = 840.
56. ${10!\over 2!\cdot 3!\cdot 2!}$ = 151 200.
57. ${n!\over k_1! k_2!\cdots k_m!}$.
63.

Позначимо кулі (вони однакові!) літерою а. Розмістимо по горизонталі n літер а. Поставимо вертикальні риски перед першою буквою і після останньої літери. Далі розставимо N ‒ 1 риску і будемо уявляти урни, як проміжки між рисками. Наприклад, послідовність символів:|аа| |а| |aaa| позначає розташування 6 куль у 5 урнах так, що в першій урні є 2 кулі, в другій немає куль, в третій — 1 куля, в четвертій немає куль, у п'ятій — 3 кулі. Такі послідовності завжди розпочинають й закінчують рискою, а інші N ‒ 1 риску та n літер розподіляють довільно. Розподіл куль в урнах повністю визначено, якщо обрано місце для N ‒ 1 риски з N ‒ 1 + n місця, що можна зробити такою кількістю способів: $C^{N-1}_{N-1+n} = C^n_{N-1+n}$.
Потрібно підрахувати число таких способів розміщення N ‒ 1 риски, при яких кожна риска міститься між двома літерами. Всього є n ‒ 1 проміжок між літерами і будь-які N ‒ 1 них можна обрати як місця для рисок такою кількістю способів: $C^{N-1}_{n-1}$.

64.

Між множиною всіх розв'язків рівняння у невід'ємних числах і множиною всіх можливих розміщень n однакових куль в N урнах існує взаємно однозначна відповідність. Тому кількість розв'язків дорівнює $C^{N-1}_{N-1+n} = C^n_{N-1+n}$.
Розв'язкам рівняння у додатних чслах взаємно однозначно відповідають ті розміщення n куль в N урнах, при яких немає жодної порожньої урни. Тому кількість таких розв'язків дорівнює $C^{N-1}_{n-1}$.

65. $C^{N-1}_{N-1+n} = C^n_{N-1+n}$. Див. розв'язання задачі 64а.
68. З трьох елементів а, b, c можна утворити такі комбінації по два з повтореннями: аа, аb, ас, bb, bс, сс. Кожну комбінацію повністю визначено, якщо вказано, скільки елементів кожного з m типів в неї входить. Поставимо у відповідність кожній комбінації послідовність з нулів та одиниць, утворену за таким правилом: напишемо підряд стільки одиниць, скільки елементів першого типу в комбінації, далі поставимо нуль і після нього напишемо стільки одиниць, скільки елементів другого типу містить ця комбінація, і т. д. Наприклад, написаним вище комбінаціям з трьох по два будуть відповідати такі послідовності: 1100, 1010, 1001, 0110, 0101, 0011. Таким чином, кожній комбінації з m по n взаємно однозначно відповідає послідовність з n одиниць та m ‒ 1 нулів. Кожну таку послідовність можна однозначно задати вибором n місць для одиниць з n + m ‒ 1 місця. Тому число різних комбінацій з m елементів по n з повтореннями дорівнює: $C^n_{n+m-1}=C^{m-1}_{n+m-1}$.
69. $C^6_{16}=C^{10}_{16}$.
70. $C^r_{r+2}=C^2_{r+2}$.
74. n^k — кількість способів заповнення таблиці значень функції.
75. с. Достатньо довести, що кожен елемент A₁ ∪ A₂ ∪ ... ∪ A_n враховано у правій частині рівності лише один раз. Розглянемо довільний елемент a з A₁ ∪ A₂ ∪ ... ∪ A_n. Припустимо, що a входить рівно в m множин з цього об'єднання, де m ∈ { 1, 2, ..., n}. У цьому випадку a враховано у правій частині рівності таку кількість разів; $$C^1_m-C^2_m+C^3_m-C^4_m+\cdots +(-1)^{m-1}C^m_m = 1- (1-1)^m = 1.$$ 80. Позначимо через A_k множину тих перестановок, в яких на k-му місці стоїть k. Множина $ A_{i_ 1}\cap A_{i_2}\cap\cdots\cap A_{i_k}$ містить ті перестановки, в яких на місцях i₁, i₂, ..., i_k стоять відповідно числа i₁, i₂, ..., i_k, а на інших місцях — інші n ‒ k чисел впорядковано довільно. Маємо: $$ |A_{i_ 1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| = (n-k)!,\\ \sum\limits_{1\leq i_1\lt i_2\lt\cdots\lt i_k\leq n} |A_{i_ 1}\cap A_{i_2}\cap\cdots\cap A_{i_k}| = C^k_n\cdot (n-k)! = {n!\over k!}.$$ З рівності c задачі 75 випливає, що $$|A_1\cup A_2\cup\cdots\cup A_n| = n!\left( {1\over 1!} - {1\over 2!} + {1\over 3!} - {1\over 4!} + \cdots + {(-1)^{n-1}\over n!}\right).$$ 85. Нехай A_k — множина тих перестановок, в яких на k-му місці стоїть k. Тоді, згідно з розв'язанням задачі 84, маємо:$$ N_{[m]} (A_1\cup A_2\cup\cdots\cup A_n)\\ = C^m_m C^m_n (n-m)! - C^m_{m+1} C^{m+1}_n (n-m-1)! +\cdots + (-1)^{n-m} C^m_n C^n_n.$$ Після подання біномних коефіцієнтів через факторіали і взаємного знищення перших двох доданків отримаємо: $${n!\over m!}\left({1\over 2!} - {1\over 3!} + \cdots + {(-1)^{n-m}\over (n-m)!}\right).$$ 86. Див. розв'язання задачі 87.
87 До кожної перестановки елементів множини A_r допишемо кожну з перестановок елементів множини A \ A_r. Тоді матимемо i_r! (n ‒ i_r)! перестановок елементів множини A. Те саме зробимо для всіх множин A₁, A₂, ..., A_k. Отримаємо таку кількість перестановок елементів множини А: $$\sum\limits_{r=1}^k i_r! (n-i_r)!.$$ Згідно з умовою задачі всі ці перестановки різні. Тому $$\sum\limits_{r=1}^k i_r! (n-i_r)! \leq n!.$$ Поділивши обидві частини нерівності на n!, отримаємо: $$\sum\limits_{r=1}^k {1\over C^{i_r}_n} \leq 1.$$ З доведеного випливає й твердження попередньої задачі (теорема Шпeрнeра). Справді, $C^{i_r}_n \leq C^{[n/2]}_n$, тому $${k\over C^{[n/2]}_n}\leq\sum\limits_{r=1}^k {1\over C^{i_r}_n} \leq 1,$$ звідки $k\leq C^{[n/2]}_n$.
88. Твердження задачі випливає з тореми Шпернера (див. задачу 86). Поставимо у відповідність кожній сумі вигляду $$\sum\limits_{k=1}^r \varepsilon_k x_k$$ підмножину S множини А = {1, 2, ..., n} таку, що k ∈ Ѕ тоді й лише тоді, коли $\varepsilon_k = 1$. Залишається тепер лише взяти до уваги таку обставину: якщо дві різні (за значеннями $\varepsilon_k$) суми лежать в інтервалі довжини 2, то жодна з відповідних множин не є частиною іншої.