Поліномна формула

Визначимо коефіцієнти функції

(x₁ + ... + x_k)ⁿ = ,

яку назвемо поліномною, де підсумовування проводиться за всіма розв’язками рівняння n₁ + ... + n_k = n у цілих невід’ємних числах.

Справедлива рівність = = .

Позначимо через = (x₁ + ... + x_k) , i = 1, 2, ..., k. Тоді (x₁ + ... + x_k)ⁿ = . Підрахуємо всі одночлени після перемноження , в яких x₁ зустрічається n₁ разів, x₂ – n₂ разів, ..., x_k – n_k разів, тобто одночлени вигляду

, де n₁ + ... + n_k = n. (3)

Розглянемо будь-який з таких одночленів. Для кожного i = {1, 2, ..., k} позначимо через A_i таку підмножину множини A( ), що в цей многочлен увійдуть змінні x з тих і тільки тих співмножників, які перераховані в A_i. Цим самим одночлену поставлено у відповідність розбиття множини А на підмножини A₁, ..., A_k так, що

|A_i| = n_i, i = 1, ..., k, = A, A_i A_j =  при i  j. (4)

Зазначена відповідність між одночленами (3) і розбиттям (4) є взаємно однозначною. Тоді

.

Приклад. Визначимо коефіцієнт с в одночлені c₁ многочлена (зі зведеними подібними членами), що утворюється з виразу (x₁ + x₂ + x₃)¹⁰

C = = = 4200.

Задачі до теми „Комбінаторика”

Приклад 1. Із міста M в місто N ведуть 7 доріг, а із міста N в місто P – 5 доріг. Скільки шляхів, що проходять через N, ведуть із M в P?

Розв’язування. Будь-який шлях, що веде із M в P можна розглядати як впорядковану пару (a_i, b_j), де a_i  A – множини доріг із M в N, b_j  B – множини доріг із N в P. За правилом добутку число всіх шляхів N = 7  5 = 35.

Зауважимо, що в даній задачі множини A, B не мають спільних елементів і вибір b_j на ,другому кроці не залежить від вибору a_i.

Приклад 2. Скільки чотиризначних чисел можна скласти із усіх цифр, якщо цифри можуть повторюватися?

Розв’язування. Будь-яке чотиризначне число розглядаємо як комбінацію (a₁, a₂, a₃, a₄), де a_i – відповідний розряд числа (i = ). Елемент a₁  A₁ = {1, 2, ..., 9}, тому що старший розряд не дорівнює 0, a₂  A₂ = {0, 1, 2, ..., 9}, a₃  A₂, a₄  A₂, оскільки цифри можуть повторюватися. Тоді за правилом добутку всього є

N = 9  10  10  10 = 9000 чисел.

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

Розв’язування. Прапор розглядаємо як комбінацію (a₁, a₂, a₃), де a_i – колір i-ої смуги (i = 1, 2, 3). Першу із смуг вибираємо із множини 5-ти різних кольорів, другу – із множини 4-х кольорів (смуги не повторюються) і при цьому вибір a₂ залежить від вибору a₁, третя смуга вибирається із множини з 3-х кольорів і вибір a₃ залежить від вибору a₁ і a₂. Тому за правилом добутку кількість таких прапорів 5  4  3 = 60.

Якщо перша смуга червона, то друга смуга вибирається із множини 4-х кольорів, а третя – із 3-х кольорів. Всього одержимо N = 4  3 = 12 прапорів. Аналогічно, якщо друга смуга червона, то є N₂ = 4  3 = 12 прапорів, і вибравши червону третю смугу, одержимо N₃ = 4  3 = 12 прапорів. Отже, за правилом суми, маємо N = 12 + 12 + 12 = 36 прапорів з червоною смугою.

Приклад 4. Автомобільні номери складаються із однієї, двох або трьох букв і чотирьох цифр. Знайти кількість таких номерів, в яких букви не повторюються, якщо використовується 32 букви українського алфавіту?

Приклад 5. Скільки різних п’ятицифрових чисел можна скласти із цифр 0, 1, 2, 3, 4, якщо в кожному числі жодна з цифр не повторюється?

Приклад 6. Скільки словників потрібно видати, щоб можна було безпосередньо виконувати переклади з будь-якої із 5 мов: української, англійської, французької, німецької, італійської на іншу з цих п’яти мов?

Приклад 7. В ящику 12 різних білих кульок і 10 різних чорних. Вибирається із нього біла або чорна кулька, після чого беруть білу і чорну кульки. В якому випадку є більша можливість вибору: якщо спочатку було взято білу або чорну кульку?

Приклад 8. У англійців прийнято давати дітям декілька імен. Скількома способами можна назвати дитину, якщо загальна кількість імен дорівнює 300, а їй дають не більше трьох імен?

Приклад 9. На пікнік поїхали 92 особи. Бутерброди з ковбасою взяли 47 осіб, із сиром – 38 осіб, із шинкою – 42 особи, із сиром і ковбасою – 28 осіб, із ковбасою і шинкою – 31 особа, із сиром і шинкою – 26 осіб. Всі три види бутербродів взяли 25 осіб, а декілька замість бутербродів взяли пиріжки. Скільки осіб взяли із собою пиріжки?

Приклад 10. У школі 1400 учнів. Із них – 1250 лижники, 952 – ковзанярі. Ні на лижах, ні на ковзанах не вміють кататися 60 учнів. Скільки учнів вміють кататися і на лижах і на ковзанах?

Приклад 11. Будь-який із учнів класу на канікули два рази був у театрі; при цьому вистави І, ІІ, ІІІ бачили відповідно 25, 12 і 23 учні. Скільки учнів у класі? Скільки із них бачили вистави І і ІІ, І і ІІІ, ІІ і ІІІ?

Приклад 12. На уроці літератури вчитель зацікавився, хто із 40 учнів класу читав книги А, В і С. Результати виявилися такі: книгу А прочитали 25 учнів; В – 22 учні; С – 22 учні, А або В – 33 учні, А або С – 32 учні, В або С – 31 учень, всі три книги – 10 учнів. Скільки учнів не читали жодної книги? Скільки учнів прочитали тільки по 1 книзі?

Приклад 13. Серед абітурієнтів, які склали вступні іспити до вузу, оцінку „5” одержали: з математики або фізики – 48, з фізики – 37, з української мови – 42, з математики або української мови – 7, з фізики або української мови – 66, з усіх трьох предметів – 4. Скільки абітурієнтів одержали хоча б одну п’ятірку? Скільки серед них одержали лише одну п’ятірку?

Приклад 14. Скільки невід’ємних чисел, менших за мільйон, містять всі цифри 1, 2, 3, 4? Скільки чисел складається тільки із цих цифр?

Приклад 15. Серед 150 людей 45 плавають, 40 їздять на велосипеді, 50 грають у теніс, 32 грають у теніс і не їздять на велосипеді, 27 грають у теніс і плавають, 10 виконують все це. Скільки людей грають у теніс і не їздять на велосипеді? Якщо відомо, що 21 їздять на велосипеді і плавають, то скільки не вміють нічого?

Приклад 16. У класі 35 учнів. З них 20 відвідують математичний гурток, 11 – фізичний, 10 не відвідують жодного гуртка. Скільки учнів відвідують математичний і фізичний гуртки? Скільки учнів відвідують лише математичний гурток?

Приклад 17. У класі 45 учнів. З них 25 хлопчиків; 30 учнів навчаються на 4 і 5, з них 16 хлопчиків; 30 займаються спортом, з них 18 хлопчиків та 17 школярів, які навчаються на 4 і 5; 15 хлопчиків навчаються на 4 і 5 і займаються спортом. Показати, що в цій інформації є помилка.

Приклад 18. Нехай |X| = m, |Y| = n, m  n. Довести, що кількість сюр’єктивних відображень з X в Y дорівнює .

Приклад 19. По пустелі іде караван з 9 верблюдів. Скількома способами можна переставити верблюдів так, щоб попереду кожного верблюда ішов інший ніж перед тим?

Приклад 20. Серед 100 студентів англійську мову знають 28 німецьку – 30, французьку – 42, англійську та французьку – 10, англійську та німецьку – 8, німецьку та французьку – 5. Скільки студентів не знають жодної мови?

Приклад 21. Скількома способами можна розставити 20 нулів і 15 одиниць так, щоб дві одиниці не стояли поруч? Відповідь обґрунтувати.

Приклад 22. У шерензі стоїть 30 людей. Скількома способами з неї можна вибрати 12 людей, які не стоять поруч?

Приклад 23. За круглим столом сидить 30 людей. Скількома способами можна вибрати 12 людей так, щоб до вибраних не потрапили два сусіда?

Приклад 24. Дано 25 різних предметів і 5 ящиків. Потрібно в кожний ящик покласти по 5 предметів. Скількома способами це можна зробити?

Приклад 25. Двоє людей повинні поділити між собою 100 гривень, 100 доларів та 100 євро. Скількома способами вони можуть це зробити?

Приклад 26. Скількома способами можна розділити 1000 гривень між 5 людьми?

Приклад 27. Скількома способами можна розділити 1000 гривень між 5 людьми за умови, що кожна людина одержує не менше ніж 50 гривень?

Приклад 28. Скількома способами можна розділити 50 гривень, 80 доларів та 100 євро між 4 особами?

Приклад 29. Є 20 чоловіків і 20 жінок. Скількома способами їх можна розсадити за круглим столом так, щоб дві особи одної статі не сиділи поруч?

Приклад 30. Скількома способами можна розсадити на карусель 20 чоловіків і 20 жінок так, щоб дві особи одної статі не сиділи поруч?

Приклад 31. Скільки існує мономів степеня n від трьох змінних x, y і z?

Приклад 32. Скільки існує мономів степеня n від k змінних?

Приклад 33. Скільки різних слів можна одержати, переставляючи букви у словах „парабола”, „математика”, „моном”?

Приклад 34. Скільки різних намист можна скласти з 20 червоних та 10 чорних кульок?

Приклад 35. У місті проживає 25000 жителів. Чи правильно, що принаймні двоє з них мають однакові ініціали?

Приклад 36. Серед 5 українців, 7 росіян та 10 англійців треба вибрати декілька людей так, щоб серед вибраних були особи всіх трьох національностей. Скількома способами можна це зробити?

Приклад 37. Скількома способами можна розбити 100 предметів на 5 груп по 20 предметів?

Приклад 38. Людина має 7 друзів і протягом 7 днів запрошує їх до себе так, щоб компанія жодного разу не повторилася. Скількома способами це можна зробити?

Приклад 39. Скількома способами можна переставити букви слова „математика” так, щоб дві голосні букви не стояли поруч?

Приклад 40. Скількома способами можна вибрати декілька букв із фрази „Око за око, зуб за зуб”? Скількома способами можна вибрати із цієї фрази 3 букви?

Приклад 41. Скільки існує семизначних чисел, у яких 4 цифри парні?

Приклад 42. Скільки існує семизначних чисел, у яких сума цифр парна?

Приклад 43. Скільки існує семизначних чисел, у яких всі цифри різні?

Приклад 44. Скільки семизначних чисел можна скласти з цифр: а) 51315113; б) 19717331; в) 18091948?

Приклад 45. Скільки є послідовностей 1  x₁ < x₂ < ... < x_k  n (x_i  N)?

Приклад 46. Скільки підмножин множини {1, 2, ..., 100} містять хоча б одне непарне число?

Приклад 47. Скільки є підстановок   S_ таких, що (1)  2?

Приклад 48. Скількома способами сукупність із 2n предметів можна розбити навпіл?

Приклад 49. Скількома способами можна розбити множину {1, 2, ..., kn} на k підмножин з n елементів?

Приклад 50. Скількома способами можна вибрати на шаховій дошці два квадрати – чорний і білий, що не лежать на тій самій горизонталі та вертикалі?

Приклад 51. Автомобільні номери складаються з двох букв та п’яти цифр. Знайти кількість таких номерів, якщо використовують 32 букви українського алфавіту?

Приклад 52. Скількома способами можна розбити m + n + p предметів на три групи так, щоб в одній було m, у другій n, а в третій p предметів?

Приклад 53. Четверо студентів складають іспит. Скількома способами можуть бути поставлені їм оцінки, якщо відомо, що ніхто з них не одержав оцінки „незадовільно”?

Приклад 54. З групи, яка складається з 7 чоловіків та 4 жінок, потрібно вибрати 6 людей так, щоб серед них було не менше ніж 2 жінки. Скількома способами можна це зробити?

Приклад 55. Скількома способами можна посадити за круглий 8 чоловіків і 8 жінок так, щоб дві жінки не сиділи поруч?

Приклад 56. Скількома способами можна переставляти букви слова „молоко”, щоб три букви „о” не стояли поряд?

Приклад 57. Знайти суму всіх чотиризначних чисел, які одержуються при довільних переставляннях цифр 1, 2, 3, 4?

Приклад 58. Скільки існує шестизначних чисел, в яких три цифри парні і три непарні?

Приклад 59. Довести, що непарну кількість предметів можна вибрати з n предметів 2^{n – 1} способами.

Приклад 60. У скількох точках перетинаються діагоналі опуклого n-кутника, якщо будь-які три з них не перетинаються в одній точці?

Приклад 61. Скількома способами можна скласти букет з 7 однакових або різних квітів, якщо є 11 сортів квитів?

Приклад 62. Скількома способами можна утворити групу з 3 солдатів і 1 офіцера, якщо є 20 солдатів і 5 офіцерів?

Приклад 63. Скільки кіл можна провести через 12 точок, розміщених так, що будь-які 4 з них не належать одному колу?

Приклад 64. Скількома способами можна одночасно з’єднати три пари серед n абонентів телефонної мережі?

Приклад 65. Скільки чисел, які менші від 1000000, можна записати за допомогою цифр 5, 7, 8?

Приклад 66. Скільки п’ятизначних чисел можна скласти з цифр числа: а) 1315113; б) 977331; в) 25565889?

Приклад 67. Маємо необмежену кількість монет вартістю 10, 25 і 50 коп. Скількома способами можна вибрати 20 монет?

Приклад 68. Скількома способами можна вибрати серед натуральних чисел від 1 до 200 два числа так, щоб їхня сума була непарною?

Приклад 69. Монету кидають 2n радів. Довести, що кількість варіантів, у яких герб за кожним разом не випав частіше ніж решітка, дорівнює 1+ ( )² + ... + ( )² = .

Приклад 70. Скількома способами можна розмістити на шаховій дошці 8 одноколірних тур, щоб будь-які дві з них не били одна одну?

Приклад 71. Довести, що при n  4 існує розміщення n одноколірних ферзів на шаховій дошці з n² клітинами, для якого будь-які два ферзі не б’ють один одного.

Приклад 72. У місті є 100 міліціонерів. Кожного вечора на чергування виходять троє. Довести, що не можна так скласти графік чергування, щоб будь-які двоє міліціонерів чергували разом лише один раз?

Приклад 73. На шкільному вечорі було 17 дівчат і 15 хлопців. Скількома способами можна вибрати серед них 4 пари?

Приклад 74. Скількома способами можна вибрати 20 осіб з 30, якщо задані двоє осіб не можуть бути вибрані разом?

Приклад 75. Скількома способами можна розділити колоду з 36 карт пополам так, щоб у кожній пачці було по два тузи?

Приклад 76. Скількома способами можна витягнути 4 карти з колоди в 36 карт так, щоб було 3 королі? Один король і три дами?

Приклад 77. Є 12 чоловіків і 16 осіб. Скількома способами можна скласти компанію: а) з 7 осіб; б) з 3 чоловіків та 4 жінок; в) з 7 чоловіків або 7 жінок?

Приклад 78. Є 12 чоловіків і 16 жінок. Скількома способами серед них можна вибрати пару (чоловік, жінка)?

Приклад 79. Скільки підмножимн множини {1, 2, ..., 2n} містять принаймні одне парне число?

Приклад 80. З міста А в місто В веде n доріг, а з міста В в місто С – k доріг. Кількома способами можна добратися з а в С і повернутися назад? А якщо назад повертатися іншими дорогами?