Принцип произведения

Принцип суммы.

Пусть множество состоит из n элементов, а множество из элементов и Ø, тогда множество содержит элементов.

Принцип суммы по индукции распространяется на множеств.

Необходимо выполнить одно за другим действий. Если первое действие может быть выполнено способами, второе – способами, третье – способами, и так далее до - ого действия, которое может быть выполнено способами, тогда все действий могут быть выполнены способами.

Пример 1.1: Номер автомобиля состоит из двух букв, за которыми следует трехзначное число. Сколько существует различных автомобильных номеров?

Решение:

Мы можем считать, что номер автомобиля состоит из 5 мест, на первые два из которых надо поставить буквы, а на остальные – цифры. Первое место можно заполнить любой из 26 букв латинского алфавита, т.е. 26^ю способами. После этого второе место мы можем заполнить также 26^ю способами, т.к. повторения букв разрешаются. Аналогично третье место можно заполнить 9 способами, так как цифр всего 10, но с цифры 0 не может начинаться трехзначное число. Четвертое место можно заполнить 10 способами, пятое – также 10 способами, так как 0 может находиться в середине или в конце трехзначного числа. По принципу произведения получаем:

Ответ: 608400 автомобильных номеров.

Пример 1.2: Сколько четырехзначных чисел можно составить, используя цифры 1,2,3,4,5, если:

а) никакая цифра не повторяется более 1 раза;

б) повторения цифр допустимы.

Решение:

а) Нам надо заполнить 4 места. На первое место можно поставить любую цифру, т.е. существует 5 способов. Затем, так как повторения цифр недопустимы, то на второе место можно поставить любую из 4^х оставшихся цифр, далее, на третье место – любую из 3^х цифр, на четвертое место – одну из 2^х цифр. Таким образом, по принципу произведения мы получим

б) Если повторения цифр допустимы, то на любое место можно поставить любую из данных 5 цифр. Следовательно, можно составить

Ответ: а) 120 чисел. б) 625 чисел.

Типы комбинаций (комбинаторных конфигураций):

1) перестановки

2) размещения

3) сочетания.

§ 2.. Перестановки

Определение 2.1: Перестановкой некоторого количества объектов называется любое размещение этих объектов в строго определенном линейном порядке.

Число всевозможных перестановок определяют по формуле:

,

где , .

Пример 2.1: Сколькими способами можно расставить на полке 3 книги ?

Решение: .

Ответ: 6 способов.

Пример 2.2: Сколькими способами можно раскрасить диаграмму из 4^х столбцов 4^х цветной шариковой ручкой так, чтобы любой столбец был окрашен в определенный цвет?

Решение: .

Ответ: 24 способа.

Перестановки с повторениями

Пусть дано множество из элементов, в котором элементов принадлежат к первому типу, элементов – ко второму типу, элементов принадлежат к третьему типу, и так далее до элементов - ого типа, причем элементы одного и того же типа не различимы между собой. Тогда общее число перестановок равно

.

Пример 2.3: Сколько различных перестановок можно образовать из всех букв слова «Миссисипи»?

Решение: В данном слове 9 букв, в том числе 1 буква «м», 3 буквы «с», 4 буквы «и» и 1 буква «п». Следовательно, n₁ = 1, n₂ = 3, n₃ = 4, n₄ = 1. Тогда общее число перестановок равно

Дата добавления: 2017-01-13