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

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

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

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

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

Лекция 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 пар.