 Правила комбинаторики

В комбинаторике, которая возникла раньше теории множеств, правило нахождения числа элементов объединения двух (или нескольких) не пересекающихся конечных множеств называют правилом суммы, а правило нахождения декартово произведение конечных множеств – правилом произведения.

Правила суммы и произведения могут быть использованы и в случае, когда рассматриваются более двух объектов.

Пример 7. На одной полке книжного магазина стоит 20 различных книг, а на другой – 40 различных книг (и не таких, как на первой полке). Сколькими способами можно выбрать одну книгу?

Решение.

Что дано? Две полки. Одна полка – это первый объект, с которой книги можно взять 20 способами, другая полка – второй объект, с которой книги можно взять 40 способами.

Что нужно сделать? Вычислить количество возможных способов выбора книги с двух полок.

Так как книгу можно взять илис первой полки,или– со второй, то количество возможных способов выбора книги с этих полок вычисляется по правилу суммы:способами.

Ответ. Возможно 60 способов выборка книги с двух полок.

Пример 8. Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и трое туфель. Сколько нарядов может иметь студентка?

Решение.

Что дано? Гардероб девушки: 4 блузки, 5 юбок и 3 туфель.

Что нужно сделать? Вычислить количество возможных способов составления нарядов студенткой.

Так как наряд студентки одновременно состоит из блузки, юбки итуфель, то количество возможных способов составления нарядов студенткой вычисляется по правилу произведения:способов.

Ответ.Возможно составления 60 комбинаций нарядов.

Пример 9. Автомобильные номера состоят из трех букв (всего 30 букв) и четырех цифр (используется 10 цифр). Сколько автомобилей можно занумеровать таким способом, чтобы никакие два автомобили не имели одинаковые номера?

Решение.

Что дано? Автомобильный номер, состоящий из 3 букв и 4 цифр. Всего букв – 30, цифр – 10.

Что нужно сделать? Вычислить количество возможных способов занумерования автомобилей.

1. Автомобильный номер состоит одновременно ииз букв,ииз цифр, поэтому нужно воспользоваться правилом произведения способов выбора 3 букв и 4 цифр.

2. Так как цифры и буквы берутся сразу не все, а только часть, важен порядок их выбора и они могут в номере повторяться, то это размещения с повторениями:

,.

3. По правилу произведения получаем: .

Ответ.Возможно 270 000 000 способов составления номеров у автомобилей.

Упражнения для выполнения

1. Дайте определение перестановки через упорядоченные подмножества, а размещения – через кортеж длины k.

2. Заполните следующую таблицу:

   Варианты способов выбора элементов		Формула
   На «языке» комбинаторики	На теоретико–множественном языке
   Перестановки с повторением из nэлементов	Перестановками nразличных элементов называются все его упорядоченные подмножества (кортежи с длиноюn), каждое из которых содержитnэлементов.
   Сочетания без повторения из n элементов поk
   Размещения с повторениями из n элементов поk
   Перестановки без повторения из kэлементов
   Сочетания с повторением из n элементов поk
   Размещения без повторения из n элементов поk

3. Составьте всевозможные сочетания по 2 элемента без повторений из элементов множества . Сравните числа:

• и;

• и.

Какой вывод можно сделать¹?

4. Не производя вычислений, выберите равные из следующих чисел: ,,,,,,,,,,,,,.

5. Вычислите:

   а) ;	ж) ;	н) ;	у) ;	ю) ;
   б) ;	з) ;	о) ;	ф) ;	я) .
   в) ;	и) ;	п) ;	х) ;
   г);	к);	р) ;	ш);
   д) ;	л) ;	с) ;	щ) ;
   е) ;	м) ;	т) ;	э) ;

6. Проверьте равенство:

   1. ;

   2. ;

7. Решите уравнения:

8. Покажите, что в нижеприведенных задачах рассматриваются перестановкиизnэлементов, определите значениеn, определите вид выборки:

   1. Сколькими способами можно составить ведомость для начисления зарплаты, если в список должны войти десять лиц?

   2. Сколькими способами nчеловек могут сесть на одной скамейке?

   3. Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?

   4. Сколькими способами можно расставить белые фигуры (1 король, 2 слона, 2 ладьи, 2 коня и 1 ферзь) на первой линии доски.

   5. Сколько способов разделить 28 костей домино между четырьмя игроками поровну?

   6. Сколькими способами можно 10 человек разбить на три группы соответственно по 2, 3, 5 человек в группе?

9. Покажите, что в нижеприведенных задачах рассматриваются размещенияизnэлементов поk, определите значенияnиk, определите вид выборки:

   1. Сколькими способами пять человек могут обменяться фотографиями?

   2. Сколько мелодий можно сыграть с помощью трех клавиш из семи?

   3. В соревновании участвуют 10 человек. Сколькими способами можно между ними распределить 3 призовых места?

   4. Сколькими способами можно составить флаг из трех вертикальных полос различных цветов, если есть материя 6 различных цветов?

   5. Сколькими способами можно разместить 8 пассажиров в три вагона?

   6. Вдоль дороги стоят 6 светофоров. Сколько может быть различных комбинаций их сигналов, если каждый светофор имеет 3 состояния: «красный», «желтый», «зеленый»?

10. Покажите, что в нижеприведенных задачах рассматриваются сочетанияизnэлементов поk; определите значенияnиk; определите вид выборки:

    1. Сколько рукопожатий получится, если здороваются 7 человек?

    2. Сколько аккордов можно сыграть с помощью трех клавиш из семи?

    3. Сколькими различными способами можно выбрать три различные краски из имеющихся пяти?

    4. В почтовом отделении имеются открытки 3 видов. Сколькими способами можно купить набор из 5 открыток?

    5. Сколько будет костей домино, если в их образовании использовать все цифры?

    6. Сколько существует прямоугольных параллелепипедов, длина ребра которых выражается целым числом от 1 до 9?

11. Укажите, какие из следующих задач являются задачами на применение правила суммы, а какие на правило произведение:

    1. На одной полке книжного магазина стоит 20 различных книг, а на другой – 40 различных книг. Сколькими способами можно выбрать одну книгу?

    2. В комнате студенческого общежития живут трое студентов. У них есть 4 разных чашек, 5 разных блюдец, 6 разных чайных ложек. Сколькими способами они могут накрыть стол для чаепития?

    3. Преступник может проникнуть в квартиру либо через входную дверь, либо через окно. Число способов проникновения через дверь – 4, через окно – 3. Сколько всего существует способов проникновения в квартиру?

    4. Во взводе 26 курсантов. Сколько существует способов назначения командира взвода и его заместителя?

    5. Сколько может быть различных комбинаций выпавших граней при бросании двух игральных костей²?

    6. В группе 11 девушек и 9 юношей. Сколькими способами можно выбрать 1 человека для работы у доски?

    7. Из города Ав городВведут 6 дорог, а из городаВв городС– 3 дороги. Сколькими способами можно проехать из городаАв городС?

12. Определите, на какие правила или формулы комбинаторики приведены следующие задачи:

    1. Сколькими способами могут быть расставлены 8 участниц финального разбега на восьми беговых дорожках?

    2. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6?

    3. Имеется девять различных книг, четыре из которых – учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?

    4. Семь мальчиков, в число которых входят Иван и Василий, становятся в ряд. Найдите число возможных комбинаций, если:

• Иван должен находиться в конце ряда;

• Иван должен находиться в начале ряда, а Василий – в конце ряда;

• Иван и Василий должны стоять рядом.