комбинаторика

Элементы кобинаторики

Изучение теории вероятностей всегда начинается с комбинаторики, ведь именно она составляет начальную базу, необходимую для дальнейшего углубления материала.

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

Правило произведения. Если элемент \bf {x_1} строки (\bf {x_1, x_2, ..., x_k}) можно выбрать \bf {n_1} способами и после каждого такого выбора \bf {x_1} элемент \bf {x_2} можно выбрать \bf {n_2} – способами, и после выбора \bf {x_1} и \bf {x_2} элемент \bf {x_3} можно выбрать \bf {n_3} способами и т.д., наконец, \bf {x_k} независимо от выбора всех предыдущих элементов можно выбрать \bf {n_k} способами. Тогда количество возможностей (комбинаций) образования строки (\bf {x_1, x_2, ..., x_k}) равно: 

\boxed {\bf {N=n_1 \cdot n_2 \cdot n_3 \cdot ... \cdot n_k}} 

ПРИМЕР 1.

Условие: Обед в университетской столовой состоит из трех блюд. Первое блюдо в меню может быть выбрано 5 способами, второе блюдо – 4, а третье блюдо – 3. Сколько дней студент может съедать новый обед, если любая комбинация блюд возможна, и один обед от другого должен отличаться хотя бы одним блюдом?

Решение. При решении данной задачи применим правило произведения (комбинаторика), и учтем, что строка состоит из трех элементов. Первое блюдо (первый элемент строки) можно выбрать пятью различными способами, второе – четырьмя различными способами независимо от выбора первого. Таким образом, первые два блюда можно выбрать \bf {5 \cdot 4} различными комбинациями. Учитывая выбор третьего блюда, окончательно получим: 

\bf {N=3 \cdot 4 \cdot 5=60}

Ответ: 60 дней


Правило суммы. Пусть множество \bf {E_1} содержит \bf {n_1} элемент, множество \bf {E_2 - n_2} элементов, …, и множество \bf {E_k - n_k} элементов. И если эти множества попарно не пересекаются (нет одинаковых элементов), то число элементов в их объединении равно сумме чисел элементов, содержащихся в каждом из этих множеств: 

\boxed {\bf {N=n_1+n_2+n_3+...+n_k}} 

Основные правила комбинаторики

Правило перестановки. Пусть \bf {E^{(n)}=\left\{ {x_1,x_2,...,x_n} \right\}} — произвольное (неупорядоченное) \bf {n} — элементов множество. Рассмотрим различные комбинации его упорядочивания. Получаемые при этом упорядоченные множества отличаются друг от друга только порядком следования входящих в них элементов, и называются перестановками из \bf {n}-элементов. Число всех таких перестановок обозначается символом \bf {P_n} и находится по формуле:

\boxed {\bf {P_n=n!=1 \cdot 2 \cdot 3 \cdot 4 \cdot ... \cdot (n-1) \cdot n}}

ПРИМЕР 2.

Условие: Пятеро гостей случайным образом рассаживаются за столом. Сколькими способами можно их рассадить так, чтобы хотя бы 2 гостя поменялись местами (изменился порядок)?

Решение. При решении данной задачи, учитывая, что за столом всегда сидят все 5 гостей, применим правило перестановки:

N=P_5=5!=1 \cdot 2 \cdot 3 \cdot 4 \cdot 5=120

Ответ: 120 способов


Правило размещения. Различные упорядоченные m – элементные подмножества данного неупорядоченного множества \bf {E^{(n)} (m < n)} называются размещениями из n элементов по m. Число таких размещений обозначается \bf {A_n^m} и вычисляется по формуле:

\boxed {\bf {A_n^m=\frac{n!}{(n-m)!}=n(n-1).....(n-m+1)}}

ПРИМЕР 3.

Условие: Десять участников финала разыгрывают одну золотую, одну серебряную и одну бронзовую медали. Сколькими способами эти награды могут быть распределены между спортсменами?

Решение. Согласно условию данной задачи  награды получат только три финалиста из десяти, а ценность медалей различна, т.е. порядок призеров имеет значение. Тогда для определения числа комбинаций призеров применим правило размещений:

A_{10}^3=\dfrac{10!}{7!}=8 \cdot 9 \cdot 10=720

Ответ: 720 способов


Правило сочетания. Различные неупорядоченные m – элементные подмножества множества \bf {E^{(n)} (m < n)} называются сочетаниями из n элементов по m. Число всех таких сочетаний обозначается символом \bf {C_n^m} и определяется по формуле:

\boxed {\bf {C_n^m=\frac{n!}{m!(n-m)!}}}

ПРИМЕР 4.

Условие: В полуфинальном забеге участвуют десять спортсменов. Три спортсмена, показавшие лучший результат, попадают в финал. Сколько существует различных троек финалистов?

Решение. По условию задачи в финал войдут только три спортсмена из десяти, причем место в призовой тройке не имеет значение. Тогда для определения числа комбинаций призеров применим правило сочетаний:

C_{10}^3=\dfrac{10!}{7! \cdot 3!}=\dfrac{8 \cdot 9 \cdot 10}{1 \cdot 2 \cdot 3}=120

Ответ: 120 троек


Примечания:

Размещения из n-элементов по m представляют собой такие m – элементные выборки из неупорядоченного множества \bf {E^{(n)}}, которые отличаются друг от друга либо самими элементами (хотя бы одним), либо порядком их расположения. Сочетания же из n-элементов по m представляет собой m – элементные выборки, отличающиеся только самими элементами. (редакция)

Правила с повторениями

Правило размещения с повторениями. Любая строка длиной m, составленная из элементов множества \bf {E^{(n)}}, причем элементы в строке могут повторяться, называется размещением с повторением из  n-элементов по m. Число всех размещений с повторениями обозначается символом \bf {\bar {A}_n^m} и вычисляется по формуле:

\boxed {\bf {\bar {A}_n^m=n^m}}          1.7

ПРИМЕР 5. Для автомобильных номеров используются 10 цифр и 28 букв. Каждый номер состоит из 3 букв и 4 цифр. Какое максимальное число машин может получить номера при такой системе нумерации?

Решение. Сначала осуществим выбор 4 цифр. Каждый такой комплект цифр представляет собой четырехэлементную выборку из  10 – элементного массива цифр, т.е. является размещением с повторениями из 10 элементов по 4. Следовательно, общее число таких элементов равно 10^4. Исключим из выборки номер 00-00, если он недопустим. Аналогично выбор трех букв из 28 осуществляется 28^3 числом способов. Так как номер каждой машины есть упорядоченная «пара», состоящая из комплекта цифр и комплекта букв, то по правилу произведения число всех номеров будет равно:

N=(10^4-1)*28^3=219 498 048

Ответ: 219 498 048 машин

Правило сочетания с повторениями. Рассмотрим сочетания из n элементов по m и предположим, что в комбинации возможны повторения. В этом случае выбор элементов комбинации осуществляется не только по одному разу из n элементов, но и еще до (m – 1) раза одного из этих элементов. В этом случае общее число элементов, из которых осуществляется комбинация, следует увеличить до (n+m-1) элементов. Следовательно, число сочетаний из n элементов по m с повторениями определяется по формуле:

\overline {C}_n^m=C_{n+m-1}^m       1.8

ПРИМЕР 6. В цветочном киоске продается 10 наименований цветов. Покупатель желает приобрести букет из 5 цветов. Сколько существует комбинаций таких букетов?

Решение. Очевидно, что цветы одного наименования могут повторяться в букете, и так как порядок цветов в букете не имеет значения, то здесь применима формула числа сочетаний с повторениями:

\overline {C}_{10}^5=C_{10+5-1}^5=C_{14}^5=\frac{14!}{5!*9!}=2002

Ответ: 2002 комбинации

Правило перестановки с повторениями. Рассмотрим перестановки, содержащие одинаковые элементы. Например, в перестановках из n элементов имеются k различных элементов (k < n). При этом первый элемент встречается n_1 раз. Это означает, что общее число перестановок должно быть уменьшено в n_1! раз, так как взаимные перестановки одного и того же элемента равнозначны.

Аналогично происходит и с остальными элементами, которые могут встречаться n_2,n_3,...,n_k раз, причем n_1+n_2+...+n_k=n. Поэтому общее число перестановок с повторениями рассчитывается по формуле:

P_n(n_1;n_2;...;n_k)=\frac{n!}{n_1!*n_2!*...*n_k!}     1.9

ПРИМЕР 7. Имеется шестизначная кодовая комбинация, состоящая из трех цифр 1, 3, 5, в которой цифра 1 встречается один раз, цифра 3 – два раза и цифра 5 – три раза. Сколько существует комбинаций таких наборов?

Решение. В данном случае имеют место перестановки с повторениями. Их число будет равно

P_6(1;2;3)=\frac{6!}{1!*2!*3!}=60

Ответ: 60 комбинаций

Ну что же поздравляю тех терпеливых, которые дошли до сюда. Уверяю вас 90% не дошли, а вы тот самый счастливчик, который вошел в 10%. На этой ноте данную тему считаю законченной. Еще увидимся, Всем спасибо!

Если кто-то не понял или не разобрался в теме или в примерах, задавайте вопросы в комментариях.

Множества. Комбинаторика

Множества

Множество – это любая совокупность объектов, называемых элементами множества.

К примеру, буквами N, Z, Q, R, C обозначаются множества:

N (Naturalis) – натуральные числа;

Z (Zahlen) – целые числа;

Q (Quisque) – рациональные числа;

R (Realis) – действительные числа;

C (Complex) – комплексные числа.

 

a A – объект «а» есть элемент множества А (a принадлежит множеству А)

a А – объект «а» не является элементом множества А

 

Если каждый элемент множества А является элементом множества В, то говорят, что множество А является подмножеством множества В (А содержится в В) и обозначается А ⊂ В.

Если А ⊂ В и В ⊂ А, то множества равны А = В

Пустое множество (∅)не содержит объектов, но имеется в каждом множестве.


 

Операции над множествами

Объединение множеств

 

Множество, которое состоит из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В называется, объединением множества А и В, которое обозначается АВ или А+В.

 

 

Пересечение множеств

 

Множество, которое состоит из элементов, как множества А, так и множества В называется пересечением множества А и В, которое обозначается AB или АВ. Если A∩B = ∅, то значит, что множества не пересекаются.

 

Разность множеств

 

Множество, которое состоит из элементов множества А, но не содержит элементов множества В называется разностью множеств А и В, которое обозначается АВ.

 

 

Если А является подмножеством В (А⊂В), то разность множеств (ВА) называют дополнением множества А до множества В, которое обозначается АB .

Кстати, если рассматривается только одно конкретное подмножество, то чаще всего его просто называют дополнением и обозначают А’.

Отсюда следуют следующие равенства:

А∪А’ = B;     A∩A’ = ∅;   (A’)’ = A

Для любых подмножеств А и В множества U также следуют равенства:

(А∪В)’ = A’∩В’;     (A∩В)’ = А’∪ В’

Данные равенства называют законами двойственности (законы де Моргана).


Упорядоченные множества

Множество называется упорядоченным, если его элементы a и b обладают отношение порядка a ≤ b или b ≤ a, т.е (а не превосходит b или b не превосходит a), а также обладающие следующими свойствами:

  • рефлексивности: (a ≤ a), т. е. ни один из элементов не превосходит самого себя;
  • ассиметричности если (a ≤ b и b ≤ a), то элементы a и b равны;
  • транзитивности: если a ≤ b, а b ≤ c, то и a ≤ c.

 

Размещения и перестановки

Пусть имеется множество, состоящее из n-элементов. Каждое его упорядоченное подмножество, состоящее из k-элементов называется размещением из n-элементов по k-элементов.

Обозначается число размещений: A_n^k

Формула вычисления числа размещений: A_n^k = n(n-1)(n-2)...(n-(k-1)).

Размещением из n-элементов по n-элементов называют перестановками из n-элементов.

Обозначается число перестановок: P_n

Формула вычисления числа перестановок: P_n = P! = 1*2*3*...*n.

 

Пример №1

Задача: группа студентов изучает восемь учебных дисциплин. Сколькими способами можно составить расписание занятий на понедельник, состоящее из трех предметов.

И вот она, наша первая задачка.

Решается тут все довольно просто, главное правильно определить, где у нас множество, а где подмножество.

В данном случае, множество — это общее количество учебных дисциплин, а подмножество — это количество предметов в понедельник. Подмножества у нас упорядоченные, т.к. их количество меньше, чем количество множеств, поэтому используем формулу для вычисления числа размещений.

Итак, n — общее количество дисциплин (8), а k — количество предметов в понедельник (3).

A_8^3 = 8(8-1)(8-2) = 8*7*6 = 336

Ответ: существует 336 способа составления расписания.

Пример №2

Сколько шестизначных чисел, кратных пяти можно составить из чисел: 1, 2, 3, 4, 5, 6, но при условии что в числе цифры не повторяются!

Все мы прекрасно знаем, еще со школьной скамьи, что числа кратные пяти должны иметь последнюю цифру либо 0, либо 5. В нашем ряду нуля нет, а значит использовать можно только цифру пять, а остальные пять цифр могут стоять в любом порядке.

И чтобы найти количество шестизначных чисел кратных пяти, нужно найти число перестановок из пяти элементов, т.е. вычислить 5! = 1*2*3*4*5 = 120

Ответ: Из данных чисел можно составить 120 шестизначных чисел, кратных пяти.


 

Сочетания

Пусть имеется множество, состоящее из n-элементов. Каждое его подмножество, состоящее из k-элементов называется сочетанием из n-элементов по k-элементов. (не путайте с размещением).

Число всех сочетаний обозначается: C_n^k

Вычисляется число сочетаний по формуле: C_n^k = frac{n!}{k!(n-k)!}

Также число сочетаний можно вычислить и по другой формуле: C_n^k = frac{n(n-1)(n-2)...(n-(k-1))}{k!}

Пример №3

Проходит чемпионат страны по футболу (высшая лига), в котором участвуют 18 команд. Каждые две команды встречаются между собой дважды. Определить общее количество матчей в сезоне.

На самом деле, чтобы решить данную задачку можно прибегнуть к маленькой хитрости, а именно если всего команд 18 и каждые две играют между собой по два раза, то общее количество игр в сезоне можно найти перемножив общее количество команд (18) на общее количество команд минус 1 (18-1 = 17). В итоге 18*17 = 306 матчей.

Но комбинаторика советует все таки действовать по правилам и решить нашу задачу по формуле сочетания чисел, где n = 18 (равно количеству команд), а k = 2 (количество игр каждой команды с другой).

Итак, C^2_{18}= frac{18!}{2!(18-2)!} = frac{18!}{2!*16!} = frac{17*18}{1*2} = 153

Получилось не совсем то, что мы ожидали — правда?

Нет, мы решили все правильно) Просто мы нашли количество матчей в первом круге сезона (т.е. каждые команды сыграли между собой по одному разу), а так как во втором круге играется  ровно столько же матчей, то сложив их получим 153+153 = 306 матчей. Задача решена))

Ответ: в течение всего сезона будет сыграно 306 матчей.

Решим еще несколько примеров, в качестве закрепления

ПРИМЕР №4 Никакие три диагонали выпуклого десятиугольника не пересекаются в одной точке. Определить число точек пересечения диагоналей.

C^4_{10} = frac{10!}{4!-(10-4)!} = frac{7*8*9*10}{1*2*3*4} = frac{5040}{24} = 210

Можно перепроверить другим способом: число точек пересечения диагоналей выпуклого n-угольника, лежащих внутри этого многоугольника можно найти по формуле: frac{1}{24}*(n*(n-1)(n-2)(n-3))

Посчитаем для нашего случая: 10*9*8*7:24 = 210

Ответ: 210 точек

ПРИМЕР №5 Сколько различных десятизначных чисел можно записать, используя только цифры 1 и 2.

Если число, записанное единицами и двойками, содержит десять цифр, то таких чисел будет: A_2^{10} = 2^{10} = 1024

Ответ: 1024 числа

ПРИМЕР №6 Сколькими способами можно упаковать 9 разных книг в 5 бандеролей, если 4 бандероли должны содержать по 2 книги.

  1. выбираем книгу в маленькую бандероль — 9 способов;
  2.  из оставшихся 8 выбираем пару книг в первую бандероль 8*7, причем так как у нас получается дублирующие случаи (сначала берем 1, потом 3 или сначала 3, потом 1 книги) , делим пополам;
  3.  аналогично заполняем третью, четвертую и пятую бандероли.

В итоге получаем:

frac{C_9^2*C_7^2*C_5^2*C_3^2*C_1^1}{4!} = frac{22680}{24} = 945

Ответ: 945 способов.

 

Спасибо за внимание, я надеюсь все разобрались с данной темой.

Если вам что-то непонятно (или нашли неточности в уроке) пишите в комментариях и мы вам обязательно ответим в ближайшее время.