Комбінаторика

Перестановки

Задачі

Нехай А и В - кінцеві безлічі, що складаються з m і n елементів відповідно:

Чому дорівнює число відповідностей між А и В?

Скільки існує функцій з А и В?

Скільки існує 1-1 функцій з А и В?

При яких m і n існує взаємооднозначна відповідність між А и В?

Нехай безліч А₁ містить n₁ елементів; безліч А₂ - n₂ елементів;...., безліч А_m - n_m елементів. Скільки елементів містить їхній декартовий добуток А₁´А₂´...´А_m ?

Скільки елементів містить безліч Аⁿ , якщо |А| = S?

Чому дорівнює число відповідностей між m - елементною безліччю А і n - елементною безліччю В:

функціональних (ін’єктивних);

усюди визначених (сюр’єктивних).

Чому дорівнює число відношень між m - елементами безлічі А и n - елементами безлічі В?

Чому дорівнює число відношень на n-елементної безлічі?

Скількома способами можна скласти чотирикольоровий прапор, якщо існує матеріал семи кольорів веселки? Вирішити задачу за умови:

одна зі смуг прапора повинна бути зеленою чи червоною;

дві зі смуг повинні бути голубою і жовтою;

три смуги повинні бути синьою, зеленою і жовтою.

Скільки різних слів можна одержати, переставляючи букви в слові «математика».

Сполучення

Задачі

Довести, що безліч з n елементів має 2ⁿ підмножин.

Скільки підмножин з k елементів має безліч з n елементів?

Чому дорівнює число всіляких проекцій кортежу довжини n?

У футбольній команді є 13 гравців і 2 воротарі. Скількома способами можна вибрати граючий склад (11 гравців, у тому числі один воротар)?

Визначити число всіляких наборів з п'яти різних елементів по трьох, якщо в кожнім наборі:

усі предмети різні;

однакові предмети можуть повторюватися.

Рекуррентные співвідношення

Задачи

В офісі є дев'ять робочих місць, з яких на двох можуть працювати тільки жінки, на трьох — тільки чоловіки і на чотирьох — чоловіки і жінки. Скількома способами можна розподілити трьох жінок і чотирьох чоловіків на ціх місцях?

Покажіть, що число сполучень з п елементів по r дорівнює числу n-перестановок з повтореннями з r елементів одного типу і n - r елементів іншого типу, тобто

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

Задачі

Визначити за допомогою біноміальних коефіцієнтів число наборів з п'яти різних елементів по три, якщо в кожнім наборі:

усі предмети різні;

однакові предмети можуть повторюватися.

Довести властивості біноміальних коефіцієнтів:

C(n, k) = C(n, n-k);

C(n, k)*C(k, r) = C(n-r, k-r)*C(n, r).

Поліноміальні і експонентні виробляючі функції

Задачі

Нехай у сполучення з повтореннями з п елементів по r повинні обов'язково входити елементи k фіксованих типів (k п). Показати, що число таких сполучень дорівнює С(r + п – k - 1, r—k). Зокрема, якщо в кожне сполучення повинний входити хоча б один елемент кожного з п типів (це можливо тільки при п £ r), то число таких сполучень дорівнює С(r – 1, r - п).

Вираз розкладається в суму членів виду з деякими коефіцієнтами, де числа приймають усілякі значення від 0 до п, причому . Покажіть, що для даного розкладання:

коефіцієнт при члені дорівнює числу перестановок з повтореннями з n елементів зі специфікацією , тобто

кількість усіх членів дорівнює числу n-сполучень з повтореннями з k елементів, тобто

сума всіх коефіцієнтів дорівнює .

На підставі співвідношень попередньої задачі для вираження (а + 3b + 5з - d)⁶ визначити:

коефіцієнти при членах і ;

кількість усіх членів розкладання.

Принцип включення і виключення

Задачі

З 30 співробітників англійську мову знають 19, німецьку— 17, французьку— 11, англійську і німецьку— 12, англійську і французьку — 7, німецьку і французьку — 5, усі три мови — 2. Скільки співробітників не володіють іноземними мовами? Скільки з них знають тільки англійську, тільки німецьку, тільки французьку мови?

Показати, що число натуральних чисел, що поділяються на n і не переважає x, дорівнює [x/n].

Знайти число цілих позитивних чисел, що не перевершують 200 і не поділяються на жодне з чисел 3, 5, 7.

Знайти число простих чисел, що не перевершують 250.

Розбивки

Задачі

N урн випадковим образом заповнюються п кулями (n < N). Знайти імовірність того, що кожна з п перших урн буде містити точно по одній кулі, якщо урна може прийняти:

не більше однієї кулі;

будь-яке число куль, яке не перевищує п.

Покажіть, що

Знайти число способів розподілу 23 студентів у групи по 3 і 5 чоловік.

БулЄва АЛГЕБРА