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

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

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

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

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

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

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

 

Пусть r Í Хх Y.

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

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

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

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

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

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


 

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

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

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

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

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

 

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

Пусть | M1 | = m1, | M2 | = m2 , … , | Mk | = mkи Mi Ç M j = Æ,

" i,j=1.. k, i ¹ j. Тогда, | M | = | M1 È M2 È … È Mk | = m1 + m2 +…+ mk.

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

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

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

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

Если объект a1 может быть выбран m1 способами; a2m2 другими cпособами; ; ak – mkспособами. Выбор "a1 или a2илиak " может быть осуществлен m1 + m2 + … + m k способами.

Например:

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

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

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

Решение:

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

 

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

 

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

 

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

Если | M1 | = m1, | M2 | = m2, … , | Mk |=mk,то | M1 ´ M2 ´ ´ Mk | = m1´m2´´mk.

 

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

 

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

Пусть объект a1 может быть выбран m1 способом, объект a2 – m2способами; объект ak – mk способами, причем выбор a1не влияет на число способов выбора a2, … ,ak, выборa2на число способов выбора a3, … ,ak и т.д. Тогда, выбор упорядоченного множества объектов (a1, a2 …ak) – в указанном порядке можно осуществить m1´m2´´mkспособами.

Например:

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

Решение:

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