1.03. Некоторые сведения из комбинаторики

Комбинаторика - это часть так называемой Дискретной математики, изучающая разнообразные соединения элементов. Под элементами понимаются любые однотипные вещи: предметы, буквы, числа, живые существа и т. д. Различают 3 вида соединений элементов:

· Размещения;

· Перестановки;

· Сочетания.

1. Размещения. Пусть рассматривается совокупность из N упорядоченных, т. е. пронумерованных, элементов (A1; A2;…An). Будет составлять из этих N элементов всевозможные Упорядоченные группы По M элементов в каждой группе, где M – любое натуральное число, не превосходящее N. Эти группы будем считать различными, если они отличаются друг от друга хотя бы одним элементом или даже только порядком следования элементов в группе (у каждого элемента в упорядоченной группе есть свое учитываемое место). Такие группы называются Размещениями из N элементов по M элементов в каждом размещении. Их общее число обозначается символом , и находится оно по формуле:

= (2.1)

Напомним, что выражение N! Называется эн–факториал, и определяется оно так:

0!=1; 1!=1; 2!= 1·2=2; 3!=1·2·3=6; 4!=1·2·3·4=24;… N!= 1·2·3···N. (2.2)

Доказательство формулы (2.1).

1) Составим сначала все возможные размещения из N Элементов (A1; A2;…An) по одному элементу в каждом размещении и подсчитаем их число . Эти размещения – просто отдельно взятые элементы A1; A2;…An. Их количество равно N. То есть

=N (2.3)

2) Составим теперь все возможные размещения из N элементов по два элемента в каждом размещении и подсчитаем их число . Эти размещения тоже очевидны:

A1 a2 a2 a1 a3 a1 an a1

A1 a3 a2 a3 a3 a2 an a2

A1 a4 a2 a4 a3 a4 an a3 (2.4)

…… …… …… ……

A1 an a2 an a3 an an an-1

В каждом из столбцов (2.4) N -1 размещение, а всех столбцов N, поэтому

=N(N-1) (2.5)

3) Составим все возможные размещения из N элементов по три элемента в каждом размещении и подсчитаем их число . Эти размещения получим, если возьмем за основу все возможные размещения (2.4) по два элемента и добавим по очереди справа к каждому из них любой из оставшихся N-2 элементов. Таким образом, из каждого размещения (2.4) по два элемента можно образовать N-2 размещения по три элемента. Например, из одного размещение A1 A2 , содержащего два элемента, можно образовать следующее N-2 размещений по три элемента:

A1 a2 a3 ; a1 a2 a4; a1 a2 a5;……… a1 a2 an (2.6)

Следовательно,

=· (N-2)=N(N-1)(N-2) (2.7)

Аналогично:

= · (N-3)=N(N-1)(N-2)(N-3) (2.8)

= · (N-4)=N(N-1)(N-2)(N-3)(N-4)

………………………………………

То есть

= N(N-1)(N-2)(N-3)…..(N-M+1) (2.9)

Итак, мы получили формулу для при произвольном M (M=1,2,…N).

Преобразуем ее к более удобному виду. Для этого домножим и разделим выражение (2.9) на убывающие недостающие множители (N-M)(N-M-1)····3·2·1 так, чтобы последний множитель в (2.9) стал 1:

==

==

Формула (2.1) доказана.

Для примера подсчитаем общее количество всех возможныхРазмещений из трех элементов (A1; A2; A3) по одному, по два и по три элемента. Причем сделаем это и непосредственно, составив все эти размещения и пересчитав их, и по формуле (2.1):

=3; =6; =6 (2.11)

Эти же результаты дает и формула (2.1):

==; =; = (2.12)

2. Перестановки. Перестановками из данной совокупности N Элементов (A1; A2;…An) называются различным образом упорядоченные (по разному переставленные) комбинации всех этих элементов. Их общее количество обозначается символом . Так как перестановки – это по сути размещения из N элементов по N элементов в каждом размещении, то

(2.13)

3. Сочетания. Сочетаниями из N элементов по M Элементов в каждом сочетании называются (в отличие от размещений) всевозможные Неупорядоченные группы по M элементов в каждой группе. Неупорядоченные - это значит, что важно, какие элементы содержатся в каждом сочетании, а каком порядке они там находятся – это неважно. Различные размещения отличаются друг от друга хотя бы одним элементом. Общее их количество обозначается символом , и находится оно по формуле:

= (2.14)

Доказательство формулы (2.14)

Очевидно, что если взять все возможные сочетания из N элементов по M элементов и сделать в каждом из них все возможные перестановки, то в итоге получим все возможные размещения из N Элементов по M элементов в каждом размещении. Отсюда следует:

, и значит (2.15)

Для примера подсчитаем общее количество всех возможных сочетаний из трех элементов (A1; A2; A3) по одному, по два и по три элемента. Причем сделаем это и непосредственно, составив все эти сочетания и пересчитав их, и по формуле (2.14):

(2.16)

Эти же результаты дает и формула (2.14):

; (2.17)

Кстати, комбинации в (2.11) и в (2.16) наглядно демонстрируют разницу между размещениями и сочетаниями.

Выводя формулы (2.1), (2.13) и (2.14) для общего числа размещений, перестановок и сочетаний, мы полагали, что в каждом из указанных соединений любой из элементов совокупности (А1; а2; …..аN) может встретиться только один раз. То есть повторять в них элементы нельзя. Если же повторять их всё же можно, то мы придём к Размещениям, перестановкам и сочетаниям с повторениями.

4. Размещения с повторениями. Начнём с рассмотрения частного случая. Пусть исходная совокупность элементов составляет всего три элемента (А1; а2; а3). Составим из них все возможные размещения с повторениями по два элемента в каждом размещении и пересчитаем их. Очевидно, их будет 9 – те 6 , что представлены в (2.11) и в которых оба элемента разные, и ещё три размещения А1а1; а2а2; а3а3 с повторяющимися элементами. Если обозначить общее число всех возможных размещений из трёх элементов по два в каждом размещении символом , то получим: =9.

Впрочем, мы могли подсчитать это число и иначе. Составляя любое размещение из двух элементов, на первое место в таком размещении можно поставить любой из данных трёх элементов (три варианта). На второе место – тоже любой из трёх элементов (тоже три варианта). Комбинируя каждый элемент, стоящий на первом месте, с каждым элементом, стоящим на втором месте, получим 32=9 всех возможных комбинаций. То есть =32=9.

А теперь легко понять, что если всех элементов не три, а N, и из них составляются все возможные размещения с повторениями по M Элементов в каждом размещении, то их общее число найдётся по формуле:

=Nm (2.18)

5. Сочетания с повторениями. Опять начнём с частного случая. А именно, подсчитаем – общее число всех возможных сочетаний с повторениями из трёх элементов (А1; а2; а3) по два элемента в каждом сочетании. Этих сочетаний, очевидно, будет 6 – те 3, которые представлены в (2.16) и в которых оба элемента разные, и ещё три сочетания А1а1; а2а2; а3а3 с повторяющимися элементами. То есть =6=. И вообще, можно доказать, что

(2.19)

6. Перестановки с повторениями. Пусть среди элементов (А1; а2; …..аN) содержится лишь K различных элементов (K<N), причём первый из них повторяется N1 раз, второй N2 раз, …K-ый Nk раз. Очевидно, что N1+N2+… Nk=N. Тогда число всех возможных перестановок из таких N Элементов обозначается символом И находится по формуле:

(2/20)

В самом деле, если бы все N Элементов были разными, то число всех возможных перестановок из них, согласно (2.13), было бы равно Но среди них разных элементов лишь K, остальные N – K элементов повторяют эти K элементов. В частности, первый из этих K элементов повторяется раз. Сделав любую перестановку из этих Одинаковых элементов (не трогая остальных!) мы ничего не нарушим ни в какой перестановке из N элементов. А вот если бы все эти повторяющихся элементов были разными, то сделав любую их перестановку, мы получили бы другую перестановку из N элементов. Количество всех возможных перестановок из N1 Элементов равно . Значит, наличие этих одинаковых элементов уменьшает в раз общее количество всех возможных перестановок из N Элементов по сравнению с тем случаем, когда все N элементов были бы разными. Тот же эффект производит наличие второго повторяющегося раз элемента, третьего, … K-ого. В итоге и приходим к формуле (2.20).

А теперь рассмотрим примеры на применение полученных выше формул.

Пример 1. В посёлке устанавливается телефонная сеть с трёхзначными телефонными номерами. Сколько всего можно установить телефонных номеров? Сколько из них будет тех, которые содержат: 1) три разные цифры? 2) две одинаковые цифры? 3) три одинаковые цифры?

Решение. Всех возможных трёхзначных телефонных номеров будет, очевидно, 1000: это номера 000, 001, 002, … 999.

1) Номеров с тремя разными цифрами будет, очевидно, столько, сколько существует всех возможных соединений (комбинаций) из 10 цифр 0,1,2,…9 по три цифры в каждом соединении. Так как в этих соединениях важен порядок следования цифр (например, 137 и 173 – это разные номера), то этими соединениями будут размещения. А значит, их общее количество N1 можно найти по формуле (2.1):

3) Пропуская вопрос (2), ответим на вопрос (3). Номеров с тремя одинаковыми цифрами будет, очевидно, 10. Это номера 000, 111, 222, … 999. То есть N3 = 10.

2) Все остальные номера – с двумя одинаковыми цифрами. Следовательно, их общее количество

N2 = 1000 – (N1 + N3 ) = 1000 – (720 + 10) = 270.

Пример 2. Сколько всего диагоналей у выпуклого N – угольника?

Решение: Соединяя каждую пару вершин треугольника, получим либо диагональ, либо сторону многоугольника. Число всех различных пар вершин N-угольника равно числу всех возможных соединений из N элементов (вершин многоугольника) по два элемента (по две вершины) в каждом соединении. Так как порядок следования элементов в этих парах, очевидно, не важен (диагональ, соединяющая, например, 2-ю и 5-ю вершину – это та же диагональ, которая соединяет 5-ю и 2-ю вершину), то такими парными соединениями будут сочетания из N элементов по два элемента в каждом сочетании. Следовательно, их общее число равно . В это число входят и сами N сторон многоугольника. Поэтому искомое число N Диагоналей N-угольника найдётся по формуле:

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

Решение. В первом круге состоится столько матчей, сколько существует сочетаний из 20 команд по две в каждом сочетании. То есть их число равно:

Во втором круге играется столько же матчей, поэтому в течение сезона их состоится 190·2=380.

Пример 4. Сколькими различными способами можно рассадить N человек за круглым столом?

Решение. Общее число всех способов, с помощью которых N человек может занять N мест за любым (не только круглым) столом равно, очевидно, числу всех перестановок из N Элементов (из N человек), то есть равно Но если стол круглый, то любая циклическая перестановка (одновременная пересадка всех вправо или влево на одно или несколько мест) не нарушает порядка рассаживания людей за столом. А таких циклических пересаживаний всего N. Поэтому искомое число Nn рассаживания N человек за круглым столом равно:

В частности, N2=1; N3 = 2; N4 = 6; N5 = 24;…..

Пример 5. Автомобильные номера состоят из двух букв (всего используется 30 букв) и трёх цифр (используются все 10 цифр). Сколько всего автомобилей можно занумеровать таким образом, чтобы никакие два автомобиля не имели одинакового номера?

Решение: Различных пар букв будет столько, сколько можно составить размещений с повторениями из 30 букв по две в каждом размещении. То есть, согласно формуле (2.18), их будет:

=302=900.

Аналогично различных троек цифр будет:

=103=1000.

(впрочем, это и так очевидно). Комбинируя (соединяя) теперь каждую пару букв с каждой тройкой цифр, получим искомое общее число N различных автомобильных номеров:

N= 900 · 1000 = 900000.

Пример 6. Имеются две колоды по 36 карт. Из каждой колоды вынимаются по одной карте. Сколько различных пар карт может быть при этом образовано?

Решение. В образовываемых парах карт порядок их следования, очевидно, не важен. Поэтому эти пары – различные сочетания из 36 карт. По условию, среди этих пар могут оказаться n пары с одинаковыми картами. То есть образованные пары карт – это сочетания с повторениями. А значит, их общее число:

Пример 7. Сколько всех возможных перестановок букв можно сделать в слове «математика»?

Решение. В слове «математика» всего 10 букв, из которых буква А повторяется 3 раза, буква М – два раза, буква т – два раза. Поэтому искомое число N Перестановок в слове «математика» - это число перестановок с повторениями. Согласно формуле (2.20),

Пример 8. Сколькими различными способами могут занять места в президиуме 5 человек, если в президиуме 8 мест?

Решение. – число всех возможных способов выбора пяти различных мест из имеющихся восьми. На этих местах 5 человек можно рассадить числом способов = 5! В итоге искомое число способов

Пример 9. Из колоды в 36 карт наудачу вынимаются две карты. Какова вероятность того, что ими окажется два туза (любых)?

Решение. В данной задаче испытание – это вынимание из колоды наудачу двух карт, а событие А – вынимание двух тузов. Возможных исходов в испытании столько, сколько всего пар карт можно составить. Таких пар будет, очевидно, N = = 630. Все эти 630 возможных исходов испытания, очевидно, равновозможны. А число M исходов, благоприятствующих событию А – это, очевидно, число всех пар из четырёх тузов, то есть M = = 6. Поэтому по классической формуле (1.3) получаем:

Пример 10. Ребёнок играет двумя карточками с буквой «М» и двумя карточками с буквой «А», выкладывая их в линию. Какова вероятность того, что у него получится слово «МАМА»?

Решение. В данной задаче испытание - это выкладывание ребёнком наудачу в линию четырёх карточек, а событие А – выкладывание слова «МАМА». Возможные исходы испытания – это различные перестановки четырёх карточек, причём перестановки с повторениями, в которых и буква М, и буква А повторяются два раза. Число таких перестановок, согласно формуле (2.20), равно

Это – число N Всех возможных исходов испытания, причём исходов равновозможных. А число M исходов, благоприятствующих событию А, равно 1: M=1 (перестановка «МАМА»). В итоге по классической формуле (1.3) получаем:

Пример 11. Из десяти билетов выигрышными являются два. Определить вероятность того, что среди наудачу взятых пяти билетов: а) только один выигрышный; б) оба выигрышные.

Решение. Здесь испытание – выбор пяти билетов из десяти. Всего существует способов выбрать 5 билетов из 10. Следовательно, число N Всех возможных исходов испытания и в задаче а), и в задаче б) одинаково и равно . Причём все эти исходы равновозможны.

В задаче а) благоприятный исход испытания состоит в том, что из двух выигрышных билетов будет выбран один (это можно сделать двумя способами), а из восьми невыигрышных будут выбраны четыре (это можно сделать Способами). Таким образом, общее число всех благоприятных исходов равно 2·, а значит, вероятность события А, состоящего в том, что среди пяти отобранных билетов окажется лишь один выигрышный, по классической формуле (1.3) равна:

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

Пример 12. На книжную полку в произвольном порядке выставлены 5 книг. Какова вероятность того, что некоторые две из них, составляющие двухтомник, окажутся на полке рядом?

Решение. В данной задаче испытание – это установка на полку в произвольном порядке пяти книг. А событие А – то, что книги двухтомника окажутся рядом.

Всех возможных исходов испытания, очевидно, столько, сколько существует перестановок из пяти книг. То есть их = 5! = 120. Благоприятствующими событию А будут те из них, когда книги двухтомника стоят рядом.

Для начала подсчитаем число тех благоприятствующих исходов, когда книги двухтомника стоят на первых двух местах, причём первый том стоит на первом месте, а второй на втором. Так как последние три книги могут быть установлены произвольно, то таких исходов будет =3! = 6. Меняя местами книги двухтомника, получим ещё 6 благоприятствующих исходов. Таким образом, если книги двухтомника занимают на полке первые два места, то всего соответствующих благоприятствующих исходов (перестановок книг) оказывается 2· = 12. Но благоприятствующими событию А Исходами будут и те, при которых книги двухтомника стоят на 2-3, 3-4, 4-5 местах. Итого всех таких исходов оказывается 12·4=48. А тогда по классической формуле (1.3) получаем:

Упражнения.

1. В пятом классе изучается 12 предметов. Сколькими способами можно составить расписание занятий на понедельник, если в этот день должно быть 4 урока? Решить задачу в предположении, что:

А) порядок уроков важен;

Б) порядок уроков не важен.

Ответ: а) 11880; б) 495.

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

Ответ: 256.

3. Пять девушек и пять юношей разыграли 10 мест выделенного им на концерт зрительного ряда (места с 31 по 40). Какова вероятность того, что они будут сидеть строго вперемешку (никакие две девушки и два юноши не будут сидеть рядом)?

Ответ: 1/126.

4. Найти вероятность того, что в лотерее «Спортлото 5 из 36» можно угадать:

А) все 5 номеров; б) 4 номера; в) 3 номера.

Ответ: а) 1/324632; б) 150/324632; в) 4350/324632.

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

6. Сколькими различными способами можно распределить 6 различных учебников между тремя студентами по два учебника каждому?

Ответ: 90 способами.

< Предыдущая		Следующая >