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

Лекция 21 Основные формулы и правила комбинаторики Комбинаторика определенным безразлично изучает условиям, какой количества которые природы, комбинаций, можно заданного составить конечного подчиненных из элементов, множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Формулы и вероятностей правила для комбинаторики подсчета вероятности используются случайных в теории событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике. Области применения комбинаторики: -учебные заведения ( составление расписаний) -сфера общественного питания (составление меню) -лингвистика (рассмотрение вариантов комбинаций букв) -спортивные соревнования (расчёт количества игр между участниками) -агротехника (размещение посевов на нескольких полях) -география (раскраска карт) -биология (расшифровка кода ДНК) -химия (анализ возможных связей между химическими элементами) -экономика (анализ вариантов купли-продажи акций) азартные игры (подсчёт частоты выигрышей) -криптография (разработка методов шифрования) -доставка почты (рассмотрение вариантов пересылки) -военное дело (расположение подразделений) и др. 1 Перестановками без повторений называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок Pn  n!, где n! = 1 ∙ 2 ∙ 3 ∙... ∙n. Заметим, что 0! = 1. Пример 1. В библиотеке в очереди стоят 4 студента. Сколько вариантов очередей возможно? Решение. Искомое число вариантов очередей P4  4! 1 2  3  4  24 . Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае перестановки с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениями: Р n (n1 , n 2 ,...)  n! , где n1 + n2 + ... = n. n1!n 2 !... Пример 2. Сколько различных «слов» можно получить, переставляя буквы в слове «математика»? Решение. Р10 (2,3,2)  Искомое число способов 10! 4  5  6  7  8  9 10   151200. 2!3!2! 22 Размещениями без повторений называют комбинации, составленные из n различных элементов по k элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений Ank  n! . (n  k )! Пример 3. Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2? 6! Решение. Искомое число сигналов А26 = (6−2)! = 2 6! 4! = 6 ∙ 5 = 30. Число размещений из n элементов по k с повторениями обозначается k k An и находится: A n  n k . Пример 4. У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера, чтобы составить каталог. Сколько различных пятизначных номеров может составить мальчик? Решение. Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов 5 по 5: A3  35  243. Сочетаниями без повторений называют комбинации, составленные из n различных элементов по k элементов, которые отличаются хотя бы одним элементом. Число сочетаний Cnk  n! k!(n  k )! Пример 5. Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей? 2  Решение. Искомое число способов C10 10! 9  10   45 . 2!8 2 k Число сочетаний с повторениями C n из n элементов по k выражается k через число сочетаний без повторений: C n  Cnk k 1 Пример 6. В кафе в продаже имеются 5 сортов пирожных. Сколькими способами 8 студенток могут заказать себе по одному пирожному? Решение. Таким образом, 8 8 C 5  C58 8 1  С12  12! 9  10  11  12   495 8!4! 2 3 4 Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством Ank  Pk  Cnk . При решении задач комбинаторики используют следующие правила: 3 Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами. Пример 7. В студенческой группе учится 10 юношей и 15 девушек. Сколькими способами можно выбрать одного старосту группы? Решение. Старостой можно выбрать юношу или девушку. По правилу суммы получаем, что одного старосту можно выбрать 10+15=25 способами. Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m·n способами. Пример 8. В студенческой группе учится 10 юношей и 15 девушек. Сколькими способами можно выбрать двух студентов разного пола для участия в научной конференции? Решение. Для участия в научной конференции необходимо выбрать одного юношу и одну девушку. По правилу произведения получаем, что выбрать двух студентов разного пола можно 10∙15=150 способами. 4