Комбинаторная формулировка правила произведения

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

Комбинаторная формулировка правила суммы

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

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

Лекция 3.Основные понятия комбинаторики.

Функциональные отношения

Пусть r Í Х х Y.

Функциональное отношение – бинарное отношение r:

" х Î D_r $! y Î Y: х r y.

Всюду определённое отношение – отношение, у которого D_r = Х ("нет одиноких х ").

Сюръективное отношение – отношение, у которого J_r = Y ("нет одиноких y ").

Инъективное отношение – отношение, в котором разным х соответствуют разные у.

Биекция – функциональное, всюду определённое, инъективное, сюръективное отношение, задаёт взаимно однозначное соответствие множеств.

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

Сформулируем эти правила с точки зрения теории множеств и комбинаторики.

Теоретико – множественная формулировка правила суммы

Пусть A и B – конечные множества и | A | = m; | B | = n; A Ç B=Æ.

Тогда, объединение множеств: A È B содержит m+n элементов.

В общем случае.

Пусть | M₁ | = m₁, | M₂ | = m₂ , …, | M_k | = m_k и M_i Ç M _j = Æ,

" i,j=1.. k, i ¹ j. Тогда, | M | = | M₁ È M₂ È … È M_k | = m₁ + m₂ +…+ m_k.

Если объект a может быть выбран m способами, а объект b – n другими способами, то выбор " a или b " может быть осуществлен m +n способами.

Выбор a и b – взаимоисключающий: выбор a исключает выбор b;

выбор a не совпадает с каким-либо способом выбора b.

В общем случае.

Если объект a₁ может быть выбран m₁ способами; a₂ – m₂ другими cпособами; …; a_k – m_k способами. Выбор " a₁ или a₂… или a_k " может быть осуществлен m₁ + m₂ + … + m _k способами.

Например:

Из Киева в Донецк в течении суток отправляется 3 поезда,

1 самолет и 2 автобуса. Сколько существует способов выехать

из Киева в Донецк?

Решение:

По правилу суммы имеем N= 3+1+2 = 6 способов.

Теоретико – множественная формулировка правила произведения

Если A и B – конечные множества и | A | = m, | B | = n, то мощность множества A ´ B равна m ´ n.

В общем случае.

Если | M₁ | = m₁, | M₂ | = m₂, …, | M_k |=m_k, то | M₁ ´ M₂ ´ … ´ M_k | = m₁ ´ m₂ ´ … ´ m_k.

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

В общем случае.

Пусть объект a₁ может быть выбран m₁ способом, объект a₂ – m₂ способами; объект a_k – m_k способами, причем выбор a₁ не влияет на число способов выбора a₂, …,a_k, выбор a₂ на число способов выбора a₃, …,a_k и т.д_. Тогда, выбор упорядоченного множества объектов (a₁, a₂ …a_k) – в указанном порядке можно осуществить m₁ ´ m₂ ´ _… ´ m_k способами.

Например:

Сколько различных танцующих пар можно составить из 3-х девушек и 2-х юношей?

Решение:

По правилу произведения имеем N= 3´2=6 пар.