Файл: Учебник по информатике оказалось, что 14 студентов имеют и ноутбук, и учебник по информатике. Сколько студентов на первом курсе.pdf

Т е м а 3. КОМБИНАТОРИКА
Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами. Она имеет широкий круг приложений: теория вероятностей, теория информации, теория надежности, алгебраическая топология, алгебра и математический анализ. Термин «комбинаторика» был введен в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».
3.1. Основные законы комбинаторики
Правило суммы.
Если некоторый элемент a может быть выбран из множества элементов m способами, а другой элемент b может быть выбран n способами, причем любой выбор элемента b отличен от любого выбора элемента a, то выбрать либо a, либо b можно m + n способами.
На языке теории множеств это правило формулируется следующим образом: если пересечение конечных множеств пусто, то число элементов в их объединении равно сумме чисел элементов множеств А и В.
А ∩В = ∅⇒ |А U В| = |A| + |B|.
Замечание. Важно, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь n+m-r способов выбора, где r – число совпадений.
Соответственно, обобщенное правило суммы принимает вид: |АUВ| = |A|
+ |B| - |A∩B|.
Пример 3.1. Среди студентов первого курса 40 человек имеют дома ноутбук, 25 – учебник по информатике; оказалось, что 14 студентов имеют и ноутбук, и учебник по информатике. Сколько студентов на первом курсе?
Решение. Пусть множество А составляют студенты, имеющие ноутбук, множество В – студенты, имеющие учебник по информатике; по условию задачи: |A| = 40 |B| = 25 |А∩В| = 14 |А ∪ В| =?
|А∪ В| = |A| + |B| – |А∩В| = 40 + 25 – 14 = 51.
Правило суммы в общем случае: пусть имеется n попарно непересекающихся множеств X
1
, X
2
, …, X
n
, содержащих m
1
, m
2
, …, m n
элементов соответственно. Число способов, которыми можно выбрать один элемент из всех этих множеств, равно m
1
+ m
2
+ … + m n
. Тогда
- это правило суммы или правило альтернатив.

Правило произведения.
Если элемент a можно выбрать из множества элементов m способами и после каждого такого выбора элемент b можно выбрать n способами, то два элемента (упорядоченную пару) a и b можно выбрать m·n способами.
На языке множеств это правило выражается в виде следующей теоремы: если множества А и В конечны, то |A×B| = |A| · |B|.
Пример 3.2. Сколько номеров, состоящих из двух букв, за которыми идут три цифры можно составить, если использовать 29 букв и 10 цифр.
Решение. Обозначим множество букв А, множество цифр – В; каждый номер требуемого вида является набором длины n из декартова произведения
А×А×В×В×В; по условию |А| = 29, |В| = 10, тогда имеем:|А×А×В×В×В| =
29·29·10·10·10 = 841 000.
Пример 3.3. В вычислительной технике используются тристабильные элементы, выходы которых имеют два состояния 0, 1 и третье состояние
(высокоимпедансное), обозначаемое цифрой 2. Сколько существует различных состояний, в которых может находиться устройство, содержащее два таких элемента?
Решение. Каждый элемент имеет три состояния, значит по теореме умножения, устройство с двумя такими элементами имеет 3 × 3 = 9 состояний.
Общая формулировка правила произведения.
По индукции правило умножения можно распространить на любое число сомножителей в декартовом произведении:
|X
1
× X
2
×…× X
n
| = |X
1
| · |X
2
| · … · |X
n
|
Наиболее часто последнее равенство применяется, когда X
1
= X
2
=…= X
n
=X
Тогда: |X
n
| = |X|
n
В этом случае множество X называют алфавитом, его элементы – буквами, а элементы декартова произведения X
n
– словами в алфавите X. Слова записывают как в обычном языке, то есть без разделения букв запятыми и без внешних скобок: x
1
x
2
…x n
. Число n при этом называют длиной слова.
Если |X|=m, то последнее правило можно сформулировать на языке
«алфафита» следующим образом: число слов длины n в алфавите из m букв равно m n
Пусть требуется выполнить одно за другим к действий, причем первое действие может быть выполнено n
1
способами, 2-е действие n
2
способами, 3-е действие n
3
способами и так далее, k-е действие n k
способами.
Тогда все k действий могут быть выполнены P
k
= n
1
× n
2
×…× n k способами.
Пример 3.4. Из 80 студентов 40 играют в футбол, а 50 – в волейбол, причем 27 студентов играют и в футбол и в волейбол. Сколько студентов играют хотя бы в одну из этих игр? Сколько студентов играют лишь в одну из этих игр? Сколько студентов не играют ни в одну из этих игр?

Решение. Пусть X – множество студентов, играющих в футбол, Y – множество студентов, играющих в волейбол. Тогда |X|=40, |Y|=50, |X∩Y|=27.
Число студентов, играющих хотя бы в одну из этих игр, соответственно:
|X∪Y|=40+50-27=63. Число студентов, играющих только в футбол: |X|-|X∩Y|, а только в волейбол: |Y|-|X∩Y|. Значит, число студентов, играющих только в одну из этих игр: |X|+|Y|-2|X∩Y|=40+50-2*27=36. Число студентов, не играющих ни в одну из этих игр: |????⋃????|=80-63=17.

Пример 3.5. Сколько существует 6-значных телефонных номеров?
Решение. Алфавит состоит из 10 цифр, номер – слово длины 6 в этом алфавите. Поэтому количество номеров равно 10 6
Пример 3.6. Найти число слов, содержащих 4 буквы, в которых любые две соседние буквы различны (число букв в алфавите равно 33).
Решение. Первую букву можно выбрать 33-мя способами, вторую, третью и четвертую – 32-мя способами. Число слов тогда равно: 33∙32 3
=1081344.
Правило биекции.
Это правило, которое называется также принципом взаимно однозначного соответствия, формулируется следующим образом: если между множествами X и Y можно установить взаимно однозначное соответствие (биекцию), то |X|=|Y|.
В качестве примера применения этого принципа найдем мощность множества всех подмножеств данного множества X. Такое множество называют булеаном множества X и обозначают символом B(X).
Пусть X – n-множество. Так как мощность множества не зависит от природы его элементов, то можно принять X={1, 2, …, n}.
Поставим в соответствие произвольному подмножеству Y⊆X двоичное слово a
1
a
2
…a n
по следующему правилу: a
i
=
1, ???? ∈ ????
0, ???? ∉ ????
, i = 1, 2, …, n
Это соответствие взаимно однозначное. Отсюда следует, что число всех подмножеств n-множества равно числу двоичных слов длины n, то есть:
|B(X)|=2
n
Метод включений-исключений.
Поставим задачу подсчитать количество элементов в объединении конечных множеств X
1
, X
2
, …, X
m
, которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением.
Для двух множеств мы имеем обобщенную формулу, следующую из правила суммы: |X
1
UX
2
| = |X
1
| + |X
2
| - |X
1
∩X
2
|. Обозначим: X
1
∪X
2
=X и применим эту же формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств:
|X
1
UX
2
UX
3
| = |XUX
3
| = |X| + |X
3
| - |X∩X
3
| = |X
1
∪X
2
| + |X
3
| - |(X
1
∪X
2
)∩X
3
| =
=|X
1
| + |X
2
| - |X
1
∩X
2
| + |X
3
| - |(X
1
∩X
3
)U(X
2
∩X
3
)| = |X
1
| + |X
2
| + |X
3
| - |X
1
∩X
2
| -
|X
1
∩X
3
| - |X
2
∩X
3
| + |X
1
∩X
2
∩X
3
|

В результате по индукции получаем формулу включений-исключений:
|X
1
U X
2
U…U X
m
| = |⋃
????
i
| = ∑
| ????
i
| - ∑
|X
i1
∩ X
i2
| + … +
+ (-1)
k+1
∑
|X
i1
∩ … ∩ X
ik
| + … + (-1)
m+1
|X
1
∩ X
2
∩ … ∩ X
m
|
Название этой формулы подчеркивает использование последовательных включений и исключений элементов подмножеств.
Часто эту формулу записывают в другом виде. Рассмотрим некоторое N- множество элементов Y и m-множество свойств P={p
1
, p
2
, … , p m
}, которыми элементы могут обладать или не обладать. Пусть подмножество X
i
 Y состоит из элементов, обладающих свойством p i
, i=1,..,m. Тогда подмножество объединяет элементы из Y, которые обладают хотя бы одним из свойств множества P. Дополнение ???? составляют элементы, которые не обладают ни одним из свойств p i
, i=1,..,m. Пересечения вида объединяют элементы, обладающие одновременно свойствами p i1
,…,p ik
. Если обозначить число таких элементов через N(p i1
,…,p ik)
, то для числа элементов множества ???? имеем формулу обращения:
Использование полученной формулы в комбинаторике называют методом включений и исключений.

Пример 3.7. Рассмотрим слова длины n в алфавите {0, 1, 2}. Сколько имеется слов, в которых встречаются все три цифры?
Решение. Обозначим через X
i множество всех слов, в которых не встречается цифра i, i=0,1,2. Тогда |X
0
|=|X
1
|=|X
2
|=2
n
. Кроме того, |X
0
∩X
1
| =
|X
0
∩X
2
| = |X
1
∩X
2
| = 1. Наконец, |X
0
∩X
1
∩X
2
|=0. В множество X
0
U X
1
U X
2
входят слова, в которых отсутствует хотя бы одна цифра. По формуле включений-исключений: |X
0
U X
1
U X
2
| = 2
n
+ 2
n
+ 2
n
– 1 – 1 – 1 + 0 = 3 · (2
n
– 1).
Тогда по формуле обращения число слов, в которых присутствуют все три цифры, равно: 3
n
– 3 · (2
n
– 1).
3.2. Комбинаторные конфигурации
Комбинаторика, комбинаторный анализ – раздел математики, в котором рассматриваются подмножества конечных множеств.
Подмножества определенного вида называются комбинаторными конфигурациями. Подсчет количества комбинаторных конфигураций (комбинаторных чисел) составляет суть перечислительных задач комбинаторного анализа. Такие задачи приходится решать, как части более сложных задач дискретной математики.
Многообразие таких задач не всегда удается описать с помощью математических формул. Однако для стандартных распространенных ситуаций

способы подсчета определены.
Все комбинаторные конфигурации представлены в таблице.
№
Теоретико- множественный язык
Комбинаторно- вероятностный язык
Формулы

1 Сколько различных упорядоченных k- подмножеств можно образовать из элементов некоторого n- подмножества?
Сколькими способами можно выбрать и разместить по k различным местам k из n различных предметов?

2 Сколько различных упорядоченных множеств можно составить, используя каждый раз все элементы некоторого n- множества?
Сколькими способами можно расставить n различных предметов по n различным местам?

3 Сколько различных k- подмножеств можно составить из элементов некоторого n-множества?
Сколькими способами можно выбрать k из n различных предметов?

4 Сколько k- последовательностей можно составить из элементов некоторого n- множества?
Сколько слов определенной длины можно составить из букв данного алфавита?
5 Сколько существует последовательностей, состоящих из одних и тех же элементов, каждый из которых входит в любую из этих последовательностей одно и тоже (но для каждого предмета свое) число раз?
Сколько существует перестановок длины n, состоящих из m различных элементов, причем первый с кратностью k
1
, второй – k
2

и т.д.?
6 Пусть A = A
1
∪ A
2
∪ ... ∪
A
n
- разбиение множества
А. Сколько существует различных k-подмножеств множества
А, если элементы принадлежащие одному и тому же классу разбиения считаются неразличимыми

(одинаковыми)?
Имеется неограниченное число предметов n видов и из них составляются наборы по k предметов, причем
2 набора считаются равными, если они имеют одинаковый состав.

Сколько таких наборов можно составить?

Определить вид комбинаторной конфигурации можно по следующей схеме:
Выборки. Если из множества предметов выбирается некоторое подмножество, то его называют выборкой. Выборки бывают упорядоченные и неупорядоченные. В выборках могут допускаться и не допускаться повторения элементов, т.е. имеются выборки с повторением и выборки без повторений.
В упорядоченной выборке существенен порядок, в котором следуют ее элементы, другими словами, изменив порядок элементов, мы получим другую выборку.
3.2.1. Перестановки
Перестановки без повторений.
Различные упорядоченные кортежи, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества), называются перестановками без повторений из n элементов.
Возьмем n различных элементов a
1
, a
2
, a
3
, … a n
; будем переставлять эти элементы всевозможными способами, оставляя без изменения число элементов и меняя только порядок их расположения.
Обозначим общее число полученных таким образом перестановок P(n).
P – первая буква французского слова permutation – перестановка.
Составив таблицу перестановок для n элементов и применив (n - 1) раз правило произведения, получим число всех возможных перестановок:
P(n) = n • (n -1) • (n - 2) • … • 3 • 2 • 1 = n!
Такие перестановки называются перестановками без повторений (один и тот же элемент не может повториться в комбинации, все элементы различны). нет нет нет нет нет да да да да да
Составить несколько комбинаций (выборок)

Повторяются ли элементы в выборке?
Меняется ли состав?

Меняется ли состав?
Существенен ли порядок?
Перестановки с повторениями
Перестановки

Существенен ли порядок?
Размещения с повторениями
Сочетания с повторениями
Сочетания
Размещения

Пример 3.8. Шесть человек могут в разном порядке сесть за круглый стол, сколько существует способов разместить эти шесть человек за столом?
Решение. Так как все люди различны и их комбинации различаются только порядком следования, то мы имеем перестановки без повторений.
Определим их число:
Р(6) = 6! = 1 • 2 • 3 • 4 • 5 • 6 = 720.
Пример 3.9. Сколькими способами можно упорядочить множество

{1,2,3,….,2n} так, чтобы каждое четное число имело четный номер?
Решение. Четные числа можно расставить на местах с четными номерами
(таких мест n) n! способами, каждому способу размещения четных чисел на местах с четными номерами соответствует n! способов размещения нечетных чисел на местах с нечетными номерами. Поэтому общее число перестановок указанного типа по правилу умножения равно n!×n!.

Пример 3.10. Сколько можно составить перестановок из n элементов, в которых данные два элемента не стоят рядом?
Решение. Определим число перестановок, в которых данные два элемента а и b стоят рядом. Могут быть следующие случаи: а стоит на первом месте, а стоит на втором месте, …, а стоит на n-1 месте, а b стоит правее а, число таких случаев равно n-1. Кроме того, а и b можно было поменять местами, и, следовательно, существует 2(n-1) способов размещения а и b рядом. Каждому из этих способов соответствует (n-2)! перестановок других элементов.
Следовательно, число перестановок, где а и b стоят рядом, равно 2(n-1)(n-
2)!=2(n-1)!. Поэтому искомое число перестановок равно n!-2(n-1)!= (n-1)!(n-2).

Пример 3.11. (хоровод) Семь девушек водят хоровод. Сколькими различными способами они могут встать в круг?
Решение. Если бы девушки стояли на месте, то получилось бы 7!=5040 перестановок. Но так как танцующие кружатся, то их положение относительно окружающих предметов не существенно, а важно лишь взаимное расположение. Поэтому перестановки, переходящие друг в друга при кружении танцовщиц надо считать одинаковыми, например: (1,2,3,4,5,6,7) и (7,1,2,3,4,5,6).
Но из каждой перестановки можно получить еще шесть новых путем вращения.
Значит, число 5040 надо разделить на 7. Получаем 5040/7=720 различных перестановок девушек в хороводе.
Вообще, если рассматривать перестановки n предметов, расположенных не в ряд, а по кругу, и считать одинаковыми расположения, переходящие друг в друга при вращении, то число различных перестановок равно (n-1)!.
А теперь сосчитаем, сколько ожерелий можно составить из 7 различных бусин. По аналогии с только что решенной задачей можно подумать, что число различных ожерелий равно 720. Но ожерелье можно не только повернуть по кругу, но и перевернуть. Поэтому ответом на эту задачу является 720/2=360.
Перестановки с повторениями.
Рассматривая различные перестановки, мы предполагали, что все n элементов различны. Если же некоторые элементы повторяются, то в этом