7.4: Загальні комбінаторичні задачі

Як це часто буває, практикуючи один тип проблеми за раз, корисно освоїти методи, необхідні для вирішення цього типу проблеми. Складніше вирішити, над яким типом проблеми ви працюєте, і вибір, які методи використовувати для вирішення проблеми. У цьому розділі об'єднані типи завдань з попередніх трьох розділів.

ВПРАВИ 4.4
НАБІР I
1) Скільки рядків з шести малих букв з англійського
\(\quad\) алфавіту містять а) букву\(a ?\)
\(\quad\) б) букви\(a\) і \(b\)в послідовних позиціях з\(a\)\(b\) попередніми, з усіма літерами відмінні?
\(\quad\)в) букви\(a\) і\(b\), де\(a\) знаходиться десь зліва від\(b\) рядка, з усіма літерами відмінні?
2) Сім жінок і дев'ять чоловіків перебувають на факультеті математичного відділення в школі.
\(\quad\)а) Скільки існує способів вибору комітету з п'яти членів відділу, якщо хоча б одна жінка повинна бути в комітеті?
\(\quad\)б) Скільки існує способів вибору комітету з п'яти членів відділу, якщо в комітеті повинні бути хоча б одна жінка і хоча б один чоловік?
3) Припустимо, що відділ містить 10 чоловіків і 15 жінок. Скільки способів створити комітет з 6 членами, якщо він повинен мати однакову кількість чоловіків і жінок?
4) Англійський алфавіт містить 21 приголосні і 5 голосних. Скільки рядків з 6 малих букв англійського алфавіту містять:
\(\quad\) а) рівно одну голосну?
\(\quad\)б) рівно 2 голосні?
\(\quad\)в) принаймні 1 голосна?
\(\quad\)г) принаймні 2 голосні?
5) Скільки способів вибрати 12 країн в Організації Об'єднаних Націй для роботи в раді, якщо 3 обрані з блоку 45,4 з блоку, а інші\(57,\) обрані з решти 69 країн?
6) Припустимо, що відділ містить 10 чоловіків і 15 жінок. Скільки способів створити комітет з 6 членами, якщо він повинен мати більше жінок, ніж чоловіків?
7) Скільки номерних знаків, що складаються з трьох букв, за якими слідують три цифри, не містять букви або цифри двічі?
8) У жіночому турнірі з тенісу на Вімблдоні за титул змагаються два фіналістки, А і Б, який буде присуджений першому гравцеві, який виграв два сети. Скільки різних способів може бути завершено матч?
9) У чоловічому турнірі з тенісу на Вімблдоні, два фіналіста,\(A\) і\(B\), змагаються за титул, який буде присуджений першому гравцеві, який виграв три сети. Скільки різних способів може бути завершено матч?
10) Скільки різних способів може бути обрана колегія з 12 присяжних та 2 альтернативних присяжних з групи з 30 майбутніх присяжних?

SET II
11) Клас має 20 учнів, з яких 12 - жінки, а 8 - чоловіки. Скільки способів може бути обраний комітет з п'яти студентів з класу, якщо:
\(\quad\) а) Ніяких обмежень на вибір студентів
\(\quad\) b) чоловіки не включені в комітет
\(\quad\) c) Комітет повинен мати трьох жінок-членів і 2 чоловіки члени
12) Комітет шкільного танцю повинен бути обраний з групи студентів, що складається з шести першокурсників, восьми другокурсників, дванадцяти юніорів і десяти людей похилого віку. Якщо комітет повинен складатися з двох першокурсників, трьох другокурсників, чотирьох юніорів і п'яти пенсіонерів, скільки способів це можна зробити?
13) Театральна трупа складається з 22 акторів - 10 чоловіків і 12 жінок. У наступному спектаклі режисерові потрібно відкинути провідного чоловіка, провідну даму, що підтримує чоловічу роль, підтримує жіночу роль і вісім статистів (три чоловіки і п'ять жінок). Скільки способів ця гра може бути кинута?
14) Хокейний тренер має 20 гравців, з яких дванадцять грають вперед, шість грають в захист і два воротарі. Скільки способів тренер може вибрати склад, що складається з трьох нападаючих, двох гравців оборони і одного воротаря?
15) Скільки способів десять учнів можуть бути розташовані поспіль для зображення класу, якщо Джон і Джейн хочуть стояти поруч один з одним, а Ед і Саллі також хочуть стояти поруч один з одним?
16) Скільки способів можуть бути влаштовані учні в попередній задачі, якщо Ед і Саллі хочуть стояти поруч один з одним, але Джон і Джейн відмовляються стояти поруч один з одним?
17) Скільки способів можна посадити чотирьох чоловіків і чотирьох жінок в ряд по вісім місць, якщо:
\(\quad\) а) Перше місце займає чоловік
\(\quad\) б) Перше і останнє місця займають жінки

SET III
18) Номер соціального страхування людини являє собою послідовність з дев'яти цифр, які не обов'язково відрізняються. Скільки номерів соціального страхування можливо?
19) Ім'я змінної в мові програмування BASIC - це або буква алфавіту, або буква, за якою слідує цифра. Скільки різних імен змінних існує в мові BASIC?
20) а) Скільки парних чисел між 0 і 100?
б) Скільки парних чисел з різними цифрами між 0 і
\(100 ?\)
21) Існує шість символів - три літери англійського алфавіту, за якими слідують три цифри - які з'являються на задній панелі певної марки принтера в якості ідентифікації число. Знайти кількість можливих ідентифікаційних номерів, якщо
\(\quad\) а) символи можуть повторюватися
\(\quad\) б) цифри не можуть повторюватися в
\(\quad\)) букви не можуть повторювати
\(\quad\) d) символи не можуть повторюватися
22) послідовність символи називають паліндромом, якщо він читає однакові вперед і назад. Наприклад,\(\mathrm{K} 98 \mathrm{EE} 89 \mathrm{K}\) восьмизначний паліндром і\(\mathrm{K} 98 \mathrm{E} 89 \mathrm{K}\) являє собою семизначний паліндром. ЛЮДИНА ПЛАН КАНАЛУ ПАНАМА також є паліндром, як це був щур я бачив, TACO CAT, TANGY ГНАТ, і НІКОЛИ НЕ ДИВНО АБО НАВІТЬ. Знайдіть кількість дев'яти символьних паліндромів, які можуть бути утворені за допомогою букв алфавіту таким чином, щоб жодна буква не з'являлася більше двох разів у кожному.
23) Знайти кількість способів формування чотирибуквенної послідовності за допомогою букв\(A\),
В,\(C, D\) і\(E\) якщо:
\(\quad\) а) допускаються повторення
\(\quad\) б) повторення не допускаються в
\(\quad\)) послідовність містить букву,\(A\) але повторення не допускаються
\(\quad\) d) послідовність містить букву\(A\) і повторення дозволені
24) У комітеті зі збору коштів 10 членів A, B, C, D, E, F, G, H, I і J. Перше завдання комітету - вибрати з цієї групи голови, секретаря і скарбника. Жодна фізична особа не може займати більше однієї посади. Скільки способів можуть бути заповнені ці три посади, якщо:
\(\quad\) а) ніхто не має жодних заперечень щодо займання жодної з цих посад
\(\quad\) б) Cпотрібно бути головою в)\(\quad\) Б не хоче бути головою
\(\quad\)
\(\quad\)г)\(\quad\) А не бажає служити головою або секретарем
\(\quad\) е) або я або J повинні бути скарбником
\(\quad\) f)\(\quad\) E\(F\) або\(G\) повинні мати одну з трьох офісів
25) Знайти кількість способів вибираючи кожен з наступних зі стандартної колоди карт.
\(\quad\)а) король і ферзь
\(\quad\) б) король або ферзь в
\(\quad\)) король і червона картка
\(\quad\) г) король або червона картка
26) Є три мости, що з'єднують два міста А і Б. Між містами Б і
C є чотири містки. Продавець повинен подорожувати від А до С через Б. Знайти:
\(\quad\) а) кількість можливих варіантів мостів від А до\(C\)
\(\quad\) б) кількість варіантів для поїздки в обидва кінці від А до С і назад до А
\(\quad\) в) кількість варіантів для раунду відключення, якщо жоден міст не може бути
перетнутий двічі 27) Послідовність цифр, в якій кожна цифра дорівнює 0 або 1 називається двійковим числом. Восьмизначні двійкові числа часто називають «байтами».
\(\quad\)а) Скільки байтів можливо?
\(\quad\)б) Скільки байт починаються з 10 і закінчуються на\(01 ?\)
\(\quad\) c) Скільки байтів починаються з 10 але не закінчуються на\(01 ?\)
\(\quad\) d) Скільки байт починаються з 10 або закінчуються на\(01 ?\)
28) Група з 12 повинна бути сидячи в ряд стільців. Скільки способів це можна зробити, якщо:
\(\quad\) а) дві людини,\(A\) і\(B\) повинні сидіти поруч один з одним?
\(\quad\)б) дві людини\(A\) і не\(B\) повинні сидіти поруч один з одним?
29) Змінна в мові FORTRAN - це послідовність, яка має не більше шести символів, причому перший символ - це буква алфавіту, а решта символів (якщо такі є) - або літери, або цифри. Скільки різних імен змінних можливі?
30) Чотири універсали, п'ять седанів і шість фургонів повинні бути припарковані в ряд з
15 місць. Знайти кількість способів паркування транспортних засобів, якщо:
\(\quad\) а) універсали припарковані на початку, потім седани, потім фургони
\(\quad\) б) транспортні засоби одного типу повинні бути припарковані разом