Завдання до виконання

1. Нехай М={1,2,3,4,5}. Навести всі розміщення та сполучення без повторень з елементів множини М по 3 елементи.

2. Розмістити наведені перестановки елементів множини {1,2,3,4,5,6} у лексикографічному порядку: 456321, 231564, 132456, 156423, 165432, 543216, 541236, 314562, 341526, 654312, 432561, 653412.

3. Знайти лексикографічно наступну для кожної з перестановок: 54123; 1432; 12453; 45231; 6714235; 31528764.

4. За допомогою алгоритму побудови лексикографічно наступної перестановки записати перші 10 розміщень з 6 по 4 елементи множини {1,2,3,4,5,6}.

5. Побудувати перші 12 перестановок елементів множини {а, б, в, г, д} у лексикографічному порядку.

6. Побудувати 3 лексикографічно наступних розміщення з повтореннями 7 по 4 елементи на множині {а, б, в, г, д, е, з} для кожного з розміщень гвба, абвг, зеде, баба, бевз, aaвз.

7. Виписати всі розміщення без повторень по два елементи та розміщення з повтореннями по два елементи множини {1, 2, 3, 4}. Виписати всі сполучення з повтореннями по два елементи цієї ж множини.

8. Знайти або довести не існування лексикографічно наступних сполучень без повторень на множині A = {a, b, c, d, e} для кожного з розміщень: dab, ad, be, abce, ade, acde, cde.

9. Виписати всі сполучення без повторень по три елементи множини {1, 2, 3, 4, 5}.

10. Виписати всі сполучення з повтореннями по три елементи множини {1, 2, 3, 4, 5}.

11. Написати алгоритм, який би виводив всі слова з літер {a,b,c,d}, довжина яких рівна 6, а однакові літери не стоять поруч.

12. Написати алгоритм виплати заданої суми грошей усіма можливими способами. В наявності є купюри вартістю 1,2,5,10,20,100 гривень. Кількість купюр кожного виду не обмежується.

13. Панянка збирається запросити своїх сімох друзів на каву. Кожен раз вона вирішує запрошувати тільки трьох з семи друзів. Крім того, вона хоче, щоб кожні з двох її гостей обов'язково зустрілися за столом. Реалізувати алгоритм перебору. Скількома способами це можна зробити? Як організувати перебір, щоб кожна пара гостей зустрічалася у неї мінімальну кількість разів?

14. *Написати алгоритм або програму, яка виводитиме всі тризначні числа, які діляться на всі свої цифри. Як оптимізувати алгоритм, щоб зменшити кількість операцій для перевірок ділення?

15. *Написати алгоритм або програму, яка виводитиме всі тризначні числа, які володіють такими властивостями:

а. число ділиться на всі свої цифри;

б. число, отримане з вихідного шляхом запису його цифр у зворотному порядку, також ділиться на всі свої цифри. Прикладом такого числа буде 216, яке ділиться на всі свої цифри і “перевернувши” яке, отримаємо 612, яке теж ділиться на всі свої цифри.

16. **Написати програму або алгоритм, яка з букв A, B, C будує слова довжиною N, в якому два з будь-яких підслів, які стоять поруч, різні. Наприклад, слово - ABCABA – правильне, а слово CABABC - неправильне, тому що поєднання букв AB стоять поруч.

17. На комп’ютері є файли великого розміру. Необхідно їх скопіювати на два інші носії з мінімальними затратами часу. Вважати, що час копіювання залежить тільки від розміру файлів. Швидкість копіювання на носії вважається однаковою, тому файли необхідно розбити на дві групи однакові чи близькі за розміром. Вважається, що окремі файли архівувати і розбивати не варто, бо це додаткові затрати часу.

Запропонувати алгоритм перебору, який би вирішував цю задачу. Як можна оптимізувати алгоритм?

18. *Запропонувати алгоритм перебору для попередньої задачі, але з можливістю копіювати на кілька носіїв. Яке розбиття необхідно застосувати? Як потрібно змінити алгоритм, якщо швидкість копіювання на різні диски різна?

19. *На комп’ютері знаходяться папки з файлами, які мають різний розмір. Необхідно скопіювати ці папки на DVD-диски, використавши мінімальну кількість дисків. Файли у папках не можна переміщати. Вважати, що розмір папок менший 4 Гб. Напишіть алгоритм, який би шукав цей оптимальний розподіл.

20. *Запропонувати алгоритм перебору для попередньої задачі, але папки можуть мати розмір більший 4 Гб і є диски різної розміру (8 Гб, 20 Гб). Вважати, що диски, більші за розміром, є суттєво дорожчі, і тому їх можна використовувати тільки в тому випадку, якщо папка перевищує розмір 4 Гб.

21. *Тролінг Комбінаторна задача, яка пропонувалася на Всеукраїнській студентській олімпіаді з програмування у тренувальному турнірі, 19 квітня 2012.

У мові тролів 5 приголосних звуків {h, k, m, r, t} і 3 голосних {a, o, u}. Кожне слово починається з приголосної букви, причому в слові не може бути підряд дві голосні або приголосні.

N тролів по черзі називають найкоротше слово, яке ще не назвав ніхто з попередніх тролів. Якщо варіантів декілька, то троль вибирає найменше лексикографічно. Лексикографічний порядок h<k<m<r<t<a<o<u.. При цьому слова порівнюють спочатку по першій букві. Якщо перші літери однакові, то по другий і т. д. Тобто порядок слів такий: h, k, m, r, t, ha, ho, hu, ka, ko, …

Знайти слово, яке назве N-ий троль.

22. **Написати алгоритм, які б розфарбовував вершини куба в три кольори (наприклад, червоний, синій, зелений). Скількома способами це можна зробити?

23. **Скількома способами можна розфарбувати грані куба в чотири кольори? Запропонувати алгоритм перебору.

24. Обчислити значення:

; ; ; ; ; .

25. Обчислити значення:

; ; ; ; ; .

26. Обчислити значення:

; ; ; ; ; .

27. Обчислити значення:

; ; ; ; ; .

28. Обчислити кількість перестановок множини {a, b, c, d, e}, які закінчуються буквою d і починаються літерою b.

29. Скількома способами можна визначити призові місця (перше, друге, третє) у забігу 10 коней?

30. Скількома способами можна поселити 12 студентів у 4 кімнати гуртожитку, поселяючи їх по троє в кожній?

31. У групі n чоловіків і n жінок. Скількома способами їх можна вишикувати в шеренгу так, щоб чергувалися чоловік і жінка?

32. Дано множину М={1, 2, 3, …, 19, 20}. Скільки існує розміщень без повторень з елементів множини М по чотири елементи, які містять:

а. число 13;

б. водночас числа 13 і 14;

в. водночас числа 13, 14 і 17;

г. водночас числа 13, 14, 17 і 20;

д. чотири послідовні числа у висхідному порядку;

е. три послідовні числа у висхідному порядку?

33. Скількома способами можна розсадити п’ять осіб за круглим столом?

34. Скількома способами з 28 кісток доміно можна утворити пару кісток, які можна докласти одна до другої за правилами доміно?

35. Скількома способами можна розсадити за круглим столом п’ятьох чоловіків і п’ятьох жінок, щоб двоє чоловіків не сиділи поруч?

36. Із цифр 1, 2, 3, 4, 5, не повторюючи їх, склали всі п’ятицифрові числа. Скільки серед них чисел, які:

а. починаються цифрою 3;

б. не починаються цифрою 5;

в. починаються з 54?

37. Дано натуральні числа від 1 до 25. Скількома способами можна вибрати з них два числа так, щоб їх сума була парним числом? Три числа? Чотири?

38. Скількома способами можна поставити на полицю 9 книжок:

а. якщо серед них є один тритомник, усі томи якого мають стояти поруч у довільному порядку;

б. щоб усі томи тритомника стояли поруч за зростанням номерів томів?

39. Скільки учасників у шаховому турнірі, якщо відомо, що кожний учасник зіграв із кожним із решти, а всього відбулося 210 партій?

40. Скількома способами з колоди 52 карт можна вийняти 10 карт, щоб серед них були такі:

а. точно один туз;

б. принаймі один туз;

в. не менше двох тузів?

41. Скількома способами можна вибрати пару однакових карт (дві дами, два туза, тощо) із колоди 36 карт? Три однакові карти? Три карти однієї масті?

42. Скільки різних рядків із п’яти літер можна утворити з алфавіту, який має 26 літер, якщо повторення дозволені?

43. Скільки різних рядків можна утворити зі слова MISSISSIPPI, використовуючи всі букви? Скільки таких рядків починаються та закінчуються літерою S? У скількох таких рядках усі чотири букви S стоять поруч?

44. Множина містить 10 елементів. Знайти кількість підмножин цієї множини, що містять більше одного елемента.

45. Скільки бітових рядків можна утворити з семи нулів і чотирьох одиниць?

46. Скільки бітових рядків можна утворити з одинадцяти нулів і трьох одиниць, якщо кожний рядок обов’язково має починатися з одиниці та після кожної одиниці має бути принаймні два нулі?

47. Побудувати розклад:

; ; ; .

48. Визначити коефіцієнти у розкладі при .

49. Визначити п’ятий член розкладу бінома , якщо відношення коефіцієнта третього члена до коефіцієнта другого члена дорівнює 11/2. Члени бінома пронумеровано від 1 до n + 1.

50. У розкладі бінома коефіцієнт третього члена дорівнює 28. Визначити середній член розкладу.

51. Визначити найменше значення показника n у розкладі , за якого відношення двох сусідніх коефіцієнтів дорівнює 7/15.

52. У розкладі бінома визначити член, який не залежить від а.

53. Скільки раціональних членів міститься в розкладі ?

54. У розкладі бінома визначити член, що містить , якщо сума біноміальних коефіцієнтів на непарних місцях у розкладі дорівнює 2048.

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

56. Нехай М - скінченна множина. Довести, що підмножин множини М із парною кількістю елементів стільки, скільки й підмножин із непарною кількістю елементів.

57. Довести, що

58. Довести біноміальну теорему алгебрично за допомогою математичної індукції.

59. Довести, що

60. Записати розклад

61. Знайти коефіцієнт при у розкладі

62. Знайти кількість членів (доданків) у розкладі

63. Скільки потрібно запросити людей, аби щонайменше шість із них народилися під одним і тим самим знаком зодіаку?

64. Скільки має бути людей, щоб принаймні двоє з них народилися в один і той самий день тижня та в один і той самий місяць (можливо, у різні роки)?

65. Позначимо М як множину з десяти натуральних чисел, які не перевищують 50. Довести, що є принаймні дві різні п'ятиелементні підмножини множини М такі, що суми їх елементів рівні.

66. Скільки елементів містить об'єднання п'яти множин, якщо кожна з них містить 10000 елементів, кожна пара — 1000 спільних елементів, кожна трійка – 100, кожна четвірка – 10 спільних елементів і один елемент належить усім п'яти множинам?

67. Скільки розв'язків має рівняння х₁ + х₂ + х₃ = 11, якщо х₁, х₂, х₃ – невід'ємні цілі числа, менші, ніж 6?

68. Знайти кількість розв'язків рівняння х₁ + х₂ + х₃ + х₄ = 17, якщо х_1, х₂, х₃, x₄ – цілі числа такі, що х₁ ≤ 3, х₂ ≤4, х₃ ≤ 5, х₄ ≤ 8.

69. Знайти кількість розв’язків наведених нижче рівнянь у невід’ємних цілих числах:

а. ;

б. ;

в. за умови

70. Знайти кількість розв’язків рівняння де - невід’ємні цілі числа, за наступних умов:

а. ;

б. для j=1, 2, 3, 4, 5;

в. ;

г.

71. Знайти кількість розв’язків нерівності у невід’ємних цілих числах.

72. Знайти кількість додатних цілих чисел, менших за 1 000 000, сума цифр яких дорівнює 19.

73. Знайти кількість додатних цілих чисел, менших за 1 000 000, що мають точно одну цифру 9, і сума їхніх цифр дорівнює 13.

Контрольні запитання.

1. За допомогою яких правил можна здійснити усі обчислення в комбінаториці? Сформулюйте та наведіть приклади їхнього використання.

2. Що таке вибірка? Які типи вибірок ви знаєте?

3. Дайте визначення поняттям «перестановки», «сполучення», «розміщення». На прикладі пояснити різницю між даними поняттями.

4. Що необхідно для реалізації алгоритму перебору?

5. Що таке лексикографічний порядок? Наведіть приклад.

6. Які кроки необхідно зробити для алгоритму перебору розміщень з повторенням та без?

7. Визначити кроки, необхідні для алгоритму перебору перестановок.

8. У чому полягає особливість алгоритму перебору сполучень з повторенням та без?

9. На прикладі покажіть як можна обчислити кількість розміщень та сполучень з повторенням та без.

10. За допомогою яких формул можна порахувати кількість перестановок із повторенням та без?

11. Визначити основні кроки алгоритму перебору всіх розбиттів множини.

12. На прикладах покажіть два способи розв’язання задачі розкладання в ящики.

13. На прикладі реалізуйте алгоритм перебору всього розбиття множини.

14. Що таке числа Белла та числа Стірлінга другого роду? Яка між ними різниця?

15. Яка послідовність називається унімодальною?

16. Що таке біном Ньютона та біноміальні коефіцієнти?

17. Які властивості мають біноміальні коефіцієнти?

18. Яка формула є узагальненням біному Ньютона? Сформулюйте.

19. Сформулюйте задачу про цілочисельні розв’язки та на прикладі покажіть її розв’язання.

20. У чому суть принципу коробок Діріхле?