Комбинаторика - это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n 1 *n 2 *n 3 *...*n k .

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

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n 1 =6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n 2 =7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n 3 =4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n 1 *n 2 *n 3 =6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n 1 =n 2 =...n k =n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью .

Число размещений из n элементов по m

Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 4. Различными размещениями из трех элементов {1, 2, 3} по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A n m и вычисляется по формуле:

Замечание: n!=1*2*3*...*n (читается: "эн факториал"), кроме того полагают, что 0!=1.

Пример 5 . Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

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

Пример 6 . Для множества {1, 2, 3}сочетаниями являются {1, 2}, {1, 3}, {2, 3}.

Число сочетаний из n элементов по m

Число сочетаний обозначается C n m и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов {1, 2, 3} являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P n и вычисляется по формуле P n =n!.

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

Решение: эта задача о числе перестановок семи разных книг. Имеется P 7 =7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

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

Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок , которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

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

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.

Комбинаторика возникла в XVI веке. Первые комбинаторные задачи касались азартных игр. Сегодня комбинаторные методы используются для решения транспортных задач, составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики. Комбинаторика используется для составления и декодирования шифров, для решения других проблем теории информации.

Значительную роль комбинаторные методы играют и в чисто математических вопросах — теории групп и их представлений, изучении основ геометрии, неассоциативных алгебр и др.

Пример комбинаторной задачи. Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа

Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:

Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:

Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию, нет.

Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8, то получим ещё 12 чисел:

По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:

Вот эти числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Ответ: 48. ◄

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

Правила сложения и умножения

Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 A n можно выбрать m n способами, то выбрать или A 1 , или A 2 , или, и так далее, A n можно

m 1 + m 2 + ... + m n

способами.

Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно

способами.

Ответ: 19. ◄

Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A 1 можно выбрать m 1 способами, элемент A 2 можно выбрать m 2 способами и так далее, элемент A n можно выбрать m n способами, то набор элементов (A 1 , A 2 , ... , A n ) можно выбрать

m 1 · m 2 · ... · m n

способами.

Например.

1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно

9 · 7 · 3 = 189

способами.

Ответ: 189.

2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II способ.

0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;

второй цифрой может быть любая из четырёх оставшихся — 4 способа;

третью цифру можно выбрать среди трёх оставшихся — 3 способа.

Итак, искомое количество трёхзначных чисел:

4 · 4 · 3 = 48.

Ответ: 48. ◄

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

Множество из n элементов называется упорядоченным , если каждому его элементу поставлено в соответствие натуральное число от 1 до n .

Перестановкой из n элементов называется любое упорядоченное множество из n элементов.

Например, из 4 элементов ♦ ♣ ♠ можно составить следующие 24 перестановки:

♦ ♣ ♠	♦ ♣ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♠ ♣	♦ ♠ ♣	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♦ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♠ ♦	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♦ ♣	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♣ ♦	♣ ♠ ♦	♠ ♣ ♦

◄

Количество перестановок из n элементов принято обозначать P n . С помощью перебора возможных вариантов легко убедиться, в том что

P 1 = 1; P 2 = 2; P 3 = 6; P 4 = 24.

Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n , то есть n ! (читается "эн факториал"):

P n = 1 · 2 · 3 · ... · (n - 1 ) · n = n !.

Для P n справедлива рекуррентная формула:

P n = n · P n - 1 .

Значение факториала определено не только для натуральных чисел, но и для 0:

0! = 1 .

Таблица факториалов целых чисел от 0 до 10
n		1	2	3	4	5	6	7	8	9	10
n !	1	1	2	6	24	120	720	5 040	40 320	362 880	3 628 800

Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?

Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.

Рассмотрим первый случай. Мальчики по нечётным местам могут сесть

P 5 = 120

способами. Столько способов и для девочек на чётных местах. Согласно правилу умножения, мальчики — на нечётных местах, девочки на чётных могут расположиться

120 · 120 = 14 400

способами. Значит, всего способов

14 400 + 14 400 = 28 800.

Ответ: 28 800. ◄

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

Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n 1 неразличимых элементов первого типа, n 2 неразличимых элементов второго типа и так далее, n k неразличимых элементов k -го типа (где n 1 + n 2 + … + n k = n ), называется любое расположение этих элементов по n различным местам.

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n 1 , n 2 , …, n k раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$

Например, сколько различных десятизначных чисел можно составить из цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В данном случае: n = 10, n 1 = 1, n 2 = 2, n 3 = 3, n 4 = 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$

Ответ: 12 600. ◄

Размещения

Размещением из n элементов по m (m ≤ n) m элементов, взятых в определённом порядке из данных n элементов.

Два размещения из n элементов по m считаются различными, если они различаются самими элементами или порядком их расположения.

Например, составим все размещения из четырёх элементов A, B, C, D по два элемента:

A B; A C;A D;

B A; B C; B D;

C A; C В; C D;

D A; D В; D C.

◄

Число всех размещений из n элементов по m обозначают \(A_n^m\) (читается: "А из n по m ") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$

Примеры задач.

1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II I способ.

Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.

2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?

Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать \(A_{20}^3\) способами. Порядок бортинженеров тоже важен, значит, для их выбора существует \(A_{15}^2\) способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. ◄

Понятно, что, если m = n , то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо также, что, если m = n - 1 , то$$A_n^{n-1}=A_n^n=P_n=n!.$$

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

Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением .

Пусть имеется n различных объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив номером 2, и снова вернём объект обратно. И так далее, пока не получим m названий.

Размещения с повторениями обозначаются \(\overline{A}_n^m\) и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.

Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$

◄

Сочетания

Сочетанием из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, выбранных из данных n элементов.

В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по m считаются различными, если они различаются хотя бы одним элементом.

Например, составим все сочетания из четырёх элементов A, B, C, D по два элемента:

A B; A C;A D;

B C; B D;

C D .

◄

Число всех сочетаний из n элементов по m обозначают \(C_n^m\) (читается: "C из n по m ") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$

Примеры задач.

1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?

Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. ◄

2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?

Количество всех возможных команд по 7 человек из класса равно \(C_{30}^7\). Количество команд в которых только мальчики — \(C_{13}^7\). Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. ◄

Сочетания с повторениями

Помимо обычных сочетаний рассматривают сочетания с повторениями .

Пусть в множестве имеется n объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был взят и записан ранее), запишем его название и снова вернём объект обратно. И так далее, пока не получим m названий.

Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми.

Сочетания с повторениями обозначаются \(\overline{C}_n^m\) и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n , то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.

Например, выясним сколькими способами можно купить 7 пирожных в кондитерском отделе, если в продаже 4 их сорта?

Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$

Ответ: 120. ◄

Бином Ньютона и биномиальные коэффициенты

Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона . Правая часть равенства называется биномиальным разложением в сумму , а коэффициенты \(C_n^0,~C_n^1,~...~,~C_n^n\) — биномиальными коэффициентами .

Свойства биномиальных коэффициентов:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ \)

Свойства биномиального разложения:

1. Число всех членов разложения на единицу больше показателя степени бинома,

то есть равно n + 1 .

2. Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,

то есть (n - m) + m = n .

3. Общий член разложения (обозначается T n +1 ) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$

Треугольник Паскаля

Все возможные значения биномиальных коэффициентов (числа сочетаний) для каждого показателя степени бинома n можно записать в виде бесконечной треугольной таблицы. Такая таблица называется треугольником Паскаля:

					\(C_0^0\)
				\(C_1^0\)		\(C_1^1\)
			\(C_2^0\)		\(C_2^1\)		\(C_2^2\)
		\(C_3^0\)		\(C_3^1\)		\(C_3^2\)		\(C_3^3\)
	\(C_4^0\)		\(C_4^1\)		\(C_4^2\)		\(C_4^3\)		\(C_4^4\)
\(C_5^0\)		\(C_5^1\)		\(C_5^2\)		\(C_5^3\)		\(C_5^4\)		\(C_5^5\)
	. . .				. . .				. . .

В этом треугольнике крайние числа в каждой строке равны 1. Действительно, \(C_n^0=C_n^n=1\). А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\).

Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел \(C_n^m\):

n = 0									1
n = 1								1		1
n = 2							1		2		1
n = 3						1		3		3		1
n = 4					1		4		6		4		1
n = 5				1		5		10		10		5		1
n = 6			1		6		15		20		15		6		1
n = 7		1		7		21		35		35		21		7		1
n = 8	1		8		28		56		70		56		28		8		1
...				...				...		...				...

Формулы комбинаторики.

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

Размещения .

Определœение 1. Размещением без повторений из n элементов по k принято называть всякое упорядоченное подмножество данного множества M={a 1 ,a 2 ,¼,a n }, содержащее k элементов.

Отметим, что из определœения сразу следует, что, во-первых, всœе элементы в размещении без повторений различны (в противном случае найдется два одинаковых элемента), во-вторых, k£ n , в-третьих, два различных размещения без повторений различаются либо составом входящих в них элементов, либо порядком их расположения. То есть порядок следования существенен.

Теорема 1. Число различных размещений без повторений из n элементов по k (k£ n) равно

Доказательство.

Пусть M ={a 1 ,a 2 ,¼,a n }. Требуется определить число различных строк вида (x 1 ,x 2 ,¼,x k ), где всœе элементы x 1 ,x 2 ,¼,x k ÎM и различны. Первый элемент x 1 можно выбрать n способами. В случае если x 1 уже выбран, то для выбора x 2 осталось n-1 элементов. Аналогично, x 3 можно выбрать n -2 способами и т.д. Последний элемент x k можно выбрать n-k+1 способами. Перемножая эти числа, получим формулу (4).Теорема доказана.

Пример 1. В классе 12 учебных предметов и в понедельник 5 разных уроков. Сколькими способами должна быть составлено расписание занятий на понедельник?

Число всœевозможных вариантов расписания есть, очевидно, число различных размещений из 12 элементов по 5, то есть

Важным частным случаем, является случай, когда n=k , то есть когда в строке (x 1 ,x 2 ,¼,x n) участвуют всœе элементы множества M . Строки без повторений, составленные из n элементов множества M называют перестановками из n элементов. Напомним, что в математике через n! обозначают произведение всœех натуральных чисел от 1 до n, то есть ¼и по определœению считают, что 0!=1.

Следствие 1 . Пользуясь формулой (4), находим, что число различных перестановок P n из n элементов равно P n = n !.

Определœение 2. Размещением с повторениями из n элементов по k принято называть любая упорядоченная строка из k элементов множества M={a 1 ,a 2 ,¼,a n }, некоторые из которых могут повторяться.

К примеру, слово “мама” есть размещение с повторениями из 2-х элементов M ={м, а} по 4.

Теорема 2. Число различных размещений с повторениями из n элементов по k

Доказательство.

Первый элемент в строку из k элементов должна быть выбран n способами, поскольку |M|=n. Точно также 2-й, 3-й, …,k-й элементы бывают выбраны n способами. Перемножая эти числа, получим

k раз

Теорема доказана.

Пример 2. Сколько можно составить различных двузначных чисел из цифр 1, 2, 3, 4, 5?

В этой задаче M ={1, 2, 3, 4, 5}, n=5, k=2.По этой причине ответом является число

Пример 3. Сколькими способами k пассажиров могут распределиться по n вагонам, в случае если для каждого пассажира существенным является только номер вагона, а не занимаемое им в вагоне место?

Перенумеруем всœех пассажиров. Пусть x 1 - номер вагона, выбранного первым пассажиром, x 2 - номер вагона второго пассажира, …, x k - номер вагона k -го пассажира. Строка (x 1 ,x 2 ,¼,x k ) полностью характеризует распределœение пассажиров по вагонам. Каждое из чисел x 1 ,x 2 ,¼,x k может принимать любое целое значение от 1 до n. По этой причине в данном примере

M ={1, 2,…,n} и различных распределœений по вагонам будет столько же, сколько строк длиной k можно составить из элементов множества M , то есть

Отметим ещё раз, что в размещениях с повторениями и без повторений важен порядок следования элементов. В случае если порядок следования элементов не существенен, то в данном случае говорят о сочетаниях.

Сочетания (без повторения ).

Определœение 3. Пусть M={a 1 ,a 2 ,¼,a n }. Любое подмножество X мно-жества M , содержащее k элементов, принято называть сочетанием k элементов из n.

Отметим сразу, что в данном определœении порядок следования элементов множества X несущественен и, что k£n , поскольку k=½X½, n=½M½ и XÍM .

Теорема 3. Число различных сочетаний k элементов из n равно

. (6)

Доказательство.

Каждое сочетание k элементов из n порождает k! различных размещений без повторений из n по k с помощью различных перестановок (см. следствие 1). Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, всœе сочетаний из k элементов из n после различных k! перестановок порождают всœе размещений без повторений из n по k . По этой причине . Следовательно,

2.1. Относительная частота. Устойчивость относительной частоты

2.2. Ограниченность классического определения вероятности. Статистическая вероятность

2.3. Геометрические вероятности

2.4. Теорема сложения вероятностей

2.5. Полная группа событий

2.6. Противоположные события

2.7. Принцип практической невозможности маловероятных событий

2.8. Произведение событий. Условная вероятность

2.9. Теорема умножения вероятностей

2.10. Независимые события. Теорема умножения для независимых событий

2.10. Вероятность появления хотя бы одного события

Лекция №3 следствия теорем сложения и умножения

3.1. Теорема сложения вероятностей совместных событий

3.2. Формула полной вероятности

3.3. Вероятность гипотез. Формулы Бейеса

4. Повторение испытаний

4.1. Формула Бернулли

4.2. Предельные теоремы в схеме Бернулли

4.3. Локальная и интегральная теоремы Муавра-Лапласа

4.3. Вероятность отклонения относительной частоты от постоянной вероятности в независимых испытаниях

5. Случайные величины

5.1. Понятие случайной величины. Закон распределения случайной величины

5.2. Закон распределения дискретной случайной величины. Многоугольник распределения

5.3. Биномиальное распределение

5.4. Распределение Пуассона

5.5. Геометрическое распределение

5.6. Гипергеометрическое распределение

6. Математическое ожидание дискретной случайной величины

6.1. Числовые характеристики дискретных случайных величин

6.2. Математическое ожидание дискретной случайной величины

6.3. Вероятностный смысл математического ожидания

6.4. Свойства математического ожидания

6.5. Математическое ожидание числа появлений события в независимых испытаниях

7. Дисперсия дискретной случайной величины

7.1. Целесообразность введения числовой характеристики рассеяния случайной величины

7.2. Отклонение случайной величины от ее математического ожидания

7.3. Дисперсия дискретной случайной величины

7.4. Формула для вычисления дисперсии

7.5. Свойства дисперсии

7.6. Дисперсия числа появлений события в независимых испытаниях

7.7. Среднее квадратическое отклонение

7.8. Среднее квадратическое отклонение суммы взаимно независимых случайных величин

7.9. Одинаково распределенные взаимно независимые случайные величины

7.10. Начальные и центральные теоретические моменты

8. Закон больших чисел

8.1. Предварительные замечания

8.2. Неравенство Чебышева

8.3. Теорема Чебышева

8.4. Сущность теоремы Чебышева

8.5. Значение теоремы Чебышева для практики

8.6. Теорема Бернулли

Функция распределения вероятностей случайной величины

9.1. Определение функции распределения

9.2. Свойства функции распределения

9.3. График функции распределения

10. Плотность распределения вероятностей непрерывной случайной величины

10.1. Определение плотности распределения

10.2. Вероятность попадания непрерывной случайной величины в заданный интервал

10.3. Закон равномерного распределения вероятностей

11. Нормальное распределение

11.1. Числовые характеристики непрерывных случайных величин

11.2. Нормальное распределение

11.3. Нормальная кривая

11.4. Влияние параметров нормального распределения на форму нормальной кривой

11.5. Вероятность попадания в заданный интервал нормальной случайной величины

11.6. Вычисление вероятности заданного отклонения

11.7. Правило трех сигм

11.8. Понятие о теореме Ляпунова. Формулировка центральной предельной теоремы

11.9. Оценка отклонения теоретического распределения от нормального. Асимметрия и эксцесс

11.10. Функция одного случайного аргумента и ее распределение

11.11. Математическое ожидание функции одного случайного аргумента

11.12. Функция двух случайных аргументов. Распределение суммы независимых слагаемых. Устойчивость нормального распределения

11.13. Распределение «хи квадрат»

11.14. Распределение Стьюдента

11.15. Распределение f Фишера – Снедекора

12. Показательное распределение

12.1. Определение показательного распределения

12.2. Вероятность попадания в заданный интервал показательно распределенной случайной величины

§ 3. Числовые характеристики показательного распределения

12.4. Функция надежности

12.5. Показательный закон надежности

12.6. Характеристическое свойство показательного закона надежности

1.7. Основные формулы комбинаторики

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

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

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

Р n = n !

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

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

Решение . Искомое число трехзначных чисел Р 3 = 3! = 123 = 6.

Размещениями n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений

Пример . Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

Решение . Искомое число сигналов
.

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний

.

Пример . Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?

Решение . Искомое число способов
.

Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством

Замечание . Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т. д., то число перестановок с повторениями

,

где n 1 + n 2 + ... = n .

При решении задач комбинаторики используют следующие правила:

1. Правило суммы. Если некоторый объект A может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А , либо В можно m + n способами.

2. Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А , В ) в указанном порядке может быть выбрана mn способами.

Приведем несколько примеров непосредственного вычисления вероятностей.

Пример 1. Набирая номер телефона, абонент забыл одну цифру и набрал ее наудачу. Найти вероятность того, что набрана нужная цифра.

Решение. Обозначим через А событие – набрана нужная цифра. Абонент мог набрать любую из 10 цифр, поэтому общее число возможных элементарных исходов равно 10. Эти исходы несовместны, равновозможны и образуют полную группу. Благоприятствует событию А лишь один исход (нужная цифра лишь одна). Искомая вероятность равна отношению числа исходов, благоприятствующих событию, к числу всех элементарных исходов:

Р (А )=1/10.

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

Решение. Обозначим через В событие – набраны две нужные цифры. Всего можно набрать столько различных цифр, сколько может быть составлено размещений из десяти цифр по две, т.е.
. Таким образом, общее число возможных элементарных исходов равно 90. Эти исходы несовместны, равновозможны и образуют полную группу. Благоприятствует событию В лишь один исход. Искомая вероятность равна отношению числа исходов, благоприятствующих событию, к числу всех элементарных исходов:

Р (В )=1/90.

Пример 3. Указать ошибку «решения» задачи: «Брошены две игральные кости. Найти вероятность того, что сумма выпавших очков равна 4 (событие А )».

Решение. Всего возможны 2 исхода испытания: сумма выпавших очков равна 4, сумма выпавших очков не равна 4. Событию А благоприятствует один исход; общее число исходов равно двум. Следовательно, искомая вероятность

Р (А ) = 1/2.

Ошибка этого решения состоит в том, что рассматриваемые исходы не являются равновозможными.

Правильное решение . Общее число равновозможных исходов испытания равно 66 = 36 (каждое число выпавших очков на одной кости может сочетаться со всеми числами очков другой кости). Среди этих исходов благоприятствуют событию А только 3 исхода: (1; 3), (3; 1), (2; 2) (в скобках указаны числа выпавших очков). Следовательно, искомая вероятность

Р (А ) = 3/36 = 1/12.

Пример 4. В партии из 10 деталей 7 стандартных. Найти вероятность того, что среди шести взятых наудачу деталей 4 стандартных.

Решение. Общее число возможных элементарных исходов испытания равно числу способов, которыми можно извлечь 6 деталей из 10, т. е. числу сочетаний из 10 элементов но 6 элементов ().

Определим число исходов, благоприятствующих интересующему нас событию А (среди шести взятых деталей 4 стандартных). Четыре стандартные детали можно взять на семи стандартных деталей способами; при этом остальные 6 – 4 = 2 детали должны быть нестандартными; взять же 2 нестандартные детали из 10 – 7 = 3 нестандартных деталей можноспособами. Следовательно, число благоприятствующих исходов равно
.

Искомая вероятность равна отношению числа исходов, благоприятствующих событию, к числу всех элементарных исходов: