1. 1) mn. 2) \(C^2_n\), \(C^2_m\). 3) \(C^3_n\), \(C^3_m\), m\(C^2_n\). 4) \(C^4_n\), m\(C^3_n\), \(C^2_n C^2_m\).
2. 1) \(C^3_{n+m+k} - C^3_n - C^3_m - C^3_k\). 2) \(C^4_{n+m+k} - C^4_n - C^4_m - C^4_k - (m+k) C^3_n - (n+k) C^3_m - (n+m) C^3_k\).
3. 1) \(C^3_{n+m+k} - C^3_n - C^3_m - C^3_k\). 2) \(C^3_{n+m+k} - mkC^2_n - nkC^2_m - nmC^2_k\).
4. 1) \(C^3_{n+m} - C^3_m\). 2) \(C^4_{n+m} - C^4_m - n C^3_m\).
5. 1) \(C^3_{4(n-1)} - 4C^3_{n-1}\). 2) \(C^4_{4(n-1)} - 4C^4_{n-1} - 12(n-1) C^3_{n-1}\).
6. \(2^n - 1 - n - C^2_n\).
7. \(3n(n+1)/2\). Порахувати окремо прямокутники, всі вершини яких лежать на двох паралельних сторонах 6-кутника, і тих, вершини яких лежать на чотирьох різних сторонах 6-кутника.
8. 1) \(C^2_n\). 2) 1 + \( n(n+1)/2\). При проведенні n-ої прямої кількість точок перетину зростає на частин зростає на \(n-1\), а кількість частин площини зростає на n. 3) 2n і 1 + \(n(n-3)/2\). Необмежені частини відокремлені одна від одної променями, що лежать на n прямих. 4) \(C^3_n\).
9. 1) \(C^2_n\). 2) \(C^4_n\). 3) \((n+1)(n^2-n+6)/6\). 4) \(n^2-n+2\) i \((n-1)(n-2)(n-3)/6\).
10. \(n^2-n+2\).
11. \(C^1_n + 2C^2_n + C^3_n = n(n+1)(n+2)/6\).
12. Нехай \(n = p_1^{k_1}\cdot p_2^{k_2} \cdots\ p_s^{k_s}\) — канонічний розклад на прості дільники. Якщо n — непарне, то кількість різних многокутників дорівнює \((k_1+1)(k_2+1)\cdots (k_s+1) - 1\), інакше (при парному n) вона дорівнює \((k_1+1)(k_2+1)\cdots (k_s+1) - 2\).
13. 1) 7 (див. попередню задачу). 2) 67. Полічити кількість многокутників кожного типу окремо.
14. \(C^3_n\) різностронніх, \(n(n-1)\) рівнобедрених, але не рівосторонніх, і n рівносторонніх.
15. 1) Для кожної четвірки вершин n-кутника існують рівно 2 діагоналі, що перетинаються всередині многокутника. Тому точок перетину діагоналей стільки, скільки є різних четвірок вершин, тобто \(C^4_n\).
2) \(C^3_n\) — кількість трикутників, вершини яких є вершинами заданого многокутника. Серед цих вершин є n таких, у яких дві сторони збігаються зі сторонами многокутника, і \(n(n-4)\) таких, у яких лише одна сторона збігається зі стороною многокутника.Тому шукана кількість дорівнює \(C^3_n - n - n(n-4) = n(n-4)(n-5)/6\).
3) Припустимо, що у многокутнку проведено кілька діагоналей, які поділили його на певне число частин. Встановимо, як зміниться це число, якщо провести ще одну діагональ. Якщо ця нова діагональ перетне раніше проведені діагоналі у k точках, то ці точки поділять її на k + 1 відрізків. Кожний з цих відрізків розітне суцільну доти частину многокутника на дві. Тому загальна кількість частин многокутника зросте на k + 1. З цих міркувань випливає, що коли всі діагоналі провести послідовно одна за одною, то кількість частин, на які вони поділяють многокутник, зросте на кількість точок перетину діагоналей всередині многокутника плюс число самих діагоналей. Додамо, що спочатку многокутник був однією областю. Отже, діагоналі поділяюнать його на таку кількість частин: \(1+C^4_n+n(n-3)/2\).
16. На кожній з 3 позицій може стояти одна з 5 цифр: 1, 3, 5, 7, 9. Тому шукана кількість дорівнює \(5\cdot 5 \cdot 5 = 125\). У кожному розряді кожна з 5 цифр з'являтметься таку кількість разів: \(5^2=25\), тому сума усіх чисел (додавати порозрядно) дорівнює \((1+3+5+7+9)\cdot 25 \cdot (1 + 10 + 100)\) = 69 375.
17. \(4\cdot 5 \cdot 5 = 100\). \((2+4+6+8)\cdot (20 \cdot (1 + 10) + 25 \cdot 100)\) = 544 00.
18. \(9\cdot 10^4-9^5\) = 30 951.
19. \(9^5\) = 59 049. На першому місці може стояти одна з 9 цифр, відмінних від 0, на всіх наступних — одна з 9 цифр, відмінних від попередньої.
20. \(C^3_6\cdot 5^6 - C^2_5\cdot 5^5\).
21. \(9\cdot 10\cdot 10\cdot 10\cdot 10\cdot 5\) = 450 000.
22. \(9\cdot 9\cdot 9\cdot 9\cdot 9\cdot 1 = 9^5\) = 59 049.
23. \(6\cdot 6\cdot 6\cdot 6\cdot 2\) = 2 592.
24. \(5\cdot 5\cdot 5\cdot 1 = 125\). Якщо написано дфовільні перші три цифри, то остання визначається онозначно за ознакою подільності на 4.
25. \((1+2+3+4)\cdot 16 \cdot (1+10+100)\) = 17 760, див. задачу 16.
26. 1) \(7\cdot 7\cdot 2 = 98\). Перші дві цифри довільні, останні дві — або 25, або 75. 2) \(A^2_{7-2}\cdot 2=40\).
27. \(C^5_{10}\). Будь-якими п'ятьма різними цифрами можна записати єдине потрібне число.
28. \(C^5_{9}\). Будь-якими п'ятьма різними цифрами, відмінними від 0, можна записати єдине потрібне число.
29. \(9\cdot 10^4 - 9\cdot 9\cdot 8\cdot 7\cdot 6\) = 62 784.
30. \(9\cdot 10^4 - 8\cdot 9^4\) = 37 512.
31. \((9000-(9+14C^2_9+7\cdot 9)\) = 8 424, де 9 — кількість 4-цифрових чисел, записаних лише однією цифрою, \((2^4 - C^0_4 - C^4_4)\cdot C^2_9\) — кількість 4-цифрових чисел, записаних двома цифрами, серед яких немає нуля, \((2^3 - C^0_3)\cdot 9\) — кількість 4-цифрових чисел, ю записаних двома цифрами, серед яких є нуль.
32. Різниця прогресїї d не може перевищувати \(n-1\)/. Перший член прогресії з різницею d не може перевищувати \(2n-2d\), тому різних 3-членних прогресій з цією різницею дорівнює сумі всіх чисел вигляду \(2n-2d\) для d = 1, 2, ... , \(n-1\), тобто
$$ (2n-2)+(2n-4)+\cdots +4+2=2((n-1)+(n-2)+\cdots +2+1) = n(n-1).$$
33. 55.
34. 5!=120. Посадивши одну особу на довільне місце, зводимо задачу до пошуку кількості перестановок 5 елементів.
35. 8! — для кожного з 8 рядків потрібно вибрати рядок з тих, що залишлися вільними від тур.
36. 64 ∙ 49 = 3 136.
37. 2 ∙ (n ‒ 1)! — вважаючи кожну пару (a, b) чи (b, a) одним елементом, маємо (n ‒ 1)! перестановок для кожної пари.
38. 2 ∙ (n ‒ k ‒ 1) ∙ (n ‒ 2)!, де 2 — кількість перестановок двох елементів, (n ‒ k ‒ 1) — кількість можливих розташувань першого з елементів, (n ‒ 2)! — кількість перестановок невиділених елементів на вільних n ‒ 2 місцях.
39. 1) \(C^3_{p+q}-C^3_p-C^3_p\). 2) p! ∙ q! 3) \(p!\cdot q!\cdot C^q_{p+1}\) — потрібно спочатку вишикувати хловців у колону одним з p! способів, потім вибрати q місць для дівчат з p ‒ 1 місця між хлопцями та ще двох з країв колони, і нарешті розставити q дівчат на q місць. При \(q > p+1\) розв'язків немає. 4) (p + 1)! ∙ q!
40. 1) \(C^p_{p+q}\). 2) \(C^p_{q+1}\). При \(p > q+1\) розв'язків немає.
41. \(2^{n-1}\). Довільне натуральне число n можна подати сумою n одиниць. У записі суми буде n ‒ 1 знак додавання. Виберемо довільну підмножину цих знаків і виконаємо додавання за іншими знаками. Отримали взаємно однозначну відповідність між поданням сумою і підмножинами (n ‒ 1)-елементної множини знаків додавання.
42. \(C^{k-1}_{n-1}\). Див. розв'язання попередньої задачі.
43. Тотожність має таке тлумачення: кількість підмножин з непарною кількістю елементів n-елементної множини дорівнює кількості підмножин з парною кількістю елементів цієї самої множини. При непарному n існує взаємно однозначна відповідність між такими підмножинами: кожна непарно-елементна підмножина має свого парно-елементного двійника, що її доповнює до всієї множини. Припустимо, що n парне. Позначимо через a один з елементів n-елементної множини A. Серед підмножин, що не містять a, парно- і непарно-елементних однакова кількість, бо вони є підмножинами (n ‒ 1)-елементної множини A\{a}. Додавши до кожної з цих підмножин елемент a, отримаємо всі підмножини, що містятть a. З попередніх міркувань випливає, що і серед цих множин кількості парно- і непарно-елементних множин збігаються. Тому ці кількості збігаються для всіх підмножин множини A.
44. \(C^n_{n+m}\). Найкоротші маршрути містять m + n ланок довжини 1, з яких m потрібно проти у напрямку зростання абсциси, n — у напрямку зростання ординати. Вибрати найкоротший маршрут означає вибрати m ланок з m + n, які потрібно пройти у горизонтальному напрямку.
45. Нехай A, B — довільні дві множини без спільних елементів, що мають по n елементів. Ліва частина рівнності — це кількість різних множин (у тому числі порожньої), що містить однакову кількість елементів кожної з множин A, B. Ці множини можна утворити таким чином: з об'єднання множини A і B, що має 2n елементів, вибрати n елементів і до створюваної множини включити вибрані елементи множини A і невибрані елементи множини B. Кількість таких множин дорівнює правій частині рівності.