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

Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью тервера) и по данной дисциплине написаны увесистые учебники, содержание которых, порой, ничуть не легче абстрактной алгебры. Однако нам будет достаточно небольшой доли теоретических знаний, и в данной статье я постараюсь в доступной форме разобрать основы темы с типовыми комбинаторными задачами. А многие из вас мне помогут;-)

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

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

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

Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, … нет, кашу с паяльником и лягушкой предлагать не буду, лучше что-нибудь повкуснее =) Представьте, что перед вами на столе материализовалось яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке:

яблоко / груша / банан

Вопрос первый : сколькими способами их можно переставить?

Одна комбинация уже записана выше и с остальными проблем не возникает:

яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко

Итого : 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

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

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

Пусть имеется 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. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com

Подписи к слайдам:

Элементы комбинаторики Никандрова И.А. МБОУ «Лицей 10» г. Великие Луки

Примеры комбинаторных задач Задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций, называются комбинаторными Раздел математики, в котором рассматриваются подобные задачи, называют комбинаторикой Слово «комбинаторика» от латинского combinare - «соединять, сочетать»

Пример 1 Из группы теннисистов, в которую входят четыре человека-Антонов, Григорьев, Сергеев и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары? АГ, АС, АФ ГС, ГФ СФ Значит, всего существует шесть вариантов выбора Способ рассуждений, которым мы воспользовались, называют перебором возможных вариантов

Пример 2 Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7 ,используя в записи числа каждую из них не более одного раза? Чтобы ответить на вопрос задачи, выпишем все такие числа. Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел: 135 137 153 157 173 175 315 317 351 357 371 375 513 517 531 537 571 573 713 715 731 735 751 753

Способ второй Проведенный перебор вариантов проиллюстрирован на схеме Такую схему называют деревом возможных вариантов

Способ третий Первую цифру можно выбрать четырьмя способами. Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать уже тремя способами. Наконец, третью цифру можно выбрать двумя способами. Следовательно, общее число искомых чисел равно произведению 4*3*2,т.е.24 Использовалось комбинаторное правило умножения: Пусть имеется п элементов и требуется выбрать из них один за другим k элементов. Если первый элемент можно выбрать п1 способами, после чего второй элемент можно выбрать п2 способами из оставшихся, затем третий элемент можно выбрать п3 способами из оставшихся и т. д., то число способов, которыми могут быть выбраны все k элементов, равно произведению п1 · п2 · п2 · … · пk .

Пример 3 Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани-две дороги. Туристы хотят проехать из города А через В и С к пристани. Сколькими способами они могут выбрать маршрут? Решение: 2*3*2=12

Задачи 1. В кафе предлагают два первых блюда:борщ, рассольник-и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель. Построить дерево возможных вариантов 2. Стадион имеет четыре входа: А, В, С, D . Укажите все возможные способы, какими посетитель может войти через один вход, а выйти через другой. Сколько таких способов? Ответ:12 способов 3. Используя цифры 0,2,4,6 составьте все возможные трехзначные числа, в которых цифры не повторяются.

Задачи 4. В шахматном турнире участвуют 9 человек. Каждый из них сыграл с каждым по одной партии. Сколько всего партий было сыграно? Ответ:36 партий 5. При встрече 8 человек обменялись рукопожатиями. Сколько всего было сделано рукопожатий? Ответ:28 рукопожатий 6. Учащиеся 9 класса решили обменяться фотографиями. Сколько фотографий для этого потребуется, если в классе 24 учащихся? Ответ:552 фотографии

Задачи 7. В кафе имеются три первых блюда, пять вторых блюд и два третьих. Сколькими способами посетитель кафе может выбрать обед, состоящий из первого, второго и третьего блюд? Ответ:30 способов 8. Петр решил пойти на новогодний карнавал в костюме мушкетера. В ателье проката ему предложили на выбор различные по фасону и цвету предметы: пять видов брюк, шесть камзолов, три шляпы, две пары сапог. Сколько различных карнавальных костюмов можно составить из этих предметов? Ответ:180 костюмов

Перестановки Простейшими комбинациями, которые можно составить из элементов конечного множества, являются перестановки Число перестановок из n элементов обозначают символом Р n(читается «Р из n ») Для произведения первых n натуральных чисел используют специальное обозначение: n! (читается n факториал) 2!=2; 5!=120; 1!=1

Примеры задач Таким образом, число всевозможных перестановок из n элементов вычисляется по формуле: Р n = n ! Пример 1 . Сколькими способами могут быть расставлены 8 участниц финального забега на восьми беговых дорожках? Р 8 =8!=40320 Пример 2 . Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6? Из цифр 0,2,4,6 можно получить Р 4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0.Получаем: Р 4 -Р 3 =4!-3!=18

Пример 3. Имеется 9 различных книг, четыре из которых- учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом? Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 9,а 6 книг. Это можно сделать Р 6 способами. В каждой из полученных комбинаций можно выполнить Р 4 перестановок учебников. Значит, искомое число способов расположения книг на полке равно произведению Р 6 *Р 4 . Получаем: Р 6 *Р 4 =6!*4!=720*24=17280

Задачи 1. Сколькими способами 4 человека могут разместиться на четырехместной скамейке? Ответ:24 2. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать? Ответ:5040 3. Сколько шестизначных чисел(без повторения цифр) можно составить из цифр: а)1,2,5,6,7,8; б)0,2,5,6,7,8 ? Ответ: а)720;б)600 4. В расписании на понедельник шесть уроков:алгебра,геометрия,биология,история,физкультура,химия.Сколькими способами можно составить расписание уроков на этот день так, чтобы два урока математики стояли рядом? Ответ:240

Задачи 5. Делится ли число 14! На: А)168; б)136;в)147;г)132? 6. 7. Ответ на 6) :15; 1 /90 ; 1722; 40

Проверочная работа 1 вариант 2 вариант 1. Комбинаторные задачи 2. Способы решения комбинаторных задач 3. Вычислить 1. Перестановки, формула 2. Комбинаторика 3.Вычислить

Размещения Пусть имеется 4 шара и 3 пустых ячейки. В пустые ячейки можно по-разному разместить три шара из этого набора шаров. Выбирая разными способами первый, второй и третий шары, будем получать различные тройки шаров. Каждую упорядоченную тройку, которую можно составить из четырех элементов, называют размещением из четырех элементов по три Размещением из n элементов по к (к

П римеры 1. Учащиеся второго класса изучают 8 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предмета? В этом примере речь идет о размещениях из 8 элементов по 4. Имеем: 2. Сколько трехзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5,6? Среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому:

Задачи 1. Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет? Ответ: 24 2. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать? Ответ: 870 3. Сколькими способами организаторы конкурса могут определить, кто из 15 его участников будет выступать первым, вторым и третьим? Ответ: 2730 4. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а)2 фотографии; б) 4 фотографии; в) 6 фотографий? Ответ: 30;360;720

Сочетания Сочетанием из n элементов по к называется любое множество, составленное из данных n элементов В отличие от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы.Два сочетания из элементов по к отличаются друг от друга хотя бы одним элементом Обозначают Читают «С из n по к» Формула числа сочетаний из n элементов по к,где к

Примеры 1. Из 15 членов туристической группы надо выбрать трех дежурных. Сколькими способами можно сделать этот выбор? Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идет о сочетаниях из 15 элементов по 3 Имеем: 2. Из вазы с фруктами, в которой лежит 9 яблок и 6 груш, надо выбрать 3 яблока и 2 груши. Сколькими способами можно сделать такой выбор? Имеем:

Задачи 1. В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде? Ответ:21 2. Учащимся дали список из 10 книг, которые рекомендуется прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг? Ответ:210 3. В классе учатся 16 мальчиков и 12 девочек. Для уборки территории требуется выделить четырех мальчиков и трех девочек. Сколькими способами это можно сделать? Ответ:400400 4. В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала? Ответ:720

Самостоятельная работа 1 вариант 1. Сколькими способами 9 участников конкурса могут выступить в порядке очередности в финале? 2. Делится ли число 40! н а: а)410;б)500;в)780? 3. Используя цифры 0,3,7,8 составьте все возможные двузначные числа, в которых цифры не повторяются 4. В городской думе 10 депутатов моложе 30 лет. Сколькими способами можно выбрать из них троих для работы в комитете по молодежной политике? 2 вариант 1. Курьер должен развести пиццу по шести адресам. Сколько маршрутов он может выбрать? 2. Делится ли число 50! н а: а)400;б)98;в)510? 3. Используя четные цифры 0,2,4,6,8, составьте все возможные трехзначные числа, в которых цифры не повторяются 4. В группе 9 студентов хорошо владеют иностранным языком. Сколькими способами можно выбрать из них четверых для работы на практике с иностранцами?

Ответы 1 вариант 1. 9!=362880 2. а) нет б) да в) да 3. 30 70 80 37 73 83 38 78 87 4. 120 2 вариант 1. 6!=720 2. а) да б) да в) да 3. 48 чисел 4. 126

КОМБИНАТОРИКА

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

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

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить 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), т. е. есть одинаковые предметы.