Язык издания: русский
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Основные понятия комбинаторики
Автор: Романов Сергей Евгеньевич
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Основные понятия комбинаторики
Автор: Романов Сергей Евгеньевич
ОСНОВНЫЕ ПОНЯТИЯ КОМБИНАТОРИКИКомбинаторикой называется область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из элементов, принадлежащих заданному множеству.При решении многих практических задач приходится выбирать из некоторой совокупности объектов элементы, обладающие тем или иным свойством, подсчитывать, сколько различных комбинаций можно составить из конечного числа элементов, принадлежащих заданной совокупности, располагать эти элементы в определенном порядке и так далее. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, то их называют комбинаторными задачами, а область математики, в которой изучаются комбинаторные задачи, — комбинаторикой. Комбинаторные методы применяются в физике, химии, биологии, экономике, лингвистике и многих других науках. Рассмотрим два основных закона, с помощью которых решаются многие задачи комбинаторики, — правило суммы и правило произведения.1. Правило суммыРассмотрим следующий пример. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой — 40 различных книг (и нет таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30+40=70 способами. Обобщением этого примера является, следующее утверждение, называемое правилом суммы.Если элемент а можно выбрать m способами, а элемент b - n способами, причем любой выбор элемента а отличен, от любого выбора элемента b, то выбор «а или b» можно сделать m+n способами. 2. Правило произведенияПусть существует три кандидата K1, K2, K3 на место командира корабля и два кандидата B1 и В2 на место бортинженера. Сколькими способами можно сформировать экипаж корабля, состоящий из командира и бортинженера?Решение. Командира корабля можно выбрать тремя способами. После выбора командира еще двумя способами можно выбрать бортинженера, поэтому общее число способов, которыми можно составить экипаж, находится произведением 3∙2=6. Обобщением этого примера является следующее утверждение, называемое правилом произведения. Если множества А и В конечны, то число N всевозможных пар (а, b), где а∈А, b∈B равно произведению чисел элементов этих множеств: N = n(А) • п(В).Пример. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?Решение. Цифра разряда десятков тысяч и цифра разряда единиц должны быть одинаковыми, не равными 0 (9 возможностей); цифра разряда тысяч и разряда десятков может быть любой (10 возможностей); цифра разряда сотен может быть любой (10 возможностей). Итак, согласно правилу произведения, всего искомых чисел 9∙10∙10=900.Пример. Сколько существует шестизначных чисел, которые делятся на пять?Решение. Поскольку число делится на 5, то его цифра разряда единиц равна 0 или 5 (2 возможности). Цифры разряда десятков, сотен, тысяч и десятков тысяч могут быть любыми (то есть в каждом из этих случаев имеется 10 возможностей). Цифра разряда сотен тысяч шестизначного числа может быть любой, кроме 0 (9 возможностей). Следовательно, всего искомых чисел 9∙10∙10∙10∙10∙2=180000.Пример. В розыгрыше первенства по футболу принимают участие 18 команд. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали, если любая команда может получить только одну медаль?Решение. Одну из медалей, например бронзовую, может получить одна из 18 команд (18 возможностей). После того как определился бронзовый призер, обладателем другой медали, например золотой, может стать одна из оставшихся 17 команд (17 возможностей). После того как определились бронзовый и золотой призеры, обладателем серебряной медали может быть одна. из оставшихся. 16 команд (16 возможностей). Следовательно, общее число способов, которыми могут быть распределены золотая, серебряная и бронзовая медали, равно 18∙17∙16==4896.3. Виды комбинацийВ комбинаторике рассматривают три типа комбинаций объектов: размещения, перестановки и сочетания. Рассмотрим их.При выборе k элементов из п различных элементов принято говорить, что они образуют комбинации из п. элементов по k.В зависимости от того, имеет ли значение порядок элементов в комбинации или нет, а также от того, входят в комбинацию все п элементов или только часть их, различают три вида комбинаций.1. Комбинации, отличающиеся друг от друга составом элементов или их порядком, каждая из которых содержит k (k≤n) элементов, взятых из n различных элементов, называются размещениями из n элементов по k.Например, выпишем все размещения из элементов а, b, с, d по два:ab, bа, ас, са, ad, da, bc, cb, bd, db, cd, dc.2. Комбинации, каждая из которых содержит п различных элементов, взятых в определенном порядке, называются перестановками из п элементов.Например, выпишем все перестановки из элементов а, b, с:аbс, acb, bас, bса, cab, cba.3. Комбинации, отличающиеся друг от друга по крайней мере, одним элементом, каждая из которых содержит k элементов, взятых из п различных элементов, называются сочетаниями (выборками) из п элементов по k. Порядок следования элементов не учитывается.Например, выпишем все сочетания из элементов а, b, с, d, е по три: аbс, abd, abe, acd, асе, ade, bcd, bce, bde,cde.4. Количество размещенийПри решении различных задач возникает вопрос о том, сколькими способами можно выбрать k объектов из множества, содержащего п таких объектов, причем k объектов должны выбираться в определенном порядке. Другими словами, сколькими способами можно выбрать и разместить по k различным местам k из n различных предметов?Пример. Сколько всего семизначных телефонных номеров, в каждом из которых ни одна цифра не повторяется?Решение. Это задача о выборе и размещении по семи различным местам семи из десяти различных цифр. Существует 10 способов выбора первой цифры телефонного номера. Так как, по условию, цифры в номере не могут повторяться, то после того, как выбрана первая цифра номера, остаётся 9 способов выбора второй цифры номера. После выбора первой и второй цифр номера остаётся 8 способов выбора третьей цифры номера и так далее. И, наконец, после выбора первых шести цифр номера остаётся четыре способа выбора последней седьмой цифры семизначного номера; поэтому, согласно правилу произведения, число указанных телефонных номеров равно 10∙9∙8∙7∙6∙5∙4=604800Определение. Размещениями из n объектов по k называют любой выбор k объектов, взятых в определенном порядке из n объектов. Число размещений из п объектов по k обозначают . В данной формуле используется понятие факториала. Определение. Произведение всех натуральных чисел от 1 до n обозначается n! и читается «эн факториал». Таким образом n!=1∙2∙3∙…∙(n-1)∙n.В частности, 1!=1; 2!=1∙2=2; 3!=1∙2∙3=6; 4!=1∙2∙3∙4=24; 5!=1∙2∙3∙4∙5=120; 6!=1∙2∙3∙4∙5∙6=720.Вычислять n! для больших значений n крайне трудно, ибо с увеличением n величина n! растет очень быстро.Для удобства условились считать, что 0!=1.5. Количество перестановокЕсли в размещениях рассмотреть случай k=n, то мы получим размещения, отличающиеся друг от друга только порядком элементов. Другими словами, возникает вопрос: сколькими способами можно переставить n различных предметов, расположенных на n различных местах?Определение. Размещения из n элементов по n называются перестановками. Число перестановок обозначается Pn. Из формулы для размещений получаем формулу для вычисления числа перестановок: Пример. Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7 и 9, если из этих чисел ни одна не повторяется.Решение. Необходимым и достаточным условием делимости натурального числа на 2 является делимость на 2 цифры разряда единиц этого числа. Поэтому из всех указанных цифр цифрой единиц искомого числа может быть только цифра 4. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Следовательно, поставленная задача сводится к нахождению числа перестановок из 5 элементов. Поскольку P5=5!=1∙2∙3∙4∙5=120, то всего можно составить 120 указанных чисел.6. Количество сочетанийВ размещениях из n элементов по k изучаемые комбинации отличаются друг от друга либо элементами, либо их порядком, либо и тем и другим. Если мы не будем различать комбинации, отличающиеся друг от друга только порядком, то придем к комбинациям, различающимся только элементами.Определение. Сочетаниями из n объектов по k называют любой выбор k объектов, взятых из n объектов.Из определения сочетаний следует, что они отличаются друг от друга только элементами. Число сочетаний из n объектов по k обозначают . Пример. В классе 25 учеников. Сколькими способами из них можно выбрать четырех учащихся для дежурства на вечере?Решение: 7. Алгоритм выбора типа комбинации
