Общие правила комбинаторики. Прямое произведение множеств и правило произведения.

Комбинаторика−это наука о конечных множествах. Мы будем изучать лишь ту ее часть, в которой нужно найти число элементов множества, которое получается из других конечных множеств с помощью специальных операций.

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

Ясно, что и всегда . Изучим некоторые свойства меры , введенной для любого конечного множества .

Свойство 2.1( правило суммы или свойство конечной аддитивности меры ). Верны утверждения:

1)если , то ;

2)если , и , то ;

3)если , ,

то .

 

Свойство 2.2( правило объединения).

Верны утверждения:

1) ;

2) .

Свойство 2.3( правило разности).

Верны утверждения:

1) ;

2) ;

3) если , то .

Свойство 2.4 ( свойство монотонности меры ).

если , то .

Свойство 2.5 (правило произведения).

Верны утверждения:

1) ;

2) .

Пример 2.1 (задача о значках). Пусть имеются три набора (множества) объектов:

множество математических символов;

множество букв;

множество красок.

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

Решение.

Способ 1. На математический символ наклеивают букву и получают новую заготовку. Число новых заготовок равно, очевидно, числу клеток таблицы и равно 12. Новую заготовку окрашивают и получают значок. Число значков равно, очевидно, числу клеток таблицы и равно 48.

Способ 2. Пусть множество значков. Ясно, что . По правилу произведения .

Способ 3. По правилу произведения число разных значков равно .

На практике решение задач похожих на задачу о значках обычно оформляется так, как показано в способе 3.

 

Размещения без повторений. Размещения с повторениями. Перестановки без повторений. Перестановки с повторениями.

Размещения без повторений.

Предположим, что в урне лежат разных объектов, которых будем называть буквами. Из этой урны без возвращения вытаскиваем последовательно букв. Получается слово длины , если буква, появившаяся при вытаскивании с номером , вставляется в это слово на место с таким же номером . Полученное слово называется размещением без повторений из элементов по элементов.

число всех размещений без повторений из элементов по элементов,

где , , , , …, (читается: эн факториал). Если , то получается одно пустое слово и .

Пример 3.1. Пусть , и в урне лежат три буквы . Найти .

Решение.

1)Нахождение с помощью явного указания всех размещений из элементов по элемента: ; .

2) .

Размещения с повторениями.

Предположим, что в урне лежат разных объектов, которых будем называть буквами. Из этой урны с возвращением вытаскиваем последовательно букв. Получается слово длины , если буква, появившаяся при вытаскивании с номером , вставляется в это слово на место с таким же номером . Полученное слово называется размещением с повторением из элементов по элементов.

число всех размещений с повторениями из элементов по элементов.

Если , то получается одно пустое слово и .

Пример 3.2. Пусть , и в урне лежат три буквы . Найти .

Решение.

1)Нахождение с помощью явного указания всех размещений из элементов по элемента: ; .

2) .