2. Основное комбинаторное правило (частный случай)

В самых разных ситуациях возникает задача подсчета количества элементов множества, заданного теми или иными условиями. Например, в такой.

Пример 1. Имеется 4 вида почтовых конвертов без марок и 3 вида марок. Сколько всего способов составления конвертов с одной маркой?

Пронумеруем марки – 1,2,3, конверты - 1,2,3,4. Конверты с маркой обозначим (номер марки, номер конверта), например, (1,3) означает «на конверт с номером 3 приклеена марка под номером 1».

Составим из этих пар прямоугольную таблицу, содержащую 3 строки и 4 столбца:

Здесь в первой строке последовательно выписаны все конверты с наклеенной маркой под номером 1, во второй и третьей строках – соответственно марки под номерами 2 и 3.

Каждый возможный конверт с наклеенной одной маркой в этой таблице встречается один и только один раз. Поэтому искомое число конвертов с маркой равно числу пар прямоугольной таблицы из 3 строк и 4 столбцов, т.е. 3х4=12.

Итак, если марка выбирается n=3 способами, а конверт – m=4 способами, то число всевозможных разных пар (марка, конверт) равно .

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

Поэтому имеет место утверждение называемое основным комбинаторным правилом.

Основное комбинаторное правило (случай пар). Из n предметов (элементов) a₁,…,a_n и из m предметов (элементов) b₁,…,b_m можно образовать ровно m n различных пар (a_i, b_j), где первый a_i элемент взят из первой группы, второй элемент b_j - из второй группы.

Для доказательства составим из этих пар прямоугольную таблицу, содержащую n строк и m столбцов так, чтобы пара (a_i, b_j) находилась на пересечении i-ой строки и j-го столбца:

			j-ый столбец
	(a1,b1)	(a1,b2) . . .	(a1,bj)	. . .	(a1,bm)
	(a2,b1)	(a2,b2) . . .	(a2,bj)	. . .	(a2,bm)
i-ая строка	(ai,b1)	(ai,b2) . . .	(ai,bj)	. . .	(ai,bm)
	(an-1,b1)	(an-1,b2) . . .	(an-1,bj)	. . .	(an-1,bm)
	(an,b1)	(an,b2) . . .	(an,bj)	. . .	(an,bm).

Каждая пара в этой таблице имеет свое единственное место, поэтому число всевозможных пар равно числу элементов таблицы, т.е. числу .

Примеры. а) Карты для игры в бридж. За множества элементов примем соответственно четыре масти и 13 возможных значений карты. Каждая карта определяется мастью и значением. Существует 4 • 13=52 таких комбинаций масти и значения. Это – число карт в колоде.

б) Многоярусные электрические лампы с несколькими способами включения содержат три обычные лампочки и светящую арматуру, которая может работать в трех положениях или может быть выключена. Каждая из этих возможностей комбинируется с 0, 1, 2, 3 включенными лампочками. Следовательно, всего имеется 4 • 4 = 16 возможных комбинаций, из которых одна (0, 0) означает, что лампа не светит. Остается 15 способов включения лампы.