Основные законы комбинаторики

2.1. Основные законы комбинаторики.

2.1.1. Правило суммы.

Задача: на блюде лежат 5 яблок и 2 груши. Сколькими способами можно выбрать один плод?

Решение: плод можно выбрать семью способами (5+2=7).

Если некоторый элемент a может быть выбран из множества элементов m способами, а другой элемент b может быть выбран n способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно m + n способами.

На языке теории множеств это правило формулируется следующим образом:

Теорема1: если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.

АВ =   | АВ | = |A| + |B|

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

Рекомендуемые материалы

Теорема2: для любых конечных множеств верно равенство:

| АВ | = |A| + |B| - | АВ |.

Задача: среди студентов первого курса 30 человек имеют дома компьютер, 35 – учебник по информатике; оказалось, что 10 студентов имеют и компьютер, и учебник по информатике. Сколько студентов на первом курсе?

Решение: пусть множество А составляют студенты, имеющие компьютер, множество В – студенты, имеющие учебник по информатике; по условию задачи:

|A| = 30                  |B| = 35                       | АВ | = 10             | АВ |  =?

| АВ | = |A| + |B| - | АВ | = 30 + 35 – 10 = 55.

2.1.2. Правило произведения.

Вторым основным правилом комбинаторики является правило произведения.

Задача: определить количество клеток в игре «морской бой», если номер клетки состоит из буквы (букв 10) и цифры (цифр тоже 10).

Решение: количество клеток равно 10•10=100.

Если элемент a можно выбрать из множества элементов m способами и после каждого такого выбора элемент b можно выбрать n способами, то два элемента (упорядоченную пару) a и b можно выбрать m•n способами.

На языке множеств это правило выражается в виде следующей теоремы.

"Часть 39" - тут тоже много полезного для Вас.

Теорема3: если множества А и В конечны, то |AB| = |A| • |B|.

Следствие: если множества А₁, А₂, …, А_n  - конечны, то

|A₁…А_n| = |A₁|• … •|A_n|.

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

Решение: обозначим множество букв А, множество цифр – В; каждый номер требуемого вида является набором длины n из декартова произведения ААВВВ; по условию |А| = 29, |В| = 10, тогда по следствию из теоремы3 имеем:

| ААВВВ | = 29•29•10•10•10 = 841 000.