загрузка...
загрузка...
На головну

Комбінаторна формулювання правила твори

правило твори

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

правило суми

Правила суми і твори

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

функціональні відносини

нехай r I Хх Y.

функціональне відношення - Бінарне відношення r:

I Dr $! y I Y: х r y.

Усюди певне ставлення - Відношення, у якого Dr = Х( "Немає одиноких х").

Сюр'ектівное ставлення - Відношення, у якого Jr = Y( "Немає одиноких y").

ін'єкційних ставлення - Відношення, в якому різним хвідповідають різні у.

біекція- Функціональне, усюди певний, ін'єкційних, сюр'ектівное відношення, задає взаємно однозначна відповідність множин.


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

Сформулюємо ці правила з точки зору теорії множин і комбінаторики.

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

нехай A и B- Кінцеві безлічі і | A | = m;| B | = n; A C B = ?.

Тоді, об'єднання множин: A E Bміститьm + n елементів.

У загальному випадку.

нехай | M1 | = m1, | M2 | = m2 , ..., | Mk | = mkи Mi C M j = ?,

"I, j = 1 .. k, i ? j. тоді, | M | = | M1 E M2 E ... E Mk | = m1 + m2 + ... + Mk.

якщо об'єкт a може бути обраний m способами, а об'єкт b - nіншими способами, то вибір "a або b"Може бути здійснений m + n способами.

вибір a и b - Взаємовиключний: вибір a виключає вибір b;

вибір a не збігається з будь-яким способом вибору b.

У загальному випадку.

якщо об'єкт a1 може бути обраний m1 способами; a2 - m2 іншими 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 пар.

Розбиття і покриття безлічі «-- попередня | наступна --» перестановки
загрузка...
© om.net.ua