Математика и информатика. Филимонова Л.В - 27 стр.

                                                     27

      Все расчетные формулы комбинаторики базируются на двух ос-
новных правилах:
      1. Правило суммы: если объект А может быть вы-
         бран n способами, а объект В – m способами,
         то выбор «А или В» может быть осуществлен
         n+m способами.
      2. Правило произведения: если объект А может
         быть выбран n способами и после каждого из
         таких выборов объект В – m способами, то вы-
         бор «А и В» в указанном порядке может быть
         осуществлен n⋅m способами.
      Пример 4.3.1. Сколько различных трехзначных чисел можно
составить из цифр 0, 1, 2, 3?
      Решение: На первое место в трехзначном числе можно выбрать
любую цифру их трех (кроме нуля), после каждого такого выбора на
второе место можно поставить любую цифру из оставшихся трех, на
третье – из оставшихся двух. По правилу 2 получим: 3⋅3⋅2=18 чисел.♦

                                Примеры
Пример 1. Сколькими способами можно раскрасить диаграмму из 4
столбцов четырехцветной ручкой так, чтобы каждый столбец был ок-
рашен в определенный цвет.
Решение: Порядок расположения элементов имеет значение и в диа-
грамме 4 столбца, а ручка тоже четырехцветная, т.е. все элементы
присутствуют в соединении, следовательно, это соединение – пере-
становка. А так как окраска столбцов не повторяется (в условии ска-
зано, что столбцы имеют разные цвета), то это перестановка без по-
вторения. Итак, Pn = n! = 4! = 1⋅2⋅3⋅4 = 24
Ответ: столбцы можно закрасить 24 способами.
Пример 2. Имеется 5 кружков: 3 белых и 2 черных. Сколько различ-
ных узоров можно получить, располагая кружки в ряд.
Решение: Порядок расположения элементов имеет значение и в узоре
5 кружков, т.е. все элементы присутствуют в соединении, следова-
тельно, это соединение – перестановка. А так как окраска кружков по-
вторяется (в условии сказано, что 3 белых и 2 черных), то это переста-
новка с повторением. Итак,
             (n1 + n2 + ... + nk )!          5! 4 ⋅ 5
Pn (3,2) =                              =        =      = 10
                n1!⋅n 2 !⋅... ⋅ n k !       3!⋅2! 1 ⋅ 2
Ответ: узор можно составить 10 способами.
Пример 3. Сколько словарей надо издать, чтобы можно было непо-
средственно выполнить перевод с любого из 5 языков на любой из 5
языков.
Решение: Порядок имеет значение (так как русско-английский и анг-
ло-русский словари различны) и не все элементы присутствуют в со-