Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)
Чем будем заниматься? В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых.
С множеством разобрались, теперь о комбинациях. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Давайте прямо сейчас посмотрим, как это происходит:
Перестановки, сочетания и размещения без повторений
Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:
яблоко / груша / банан
Вопрос первый : сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого : 6 комбинаций или 6 перестановок .
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!
Пожалуйста, откройте справочный материал (методичку удобно распечатать) и в пункте № 2 найдите формулу количества перестановок.
Никаких мучений – 3 объекта можно переставить способами.
Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте – для того, чтобы съесть! =)
а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний
:
Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша;
яблоко и банан;
груша и банан.
Количество комбинаций легко проверить по той же формуле:
Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.
г) Сколькими способами можно взять хотя бы один
фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.
Читатели, внимательно изучившие вводный урок по теории вероятностей , уже кое о чём догадались. Но о смысле знака «плюс» позже.
Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)
Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:
яблоко и груша;
яблоко и банан;
груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.
И такая перестановка возможна для каждой пары фруктов.
Рассмотрим ту же студенческую группу, которая пошла на танцы. Сколькими способами можно составить пару из юноши и девушки?
Способами можно выбрать 1 юношу;
способами можно выбрать 1 девушку.
Таким образом, одного юношу и
одну девушку можно выбрать: 
способами.
Когда из каждого множества выбирается по 1 объекту, то справедлив следующий принцип подсчёта комбинаций: «каждый объект из одного множества может составить пару с каждым объектом другого множества».
То есть, Олег может пригласить на танец любую из 13 девушек, Евгений – тоже любую из тринадцати, и аналогичный выбор есть у остальных молодых людей. Итого: возможных пар.
Следует отметить, что в данном примере не имеет значения «история» образования пары; однако если принять во внимание инициативу, то количество комбинаций нужно удвоить, поскольку каждая из 13 девушек тоже может пригласить на танец любого юношу. Всё зависит от условия той или иной задачи!
Похожий принцип справедлив и для более сложных комбинаций, например: сколькими способами можно выбрать двух юношей и двух девушек для участия в сценке КВН?
Союз И недвусмысленно намекает, что комбинации необходимо перемножить:
Возможных групп артистов.
Иными словами, каждая пара юношей (45 уникальных пар) может выступать с любой парой девушек (78 уникальных пар). А если рассмотреть распределение ролей между участниками, то комбинаций будет ещё больше. …Очень хочется, но всё-таки воздержусь от продолжения, чтобы не привить вам отвращение к студенческой жизни =).
Правило умножения комбинаций распространяется и на бОльшее количество множителей:
Задача 8
Сколько существует трёхзначных чисел, которые делятся на 5?
Решение : для наглядности обозначим данное число тремя звёздочками: ***
В разряд сотен можно записать любую из цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9). Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.
А вот в разряд десятков («посерединке») можно выбрать любую из 10 цифр: .
По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.
Итого, существует : трёхзначных чисел, которые делятся на 5.
При этом произведение расшифровывается так: «9 способами можно выбрать цифру в разряд сотен и 10 способами выбрать цифру в разряд десятков и 2 способами в разряд единиц »
Или ещё проще: «каждая из 9 цифр в разряде сотен комбинируется с каждой из 10 цифр разряда десятков и с каждой из двух цифр в разряде единиц ».
Ответ : 180
А теперь…
Да, чуть не забыл об обещанном комментарии к задаче № 5, в которой Боре, Диме и Володе можно сдать по одной карте способами. Умножение здесь имеет тот же смысл: способами можно извлечь 3 карты из колоды И в каждой выборке переставить их способами.
А теперь задача для самостоятельного решения… сейчас придумаю что-нибудь поинтереснее, …пусть будет про ту же русскую версию блэкджека:
Задача 9
Сколько существует выигрышных комбинаций из 2 карт при игре в «очко»?
Для тех, кто не знает: выигрывает комбинация 10 + ТУЗ (11 очков) = 21 очко и, давайте будем считать выигрышной комбинацию из двух тузов.
(порядок карт в любой паре не имеет значения)
Краткое решение и ответ в конце урока.
Кстати, не надо считать пример примитивным. Блэкджек – это чуть ли не единственная игра, для которой существует математически обоснованный алгоритм, позволяющий выигрывать у казино. Желающие могут легко найти массу информации об оптимальной стратегии и тактике. Правда, такие мастера довольно быстро попадают в чёрный список всех заведений =)
Пришло время закрепить пройденный материал парой солидных задач:
Задача 10
У Васи дома живут 4 кота.
а) сколькими способами можно рассадить котов по углам комнаты?
б) сколькими способами можно отпустить гулять котов?
в) сколькими способами Вася может взять на руки двух котов (одного на левую, другого – на правую)?
Решаем : во-первых, вновь следует обратить внимание на то, что в задаче речь идёт о разных объектах (даже если коты – однояйцовые близнецы). Это очень важное условие!
а) Молчание котов. Данной экзекуции подвергаются сразу все коты
+ важно их расположение, поэтому здесь имеют место перестановки:
способами можно рассадить котов по углам комнаты.
Повторюсь, что при перестановках имеет значение лишь количество различных объектов и их взаимное расположение. В зависимости от настроения Вася может рассаживать животных полукругом на диване, в ряд на подоконнике и т.д. – перестановок во всех случаях будет 24. Желающие могут для удобства представить, что коты разноцветные (например, белый, чёрный, рыжий и полосатый) и перечислить все возможные комбинации.
б) Сколькими способами можно отпустить гулять котов?
Предполагается, что коты ходят гулять только через дверь, при этом вопрос подразумевает безразличие по поводу количества животных – на прогулку могут выйти 1, 2, 3 или все 4 кота.
Считаем все возможные комбинации:
Способами можно отпустить гулять одного кота (любого из четырёх);
способами можно отпустить гулять двух котов (варианты перечислите самостоятельно);
способами можно отпустить гулять трёх котов (какой-то один из четырёх сидит дома);
способом можно выпустить всех котов.
Наверное, вы догадались, что полученные значения следует просуммировать:
способами можно отпустить гулять котов.
Энтузиастам предлагаю усложнённую версию задачи – когда любой кот в любой выборке случайным образом может выйти на улицу, как через дверь, так и через окно 10 этажа. Комбинаций заметно прибавится!
в) Сколькими способами Вася может взять на руки двух котов?
Ситуация предполагает не только выбор 2 животных, но и их размещение по рукам:
способами можно взять на руки 2 котов.
Второй вариант решения: способами можно выбрать двух котов и
способами посадить каждую
пару на руки: 
Ответ : а) 24, б) 15, в) 12
Ну и для очистки совести что-нибудь поконкретнее на умножение комбинаций…. Пусть у Васи дополнительно живёт 5 кошек =) Сколькими способами можно отпустить гулять 2 котов и 1 кошку?
То есть, с каждой парой котов можно выпустить каждую кошку.
Ещё один баян для самостоятельного решения:
Задача 11
В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами:
1) пассажиры могут выйти на одном и том же этаже (порядок выхода не имеет значения)
;
2) два человека могут выйти на одном этаже, а третий – на другом;
3) люди могут выйти на разных этажах;
4) пассажиры могут выйти из лифта?
И тут часто переспрашивают, уточняю: если 2 или 3 человека выходят на одном этаже, то очерёдность выхода не имеет значения. ДУМАЙТЕ, используйте формулы и правила сложения/умножения комбинаций. В случае затруднений пассажирам полезно дать имена и порассуждать, в каких комбинациях они могут выйти из лифта. Не нужно огорчаться, если что-то не получится, так, например, пункт № 2 достаточно коварен.
Полное решение с подробными комментариями в конце урока.
Заключительный параграф посвящён комбинациям, которые тоже встречаются достаточно часто – по моей субъективной оценке, примерно в 20-30% комбинаторных задач:
Перестановки, сочетания и размещения с повторениями
Перечисленные виды комбинаций законспектированы в пункте № 5 справочного материала Основные формулы комбинаторики , однако некоторые из них по первому прочтению могут быть не очень понятными. В этом случае сначала целесообразно ознакомиться с практическими примерами, и только потом осмысливать общую формулировку. Поехали:
Перестановки с повторениями
В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов , но есть одно но: в данном множестве один или бОльшее количество элементов (объектов) повторяются. Встречайте очередной стандарт:
Задача 12
Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?
Решение : в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу , однако совершенно понятно, что для предложенного набора карточек некоторые манипуляции будут срабатывать «вхолостую», так, например, если поменять местами любые две карточки с буквами «К» в любом слове, то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой «К», другая – квадратной с нарисованной буквой «К». Но по смыслу задачи даже такие карточки считаются одинаковыми , поскольку в условии спрашивается о буквосочетаниях.
Всё предельно просто – всего: 11 карточек, среди которых буква:
К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.
Проверка: 3 + 3 + 2 + 1 + 1 + 1 = 11, что и требовалось проверить.
По формуле количества перестановок с повторениями
:
различных буквосочетаний можно получить. Больше полумиллиона!
Для быстрого расчёта большого факториального значения удобно использовать стандартную функцию Экселя: забиваем в любую ячейку =ФАКТР(11) и жмём Enter .
На практике вполне допустимо не записывать общую формулу и, кроме того, опускать единичные факториалы:
Но предварительные комментарии о повторяющихся буквах обязательны!
Ответ : 554400
Другой типовой пример перестановок с повторениями встречается в задаче о расстановке шахматных фигур, которую можно найти на складе готовых решений в соответствующей pdf-ке. А для самостоятельного решения я придумал менее шаблонное задание:
Задача 13
Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?
Формула здесь не годится, поскольку учитывает совпадающие перестановки (например, когда меняются местами силовые упражнения в среду с силовыми упражнениями в четверг). И опять – по факту те же 2 силовые тренировки могут сильно отличаться друг от друга, но по контексту задачи (с точки зрения расписания) они считаются одинаковыми элементами.
Двухстрочное решение и ответ в конце урока.
Сочетания с повторениями
Характерная особенность этого вида комбинаций состоит в том, что выборка проводится из нескольких групп, каждая из которых состоит из одинаковых объектов.
Сегодня все хорошо потрудились, поэтому настало время подкрепиться:
Задача 14
В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести пять пирожков?
Решение : сразу обратите внимание на типичный критерий сочетаний с повторениями – по условию на выбор предложено не множество объектов как таковое, а различные виды объектов; при этом предполагается, что в продаже есть не менее пяти хот-догов, 5 ватрушек и 5 пончиков. Пирожки в каждой группе, разумеется, отличаются – ибо абсолютно идентичные пончики можно смоделировать разве что на компьютере =) Однако физические характеристики пирожков по смыслу задачи не существенны, и хот-доги / ватрушки / пончики в своих группах считаются одинаковыми.
Что может быть в выборке? Прежде всего, следует отметить, что в выборке обязательно будут одинаковые пирожки (т.к. выбираем 5 штук, а на выбор предложено 3 вида). Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пончика и т.д.
Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё.
Используем формулу 
количества сочетаний с повторениями:
способом можно приобрести 5 пирожков.
Приятного аппетита!
Ответ : 21
Какой вывод можно сделать из многих комбинаторных задач?
Порой, самое трудное – это разобраться в условии.
Аналогичный пример для самостоятельного решения:
Задача 15
В кошельке находится достаточно большое количество 1-, 2-, 5- и 10-рублёвых монет. Сколькими способами можно извлечь три монеты из кошелька?
В целях самоконтроля ответьте на пару простых вопросов:
1) Могут ли в выборке все монеты быть разными?
2) Назовите самую «дешевую» и самую «дорогую» комбинацию монет.
Решение и ответы в конце урока.
Из моего личного опыта, могу сказать, что сочетания с повторениями – наиболее редкий гость на практике, чего не скажешь о следующем виде комбинаций:
Размещения с повторениями
Из множества, состоящего из элементов, выбирается элементов, при этом важен порядок элементов в каждой выборке. И всё бы было ничего, но довольно неожиданный прикол заключается в том, что любой объект исходного множества мы можем выбирать сколько угодно раз. Образно говоря, от «множества не убудет».
Когда так бывает? Типовым примером является кодовый замок с несколькими дисками, но по причине развития технологий актуальнее рассмотреть его цифрового потомка:
Задача 16
Сколько существует четырёхзначных пин-кодов?
Решение : на самом деле для разруливания задачи достаточно знаний правил комбинаторики: способами можно выбрать первую цифру пин-кода и способами – вторую цифру пин-кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить: способами.
А теперь с помощью формулы. По условию нам предложен набор из цифр, из которого выбираются цифры и располагаются в определенном порядке
, при этом цифры в выборке могут повторяться (т.е. любой цифрой исходного набора можно пользоваться произвольное количество раз)
. По формуле количества размещений с повторениями: 
Ответ : 10000
Что тут приходит на ум… …если банкомат «съедает» карточку после третьей неудачной попытки ввода пин-кода, то шансы подобрать его наугад весьма призрачны.
И кто сказал, что в комбинаторике нет никакого практического смысла? Познавательная задача для всех читателей сайт:
Задача 17
Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами) .
Сколько различных номерных знаков можно составить для региона?
Не так их, кстати, и много. В крупных регионах такого количества не хватает, и поэтому для них существуют по несколько кодов к надписи RUS.
Решение и ответ в конце урока. Не забываем использовать правила комбинаторики;-) …Хотел похвастаться эксклюзивом, да оказалось не эксклюзивом =) Заглянул в Википедию – там есть расчёты, правда, без комментариев. Хотя в учебных целях, наверное, мало кто прорешивал.
Наше увлекательное занятие подошло к концу, и напоследок я хочу сказать, что вы не зря потратили время – по той причине, что формулы комбинаторики находят ещё одно насущное практическое применение: они встречаются в различных задачах по теории вероятностей
,
и в задачах на классическое определение вероятности
– особенно часто =)
Всем спасибо за активное участие и до скорых встреч!
Решения и ответы :
Задача 2: Решение
: найдём количество всех возможных перестановок 4 карточек:
Когда карточка с нулём располагается на 1-м месте, то число становится трёхзначным, поэтому данные комбинации следует исключить. Пусть ноль находится на 1-м месте, тогда оставшиеся 3 цифры в младших разрядах можно переставить способами.
Примечание
: т.к. карточек немного, то здесь несложно перечислить все такие варианты:
0579
0597
0759
0795
0957
0975
Таким образом, из предложенного набора можно составить:
24 – 6 = 18 четырёхзначных чисел
Ответ
: 18
Задача 4: Решение
: способами можно выбрать 3 карты из 36.
Ответ
: 7140
Задача 6: Решение
: 
способами.
Другой вариант решения
: способами можно выбрать двух человек из группы и
и
2) Самый «дешёвый» набор содержит 3 рублёвые монеты, а самый «дорогой» – 3 десятирублёвые.
Задача 17: Решение
: 
способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить: .
способами можно составить буквенную комбинацию автомобильного номера.
По правилу умножения комбинаций, всего можно составить:
автомобильных номера
(каждая
цифровая комбинация сочетается с каждой
буквенной комбинацией).
Ответ
: 1726272
Рассмотрим задачу подсчета числа выборок из данного множества в общем виде. Пусть имеется некоторое множество N , состоящее из n элементов. Любое подмножество, состоящее из m элементов можно рассматривать без учета их порядка, так и с его учетом, т.е. при изменении порядка переходим к другой m – выборке.
Сформулируем следующие определения:
Размещения без повторения
Размещением без повторения из n элементов по m N , содержащее m различных элементов .
Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.
Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:
Перестановки без повторений
Перестановками из n элементов называются различные упорядочения множества N .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Теорема 4 . Число различных перестановок без повторений вычисляется по формуле
Сочетания без повторений
Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.
Из определения следует, что два сочетания различаются только элементами, порядок не важен.
Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:
Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них
а) 7 человек; б) 5 человек; в) 3 человека?
Решение:
а) Прежде всего надо выбрать 5 человек
из 7 для посадки на стулья. Это можно
сделать
способом. С каждым выбором конкретной
пятерки можно произвести
перестановок местами. Согласно теореме
умножения искомое число способов посадки
равно.
Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как
б) Решение очевидно
-
в)
- число выборов занимаемых стульев.
- число размещений
трех человек на трех выбранных стульях.
Общее число выборов равно .
Не трудно проверить
формулы
;
;
Число всех подмножеств множества, состоящего из n элементов.
Размещения с повторением
Размещением с повторением из n элементов по m называется всякое упорядоченное подмножество множества N , состоящее из m элементов так, что любой элемент ожжет входить в это подмножество от 1 до m раз, либо вообще в нем отсутствовать .
Число
размещений с повторением обозначают
и вычисляют по формуле, представляющей
собой следствие из теоремы умножения:
Пример 2
.
Пусть дано множество из трех букв N
= {a,
b,
c}.
Назовем словом любой набор из букв,
входящих в это множество. Найдем
количество слов длиной 2, которые можно
составить из этих букв:
.
Замечание:
Очевидно, размещения с повторением
можно рассматривать и при
.
Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?
Ответ
:
Комбинаторика — раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям, можно составить из заданных объектов.
Комбинаторика возникла в 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 |
||||||||
| ... | ... | ... | ... | ... |
КОМБИНАТОРИКА
Комбинаторика - раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В - n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Решение
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n 1 способами, второе действие n 2 способами, третье - n 3 способами и так до k-го действия, которое можно выполнить n k способами, то все k действий вместе могут быть выполнены:
способами.
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Решение
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Решение
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Решение
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение.
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно вы б рать и разместить по m различным местам m из n предметов, с реди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера- составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Перестановки без повторений . Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Решение
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Решение
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ "КОМБИНАТОРИКА"
Большинство формул комбинаторики используют понятие факториала. Термин «факториал» произошел от латинского слова factor («производящий») и обозначает созвучное действие - произведение.
Определение 5.1. Произведение п первых последовательных натуральных чисел называется п-факториал.
Обозначение: п.
Единственная формула для вычисления факториалов, которая будет использоваться, выражает определение факториалов:
Например: 4! = 1 2 3 4 = 24.
Особо оговариваются частные случаи значения факториала: 0! = 1 и 1! = 1.
Многие творчески настроенные студенты пытаются использовать собственные формулы для вычисления факториала, что приводит к ошибкам. Стоит напомнить, что факториал разности не равен разности факториалов и, соответственно, сначала следует выполнять действие в скобках, а потом от результата брать факториалы.
Например: (3 - 2)! = 1! = 1. Ошибочно выполнять действия в ином порядке: 3! - 2! = 1 - 2*3-1-2 = 6- 2 = 4. Как видим 4 Ф 1 и, соответственно, (3 - 2)! Ф 3! - 2!.
Сокращать факториалы в дробном выражении можно, но тоже осторожно.
Если надо поделить факториал большого числа на факториал другого большого числа, то выгодно расписать произведение натуральных чисел в укороченном виде. Для этого надо понимать, что факториал является просто другой короткой формой записи особого произведения. А одну форму записи можно заменить на другую, где бы она ни встречалась. Например:
По основному, всеми любимому свойству дроби одинаковые множители в числителе и знаменателе можно сокращать, в каком бы виде они ни выражались, в том числе и через факториалы. Зная, что внутри любого произведения п первых последовательных натуральных чисел будет содержаться более короткий ряд сомножителей, на который предстоит поделить, сократив одинаковые множители, можно сразу записывать только оставшийся «хвостик» произведения, причем уже без знаков факториала.
Уже не ошибки, но трудности возникают иногда, когда приходится оперировать буквенными выражениями с факториалами. В связи с этим стоит осмыслить следующий факт. Каждый сомножитель в записи значения факториалов отличается от предыдущего на единицу. Поэтому число, стоящее в таком произведении перед множителем п, имеет вид (п - 1), а перед ним стоит число вида (п - 2). Значит, при необходимости п можно записать, например, в таком виде: п = 1 2 3 ... (п - 2) (п - 1) п = (п - 2)! (п - 1) п.
Дальнейший текст надо прочесть и разобраться в приведенных обоснованиях, но запоминать их необязательно. Для людей, не занимающихся математикой, а только нуждающихся в использовании ее результатов для обработки информации в своей области знаний, будет предложен способ систематизации основных понятий и формул комбинаторики, а также поиска нужной математической модели для решения комбинаторной задачи. Однако без понимания сути комбинирования разных видов труднее будет пользоваться схемой поиска решения комбинаторных задач.
Не приводя строгих доказательств, посмотрим, как можно подметить закономерности при подсчете количества комбинаций разных видов. Комбинировать элементы исходного множества можно двумя принципиально отличными способами: используя в каждой комбинации только различные элементы или допуская повторение одних и тех же элементов в комбинации. В первом случае, выбрав из множества в подмножество элемент, повторно его уже использовать нельзя, так как он уже удален из исходного множества. При втором способе выбора допускается, что один и тот же элемент может быть использован несколько раз. Сначала напомним первый способ составления комбинаций, не допускающий повторения одних и тех же элементов в одной комбинации.
Пример 5.5
В семье четыре ребенка: Аия, Боря, Ваня, Галя. Они постоянно спорят между собой за лучшее место в машине, в кино, за столом. Родители, устав от разборок, постановили, что каждый следующий раз дети садятся по-разному. Через сколько раз придется повторить рассадку?
Решение
Пока детей было двое, то возможны были только две комбинации: А - Б, Б - А.
Когда подрос Ваня, его можно было разместить на трех местах но отношению к каждой из этих комбинаций: по бокам и между старшими детьми.
Для комбинации А - Б возможны три варианта: В - А - Б, А - Б - В, А-В - Б, и для комбинации Б - Л есть еще три варианта: В - Б - Л, Б - Л - В, Б - В - Л.
Всего два раза по три новые комбинации, что соответствует действию умножения 2 3.
Когда детей стало четыре, то по отношению к каждой из предыдущих (2 *3) = = 6 комбинаций четвертого ребенка можно было опять-таки разместить по бокам или на одном из двух мест между старшими тремя детьми, т.е. на одном из четырех мест. Например, для комбинации В - А - Б получится четыре новые комбинации:
Таким образом, вместо каждой из предыдущих (2 3) комбинаций получится четыре новые комбинации. Всего надо взять (2 - 3) раз по 4, что соответствует действию умножения: (2 3) 4, или можно записать 1 *2-3*4 = 4!.
Ответ : 24 раза.
Если же в описанной в примере семье появится пятый ребенок, то его можно уже будет посадить на одно из пяти мест: два но бокам и на три пропуска между старшими детьми, т.е. получится (1 *2*3* 4) *5 = 5! комбинаций и т.д.
В приведенном примере шла речь о том, как по-разному можно расположить п элементов, и получили ответ - п комбинаций. Такие комбинации называются перестановками.
Определение 5.2. Множества, отличающиеся от исходного множества порядком расположения его элементов, называются перестановками.
Обозначение: Р п.
Утверждение 5.1. Число перестановок определяется по формуле Р п = п.
Теперь, после обоснования подсчета числа перестановок, естественно принять, что 0! = 1 и 1! = 1, поскольку одноэлементное и пустое множество можно представить (упорядочивай, не упорядочивай) только в одном виде.
Определение 5.3. Упорядоченные m-элементные подмножества данного множества из п элементов называются размещениями из п элементов по т.
Обозначение: А™, где п > т.
Чтобы обосновать выведение формулы для подсчета числа размещений, рассмотрим следующий пример.
Пример 5.6
Сколько различных трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5 и 6, если цифры в записи числа не могут повторяться?
Решение
В данной задаче речь идет о подсчете количества упорядоченных трехэлементных подмножеств множества из шести элементов, т.е. о числе размещений.
На первое место в числе можно поставить любую из шести доступных цифр, при этом пустыми останутся два разряда в записи числа. Претендентами на вторые места в каждом из шести случаев будут уже не 6, а 5 оставшихся цифр. В каждом из шести случаев это будут, конечно, разные цифры, но нам не важно, какие именно цифры. В комбинаторике достаточно учитывать количество доступных для выбора элементов. В результате, приставив к каждой из первых шести цифр по одной из оставшихся пяти цифр, получим уже 6 раз по 5 наборов цифр, т.е. (6 5) наборов. В каждом из этих (6-5) наборов осталось одно неиспользованное место, на которое можно поставить по одной из оставшихся четырех цифр. Получится (6 5) раз но 4 варианта, т.е. (6-5-4) комбинаций.
Ответ : 120 чисел.
Легко заметить, что при такой процедуре в ответе получается произведение чисел, уменьшающихся на единицу. В общем случае при выборе из п элементов это произведение выглядит так: п (п - 1) (п - 2) ... . Таких сомножителей должно быть т , по числу мест в каждой комбинации. Последний сомножитель в общем виде представить сложнее, но достаточно внимательно проанализировать полученное произведение. В каждом сомножителе вычитаемое на единицу больше, чем в предыдущем множителе. Поскольку начинается произведение фактически с вычитания нуля, а всего в произведении т разностей, то последнее уменьшаемое равно (т - 1). Так, обработав информацию при помощи нахождения сходств и различий в полученных выражениях, можно получить общий ответ о числе комбинаций при данной выборке: п (п - 1) ... [п - (т - 1)].
Утверждение 5.2. Число размещений определяется по формулам
Обоснование. В первой формуле расписаны «почти 77!», но без первых сомножителей из (77-777)!. Во второй формуле из факториала убраны первые сомножители из (77-777)! при помощи деления.
Замечание. Л" = Р п, если 77 = 777.
Если не повторять каждый раз все рассуждения, а пользоваться готовой формулой (5.1), то решение примера 5.6 выглядит так: число элементов в исходном множестве п = 6, /7? = 3, упорядоченность записи элементов в подмножестве - важна. Тогда
Рассмотрим другую, но очень похожую задачу: сколько различных произведений из трех различных множителей можно составить, взяв в качестве множителей числа 1, 2, 3, 4, 5, 7?
Отличие в процедуре составления данных комбинаций состоит в том, что не надо учитывать порядок расположения элементов в подмножествах, так как от перестановки мест сомножителей произведение не меняется. Подобные комбинации называются сочетаниями.
Определение 5.4. Неупорядоченное т/7-элементное подмножество данного множества из п элементов называется сочетанием из п элементов
ПО 777.
Обозначение: С" 7 , где п > т.
Утверждение 5.3. Число сочетаний определяется по формуле
Обоснование. Неупорядоченных подмножеств из т элементов будет меньше, чем упорядоченных т -элементных подмножеств того же множества, во столько раз, сколько существует перестановок внутри каждого набора из т зафиксированных элементов. Уменьшение в несколько раз соответствует действию деления, поэтому
Довольно долго и достаточно подробно мы рассматривали три вида комбинаций первого, бесповторного способа их составления. Чтобы использовать эту информацию, необходимо представить ее в компактном виде. Для этого еще раз используем такой способ обработки информации, как нахождение сходств и различий в трех определениях и табличный способ представления информации. Такой анализ информации позволит выделить три параметра, определяющих подсчет количества комбинаций без повторов: число элементов в исходном множестве п, число элементов в подмножестве т , наличие упорядоченности в подмножествах. Отличия в составлении комбинаций наблюдается по двум вопросам:
- наличие совпадения числа элементов в множестве и числа элементов в подмножестве;
- отличие подмножеств друг от друга по порядку записи элементов.
Теперь можно организовать выбор математической модели - формулы - для подсчета числа комбинаций в виде таблицы (табл. 5.2).
Таблица 5.2
Выбор формул для подсчета комбинаций без повторений
В этой таблице явно не хватает сочетания ответов «да - нет»: количество элементов в исходном множестве и в составляемом подмножестве совпадает и не надо учитывать порядок записи элементов в подмножестве. На прямой вопрос о количестве способов выбора пяти юношей из пяти имеющихся юношей в группе без учета порядка все отвечают правильно: 1, но очень часто встречаются ошибки при поверхностном формальном использовании таблицы.
Есть еще одна проблема, связанная с использованием таблицы: трудность определения необходимости упорядоченности подмножеств. Первоначально не осознавая важности этого вопроса и не уделяя ему должного внимания, в дальнейшем многие студенты делают ошибки, причины которых связаны именно с определением наличия упорядоченности в составляемых комбинациях. На материале комбинаторики проявляется мотив изучения этого свойства множеств, его роль. В силу его важности необходима актуализация знаний об упорядоченных множествах именно на этом этапе.
Нумерованная упорядоченность вызывает меньше трудностей в ее определении. Например, очередь из бабушек, у которых на ладошке записан номер их в очереди, чтобы, отойдя подышать воздухом, отдохнуть на скамеечке, они не перепутали свою очередь, выстроившись перед заветной целью в установленном порядке. Иерархическая упорядоченность вызывает большие затруднения. Если в тексте определены разные должности или функции для выбираемых элементов, то таким образом устанавливается требование упорядоченности для составляемых в сюжете комбинаций.
Помогают смягчить трудности в определении иерархической упорядоченности ролевые игры. Они опять-таки реализуют прием представления себя участником описываемых событий. Например, здесь стоит вспомнить организацию классных часов, а именно, школьного самоуправления, которым придется заниматься будущим учителям.
Представляем, как ведущий классного часа предлагает выбрать старосту класса, ответственного за дежурство по школе, за стенгазету, за организацию турпоходов, за культурную программу, подготовку всевозможных предметных недель и записывает на доске много всяких должностей, чтобы заинтересовать учащихся выбором наиболее адекватной должности, подавив позицию «лишь бы не меня». После опубликования должностей ведущий начинает собирать предложения, учитывает самоотводы и переходы на более предпочтительные должности. В результате на доске может оказаться несколько столбцов - списков фамилий, некоторые из которых будут отличаться не самими фамилиями, а лишь порядком их записи в соответствующем столбце. Далее начинается голосование, которое может собрать разное количество голосов под списками актива класса, отличающимися друг от друга только по порядку записи одних и тех же фамилий, но на разные должности. Разное количество голосов убеждает, что это были разные выборки, разные комбинации, пусть и из одинаковых фамилий, но по-разному упорядоченных. В связи с этим лучше ставить вопрос об упорядоченности подмножеств в алгоритме решения комбинаторных задач в следующей форме: «Могут ли отличаться подмножества друг от друга не только по содержанию, но и по порядку записи элементов?»
Определение требования упорядоченности подмножеств смущает студентов или, наоборот, преждевременно радует еще и тогда, когда в тексте фигурирует слово «порядок». Например, учитель берет коробку, в которой лежат пятнадцать карточек с буквами. Он достает из коробки по четыре карточки и раскладывает их ряд в алфавитном порядке. Требуется ли в данном сюжете упорядоченность выбираемых подмножеств? Обычно обязательно среди ответов присутствует радостное «Да!». Написано же, что есть алфавитный порядок в выбираемых четверках. Здесь выручает приведенная формулировка вопроса об упорядоченности. Среди выбранных четверок не будет наборов из одинаковых букв, но расположенных в разном порядке. Значит, подмножества не будут отличаться друг от друга по порядку записи элементов в них. Наборов будет столько же, сколько было бы, если бы их не выкладывали в ряд, а раскладывали бы по мешочкам, внутри которых между элементами порядка не будет. Такое количественное осмысление вопроса об упорядоченности элементов в комбинациях очень важно для комбинаторики.
При овладении умением определять упорядоченность составляемых комбинаций эффективна бывает организация обсуждения следующего вопроса: «Упорядоченных или неупорядоченных подмножеств получится больше, если выбирать парочки из студентов, сидящих на занятии?» Прежде всего и всегда присутствуют неправильные ответы. Только понимание того, что на каждую неупорядоченную парочку придутся две упорядоченные пары, отличающиеся друг от друга только порядком записи фамилий, приводит к оптимистичному убеждению: «Упорядоченных больше».
Пример 5.7
Из десяти студентов нужно выбрать троих для работы в приемной комиссии с абитуриентами. Сколько комбинаций надо рассмотреть, чтобы сделать полный перебор вариантов?
Решение
Этап 1. Краткая словесная (вербальная) обработка: например, «выбрать три студента из десяти студентов».
Этап 2. Полная запись условия на языке математических символов.
Для реализации этого этапа работы над комбинаторной задачей необходимо знание символики комбинаторики и умение определять наличие такого свойства множеств, как их упорядоченность. Поэтому предлагается следующая заготовка для символьной обработки текста с целью решения комбинаторных задач.
Дано: п =...; т =...;
порядок: да /нет.
Для примера 5.8 эта заготовка заполнится следующим образом:
Дано: п = 10; т = 3;
порядок: нет.
На основе этой заготовки и табл. 5.2 выбор необходимой для решения задачи математической модели выполняется легко.
Поскольку в данном условии число элементов в множестве и подмножестве нс равны (/? Ф т ), то на два вопроса таблицы ответы: «нет - нет». В соответствующей строке таблицы находится формула для подсчета числа сочетаний из п элементов по т. Таким образом, запись решения задачи в целом будет выглядеть так:
«Выбрать три студента из десяти студентов».
Дано: п - 10; т = 3;
порядок: нет.
Ответ: 120 комбинаций надо рассмотреть, чтобы сделать полный перебор вариантов.
Для более продвинутых пользователей табл. 5.2 можно расширить, добавив еще один параметр - повторное использование элементов в подмножестве (табл. 5.3).
Таблица 53
Выбор формул для подсчета всех возможных комбинаций
|
Комбинации |
Подмножества могут отличаться но порядку элементов? |
Возможно повторное использование элементов в подмножествах? |
||
|
Перестановки |
Р п = п |
|||
|
Размещения |
а;:,= |
|||
|
Сочетания |
ш (п-т)т! |
|||
|
Размещения с повторениями |
А„ = и"" |
|||
|
Сочетания с повторениями |
W _ (//2-1-/7-1)! " ~т!-(л- 1)! |
|||
|
Перестановки с повторениями |
k Jповторов
k n повторов /7-го элемента. |
Pn(k t,&2,= п V- k 2 ! *„! |
Принцип выбора математической модели по табл. 5.3 аналогичен показанному в примере 5.7. Некоторые затруднения могут возникнуть с конкретизацией формулы для подсчета числа перестановок с повторениями. Поэтому рассмотрим подробнее пример ее использования.
Пример 5.8
Дети любят играть в игры со словами, в частности составлять слова из букв загаданного слова. Выигрывает тот, кто составит больше слов с наибольшим количеством букв. Для простоты предположим, что загадано слово «гагара». Чтобы не упустить выгодные длинные варианты, посчитаем, сколько шестибуквенных комбинаций из букв слова «гагара» в принципе можно составить.
Решение
Этап 1: «Выбрать шесть букв из шести букв».
Дано: п = 6; т = 6;
порядок: да;
повтор: да, к а = 3, к г = 2, k ? = 1
Поскольку на три вопроса таблицы ответ «да», то выбираем математическую модель с использованием подсчета числа перестановок с повторениями. Элемент «а» повторяется в исходном множестве три раза, а значит, и в шестиэлементных комбинациях повторно будет использоваться три раза. Аналогично элемент «р» имеет количество повторов, равное двум. Далее - самое простое. Поскольку математическая модель выбрана, остается правильно подставить значения неизвестных в формулу и выполнить необходимые вычисления:
Ответ : 60.
Вид формулы для подсчета числа перестановок с повторениями легко обосновать. Если бы все шесть букв были разные, то количество перестановок равнялось бы 6!. Но если в подмножествах могут фигурировать, например, три одинаковые буквы, то неважно, какая из этих одинаковых букв на каком месте, отведенном для этих букв, находится. А это значит, что количество перестановок с повторениями будет меньше количества бес- повторных перестановок во столько раз, сколько перестановок одинаковых элементов можно сделать, т.е. в /^-факториал раз. Поэтому в формуле числа перестановок с повторениями появился знаменатель в отличие от формулы бесповторных перестановок.
