Правило суммы. Правило произведения

На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, располагать элементы одного или нескольких множеств в определенном порядке, т.е. решать задачи, в которых речь идет о тех или иных комбинациях объектов. Такие задачи называются комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называют комбинаторикой. Комбинаторика связана с теорией конечных множеств. Условимся обозначать число элементов произвольного конечного множества Х символом n (X). Например, для множества Х = { а, в, с } n (X) = 3, и множество Х можно назвать трехэлементным. Если конечное множество состоит из т элементов, его можно назвать т элементным множеством.

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

Правило суммы. Если множество X состоит из k элементов, а множество Y из т элементов и = Æ, то состоит из k + т элементов, т.е.

n () = п (Х) + n (Y) = k + т.

(Напомним, что п (Х) – обозначение числа элементов в множестве X). Это очевидное утверждение и называют правилом суммы, его формулируют так.

Если элемент х можно выбрать k способами, а элемент у можно выбрать т способами, причем любой способ выбора х отличается от способа выбора у, то выбор либо х, либо у можно сделать (k + т) способами.

Например, если на тарелке лежат 8 яблок и 6 груш, то один плод можно выбрать 8 + 6 = 14 способами.

Если ¹Æ, то n ()= п (Х) + n (Y) – п ().

Если = Æ при i ¹ j, i, j = 1, 2,..., q, то

.

Правило произведения. Если множество X состоит из k элементов, а множество Y состоит из т элементов, то множество X ´ Y состоит из k · т элементов, т.е.

n (X ´ Y) = п (Х) · n (Y) = k · т.

Это очевидное утверждение называют правилом произведения, его формулируют так.

Если элемент х можно выбрать k способами, а элемент у можно выбрать т способами, то пару (х, у) можно выбрать k · т способами.

Это правило можно обобщить (с помощью метода математической индукции) на случай произведения нескольких множеств:

.

Дата добавления: 2015-07-18