ВУЗ:
Составители:
Рубрика:
3
§ 1. Элементы комбинаторики.
Центральной задачей комбинаторной теории (комбинаторики) можно
считать задачу размещения (распределения) объектов в соответствии со специ-
альными правилами. Если эти правила просты , то основным в этой задаче явля-
ется подсчет числа возможностей для осуществления искомого размещения.
Задачи такого типа принято называть задачами перечисления. Если же правила
распределения объектов сложны , то главной проблемой становится вопрос су-
ществования таких распределений и нахождения методов их осуществления .
Нас будут интересовать только перечислительные задачи. В том случае,
когда интересующих нас вариантов размещения немного, мы можем все эти ва-
рианты перебрать . В других случаях это невозможно из - за большого числа ва-
риантов и тогда на помощь приходят основные правила подсчета : принципы
( правила ) сложения и умножения.
Принцип суммы . Пусть множество А содержит п элементов, а множество
B - k элементов, причем AB
=∅
I . Тогда множество
AB
U
содержит п + k
элементов.
Замечание 1. Если обозначить
A
- число элементов множества А , то в
формализованном виде правило суммы можно сформулировать следующим об -
разом: если
,,,
ABAB
<∞<∞=∅
I то
ABAB
=+
U .
Замечание 2. При решении задач удобной бывает следующая формули-
ровка: элемент из А или элемент из В можно выбрать п + k числом способов, где
п - количество способов выбрать элемент из А , k – элемент из В .
Принцип произведения. Пусть заданы два множества
{
}
1
,...,
n
Aaa
=
и
{
}
1
,...,
k
Bbb
= . Тогда декартово произведение
(
)
{
}
,:,1,...,;,1,...,
ijij
CABabaAinbBjk
=×=∈=∈= содержит
nk
элемен -
тов, т.е.
ABAB
×=⋅
, если
,.
AB
<∞<∞
Подводя итог сказанному, подчеркнем , что если выбирается или то или
другое, то нужно применять правило суммы , а если и то , и другое, то правило
произведения . Например, на тарелке лежат 5 яблок и 3 груши. Если выбираем
яблоко или грушу, то число способов 5+3=8. Если выбираем и яблоко, и грушу,
то 5 • 3 == 15.
Замечание 1. Пусть необходимо выполнить одно за другим какие- то
r
действий (
r
≥
2). Если первое действие можно выполнить
1
n
способами, по-
сле чего второе
2
n
способами, после чего и т.д.
r
- ое действие можно
выполнить
r
n
способами, то все
r
действий можно выполнить
12
...
r
nnn
⋅⋅⋅
спо-
собами.
Замечание 2. Если на выполнение какого-либо из действий наложены ог -
раничения (т.е. некоторое действие необходимо выполнить по- особому, не так ,
как другие), то обычно бывает целесообразно подсчет начинать именно с этого
действия.
Пример. В автомашине семь мест. Сколькими способами семь человек
могут сесть в эту машину, если занять место водителя могут только трое из
них ?
Решение. Для размещения семи человек в автомашине необходимо вы -
3
§ 1. Э лементы к омбинаторик и.
Ц ентральной зад ач ей к омбинаторной теории (к омбинаторик и) мож но
сч итать зад ач у размещ ения (распред еления) объ ек тов в соответствии со специ-
альны ми правилами. Е сли эти правила просты , то основны мвэтой зад ач еявля-
ется под сч ет ч исла возможностей д ля осущ ествления иск омого размещ ения.
Зад ач и так ого типа принято назы вать зад ач ами переч исления. Е сли жеправила
распред еления объ ек тов сложны , то г лавной проблемой становится вопрос су-
щ ествования так их распред елений и нах ожд ения метод ових осущ ествления.
Н ас буд утинтересовать тольк о переч ислительны е зад ач и. В том случ ае,
к огд а интересующ их насвариантовразмещ ения немного, мы можемвсеэти ва-
рианты перебрать. В д ругих случ аях это невозможно из-за больш ог о ч исла ва-
риантови тогд а на помощ ьприх од ятосновны еправила под сч ета: принципы
(правила) сложения и умножения.
Принцип суммы . Пусть множество А сод ержитп элементов, а множество
B - k элементов, прич ем A I B = ∅ . Т огд а множество A U B сод ержитп + k
элементов.
Замеч ание 1. Е сли обознач ить A - ч исло элементов множества А , то в
ф ормализованномвид еправило суммы можно сф ормулировать след ующ имоб-
разом: если A < ∞, B < ∞, A I B = ∅, то A U B = A + B .
Замеч ание 2. При реш ении зад ач уд обной бы ваетслед ующ ая ф ормули-
ровк а: элементиз А или элементиз В мож но вы братьп + k ч исломспособов, гд е
п - к олич ество способоввы братьэлементиз А , k – элементиз В .
Принцип произвед ения. Пусть зад аны д ва множества A = {a1 ,..., an }
иB = {b1 ,..., bk } . Т огд а д ек артово произвед ение
C = A× B = {( a , b ) : a ∈ A,i = 1,..., n; b ∈ B , j = 1,..., k}
i j i j сод ержит nk элемен-
тов, т.е. A × B = A ⋅ B , если A < ∞, B < ∞.
Под вод я итог ск азанному, под ч ерк нем, ч то если вы бирается или то или
д ругое, то нужно применять правило суммы , а если и то, и д ругое, то правило
произвед ения. Н апример, на тарелк е лежат5 яблок и 3 груш и. Е сли вы бираем
яблок о или груш у, то ч исло способов5+3=8. Е сли вы бираеми яблок о, и г руш у,
то 5 • 3 == 15.
Замеч ание 1. Пусть необх од имо вы полнить од но за д руг им к ак ие-то
r д ействий ( r ≥ 2). Е сли первое д ействие можно вы полнить n1 способами, по-
сле ч ег о второе n2 способами, после ч его и т.д . r - ое д ействие мож но
вы полнить nr способами, то все r д ействий можно вы полнить n1 ⋅ n2 ⋅ ... ⋅ nr спо-
собами.
Замеч ание 2. Е сли на вы полнение к ак ог о-либо из д ействий наложены ог-
ранич ения (т.е. нек отороед ействие необх од имо вы полнить по-особому, не так ,
к ак д ругие), то обы ч но бы ваетцелесообразно под сч етнач инать именно с этого
д ействия.
Пример. В автомаш ине семь мест. Ск ольк ими способами семь ч еловек
мог утсесть в эту маш ину, если занять место вод ителя могут тольк о трое из
них ?
Реш ение. Д ля размещ ения семи ч еловек в автомаш ине необх од имо вы -
