Реклама на портале

Количество перестановок из n по m. Комбинаторика

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

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

Комбинаторные конфигурации

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

  • размещение;
  • перестановка;
  • сочетание;
  • композиция числа;
  • разбиение числа.

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

Разделы

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

  • перечислительная;
  • структурная;
  • экстремальная;
  • теория Рамсея;
  • вероятностная;
  • топологическая;
  • инфинитарная.

В первом случае речь идет об исчисляющей комбинаторике, задачи рассматривают перечисление или подсчет разных конфигураций, которые образованы элементами множеств. На данные множества, как правило, накладываются какие-либо ограничения (различимость, неразличимость, возможность повтора и так далее). А количество этих конфигураций подсчитывается при помощи правила сложения или умножения, о которых мы поговорим немного позже. К структурной комбинаторике относятся теории графов и матроидов. Пример задачи экстремальной комбинаторики - какова наибольшая размерность графа, который удовлетворяет следующим свойствам… В четвертом пункте мы упомянули теорию Рамсея, которая изучает в случайных конфигурациях наличие регулярных структур. Вероятностная комбинаторика способна нам ответить на вопрос - какова вероятность того, что у заданного множества присутствует определенное свойство. Как нетрудно догадаться, топологическая комбинаторика применяет методы в топологии. И, наконец, седьмой пункт - инфинитарная комбинаторика изучает применение методов комбинаторики к бесконечным множествам.

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

Среди формул комбинаторики можно найти и довольно простые, с которыми мы достаточно давно знакомы. Примером является правило суммы. Предположим, что нам даны два действия (С и Е), если они взаимоисключаемы, действие С выполнимо несколькими способами (например а), а действие Е выполнимо b-способами, то выполнить любое из них (С или Е) можно а+b способами.

В теории это понять достаточно трудно, постараемся донести всю суть на простом примере. Возьмем среднюю численность учеников одного класса - допустим, это двадцать пять. Среди них пятнадцать девочек и десять мальчиков. Ежедневно в классе назначается один дежурный. Сколько есть способов назначить дежурного по классу сегодня? Решение задачи достаточно простое, мы прибегнем к правилу сложения. В тексте задачи не сказано, что дежурными могут быть только мальчики или только девочки. Следовательно, им может оказаться любая из пятнадцати девочек или любой из десяти мальчиков. Применяя правило суммы, мы получаем достаточно простой пример, с которым без труда справится школьник начальных классов: 15 + 10. Подсчитав, получаем ответ: двадцать пять. То есть существует всего двадцать пять способов назначить на сегодня дежурного класса.

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

К основным формулам комбинаторики относится и правило умножения. Начнем с теории. Допустим, нам необходимо выполнить несколько действий (а): первое действие выполняется с1 способами, второе - с2 способами, третье - с3 способами и так далее до последнего а-действия, выполняемого са способами. Тогда все эти действия (которых всего у нас а) могут быть выполнены N способами. Как высчитать неизвестную N? В этом нам поможет формула: N = с1 * с2 * с3 *…* са.

Опять же, в теории ничего не понятно, переходим к рассмотрению простого примера на применение правила умножения. Возьмем все тот же класс из двадцати пяти человек, в котором учится пятнадцать девочек и десять мальчиков. Только на этот раз нам необходимо выбрать двух дежурных. Ими могут быть как только мальчики или девочки, так и мальчик с девочкой. Переходим к элементарному решению задачи. Выбираем первого дежурного, как мы решили в прошлом пункте, у нас получается двадцать пять возможных вариантов. Вторым дежурным может быть любой из оставшихся человек. У нас было двадцать пять учеников, одного мы выбрали, значит вторым дежурным может быть любой из оставшихся двадцати четырех человек. Наконец, применяем правило умножения и получаем, что двоих дежурных можно избрать шестью сотнями способов. Мы данное число получили умножением двадцати пяти и двадцати четырех.

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

Сейчас мы рассмотрим еще одну формулу комбинаторики. В данном разделе статьи мы поговорим о перестановках. Рассмотреть проблему предлагаем сразу же на примере. Возьмем бильярдные шары у нас их n-ое количество. Нам нужно подсчитать: сколько есть вариантов расставить их в ряд, то есть составить упорядоченный набор.

Начнем, если у нас нет шаров, то и вариантов расстановки у нас так же ноль. А если у нас шар один, то и расстановка тоже одна (математически это можно записать следующим образом: Р1 = 1). Два шара можно расставить двумя разными способами: 1,2 и 2,1. Следовательно, Р2 = 2. Три шара можно расставить уже шестью способами (Р3=6): 1,2,3; 1,3,2; 2,1,3; 2,3,1; 3,2,1; 3,1,2. А если таких шаров не три, а десять или пятнадцать? Перечислять все возможные варианты очень долго, тогда нам на помощь приходит комбинаторика. Формула перестановки поможет нам найти ответ на интересующий нас вопрос. Pn = n *P (n-1). Если попытаться упростить формулу, то получаем: Pn = n* (n - 1) *…* 2 * 1. А это и есть произведение первых натуральных чисел. Такое число называется факториалом, а обозначается как n!

Рассмотрим задачу. Вожатый каждое утро выстраивает свой отряд в шеренгу (двадцать человек). В отряде есть три лучших друга - Костя, Саша и Леша. Какова вероятность того, что они будут стоять рядом? Чтобы найти ответ на вопрос, нужно вероятность «хорошего» исхода поделить на общее количество исходов. Общее число перестановок составляет 20! = 2,5 квинтиллиона. Как посчитать количество «хороших» исходов? Предположим, что Костя, Саши и Леша - это один сверхчеловек. Тогда мы имеем всего восемнадцать субъектов. Число перестановок в данном случае равняется 18 = 6,5 квадриллионов. При всем этом, Костя, Саша и Леша могут произвольно перемещаться между собой в своей неделимой тройке, а это еще 3! = 6 вариантов. Значит всего «хороших» расстановок у нас 18! * 3! Нам остается только найти искомую вероятность: (18! * 3!) / 20! Что равняется примерно 0,016. Если перевести в проценты, то это получается всего 1,6%.

Размещение

Сейчас мы рассмотрим еще одну очень важную и необходимую формулу комбинаторики. Размещение - это наш следующий вопрос, который предлагаем вам рассмотреть в данном разделе статьи. Мы идем на усложнение. Предположим, что мы хотим рассмотреть возможные перестановки, только не из всего множества (n), а из меньшего (m). То есть мы рассматриваем перестановки из n предметов по m.

Основные формулы комбинаторики стоит не просто заучивать, а понимать их. Даже несмотря на то, что они усложняются, так как у нас не один параметр, а два. Предположим, что m = 1, то и А = 1, m = 2, то А = n * (n - 1). Если далее упрощать формулу и перейти на запись при помощи факториалов, то получится вполне лаконичная формула: А = n! / (n - m)!

Сочетание

Мы рассмотрели практически все основные формулы комбинаторики с примерами. Теперь перейдем к заключительному этапу рассмотрения базового курса комбинаторики - знакомство с сочетанием. Сейчас мы будем выбирать m предметов из имеющихся у нас n, при этом всем мы будем выбирать всеми возможными способами. Чем же тогда это отличается от размещения? Мы не будем учитывать порядок. Этот неупорядоченный набор и будет являться сочетанием.

Сразу введем обозначение: С. Берем размещения m шариков из n. Мы перестаем обращать внимание на порядок и получаем повторяющиеся сочетания. Чтобы получить число сочетаний нам надо поделить число размещений на m! (m факториал). То есть С = А / m! Таким образом, способов выбрать из n шаров немножко, равняется примерно столько, сколько выбрать почти все. Этому есть логическое выражение: выбрать немножко все равно, что выкинуть почти все. Еще в данном пункте важно упомянуть и то, что максимальное число сочетаний можно достигнуть при попытке выбрать половину предметов.

Как выбрать формулу для решения задачи?

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

  1. Задайте себе вопрос: порядок размещения элементов учитывается в тексте задачи?
  2. Если ответ нет, то воспользуйтесь формулой сочетания (С = n! / (m! * (n - m)!)).
  3. Если ответ нет, то необходимо ответить на еще один вопрос: все ли элементы входят в комбинацию?
  4. Если ответ да, то воспользуйтесь формулой перестановки (Р = n!).
  5. Если ответ нет, то воспользуйтесь формулой размещения (А = n! / (n - m)!).

Пример

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

Вопрос первый: сколькими способами их можно переставить? Для этого воспользуемся формулой перестановок: Р = 3! = 6 способов.

Вопрос второй: сколькими способами можно выбрать один фрукт? Это очевидно, у нас всего три варианта - выбрать киви, апельсин или банан, но применим формулу сочетаний: С = 3! / (2! * 1!) = 3.

Вопрос третий: сколькими способами можно выбрать два фрукта? Какие есть у нас вообще варианты? Киви и апельсин; киви и банан; апельсин и банан. То есть три варианта, но это легко проверить при помощи формулы сочетания: С = 3! / (1! * 2!) = 3

Вопрос четвертый: сколькими способами можно выбрать три фрукта? Как видно, выбрать три фрукта можно одним-единственным способом: взять киви, апельсин и банан. С = 3! / (0! * 3!) = 1.

Вопрос пятый: сколькими способами можно выбрать хотя бы один фрукт? Это условие подразумевает, что мы можем взять один, два или все три фрукта. Следовательно, мы складываем С1 + С2 + С3 =3 + 3 + 1 = 7. То есть у нас есть семь способов взять со стола хотя бы один фрукт.

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

Рождение комбинаторики как раздела математикисвязано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) - немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

В дальнейшем важную роль будет играть следующая

Лемма. Пусть в множестве элементов, а в множестве-элементов. Тогда число всех различных пар, гдебудет равно.

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

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

Пусть у нас есть множество из трех элементов . Какими способами мы можем выбрать из этих элементов два?.

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

Число всех размещений множества из элементов поэлементов обозначается через(от начальной буквы французского слова “arrangement”, что означает размещение), гдеи.

Теорема. Число размещений множества из элементов поэлементов равно

Доказательство. Пусть у нас есть элементы . Пусть- возможные размещения. Будем строить эти размещения последовательно. Сначала определим- первый элемент размещения. Из данной совокупностиэлементов его можно выбратьразличными способами. После выбора первого элементадля второго элементаостаетсяспособов выбора и т.д. Так как каждый такой выбор дает новое размещение, то все эти выборы можно свободно комбинировать между собой. Поэтому имеем:

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

Решение. Искомое число трехполосных флагов:

Определение. Перестановкой множества из элементов называется расположение элементов в определенном порядке.

Так, все различные перестановки множества из трех элементов - это

Число всех перестановок из элементов обозначается(от начальной буквы французского слова “permutation”, что значит “перестановка”, “перемещение”). Следовательно, число всех различных перестановок вычисляется по формуле

Пример. Сколькими способами можно расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

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

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

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

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

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

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

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

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

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

Итого : 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 по k n k различными координатами.

Число размещений без повторений находится по формуле:

Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?

Количество цифр
, размерность вектора с различными координатами

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

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

Число размещений с повторениями находится по формуле:

.

Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?

Количество букв
, размерность вектора

Число перестановок без повторений

Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов.

Число перестановок без повторений находится по формуле:

.

Замечание: Мощность искомого множества А удобно искать по формуле:
, гдех – число способов выбрать нужные места; у – число способов расположить на них нужные элементы; z – число способов расположить остальные элементы на оставшихся местах.

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

Всего способов расставить 5 книг на 5-ти местах – равно = 5! = 120.

В задаче х – число способов выбрать два места рядом, х = 4; у – число способов расположить две книги на двух местах, у = 2! = 2; z – число способов расположить остальные 3 книги на оставшихся 3-х местах, z = 3! = 6. Значит
= 48.

Число сочетаний без повторений

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

Число сочетаний без повторений находится по формуле:

.

Свойства:

1)
; 2)
; 3)
;

4)
; 5)
; 6)
.

Пример. В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет ровно один белый.

Всего способов
. Чтобы получить число способов выбрать 1 белый шар (из 3-х белых) и 2 черных шара (из 4-х черных), надо перемножить
и
Таким образом искомое количество способов

Упражнения

1. Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек. Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?

2. В группе из 30 студентов каждый знает, по крайней мере, один иностранный язык – английский или немецкий. Английский знают 22 студента, немецкий – 17. Сколько студентов знают оба языка? Сколько студентов знают немецкий язык, но не знают английский?

3. В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Америки. Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы; в 3 – и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты: 1) только с одного континента; 2) только с двух континентов; 3) только африканцы.

4. Каждый из 500 студентов обязан посещать хотя бы один из трех спецкурсов: по математике, физике и астрономии. Три спецкурса посещают 10 студентов, по математике и физике – 30 студентов, по математике и астрономии – 25; спецкурс только по физике – 80 студентов. Известно также, что спецкурс по математике посещают 345 студентов, по физике – 145, по астрономии – 100 студентов. Сколько студентов посещают спецкурс только по астрономии? Сколько студентов посещают два спецкурса?

5. Староста курса представил следующий отчет по физкультурной работе. Всего – 45 студентов. Футбольная секция – 25 человек, баскетбольная секция – 30 человек, шахматная секция – 28 человек. При этом, 16 человек одновременно посещают футбольную и баскетбольную секции, 18 – футбольную и шахматную, 17 – баскетбольную и шахматную, 15 человек посещают все три секции. Объясните, почему отчет не был принят.

6. В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: 1) ровно одна красная; 2) ровно 2 золотых; 3) хотя бы одна красная.

7. В списке 8 фамилий. Из них 4 – женские. Сколькими способами их можно разделить на две равные группы так, чтоб в каждой была женская фамилия?

8. Из колоды в 36 карт выбирают 4 . Сколько способов сделать это так, чтобы: 1) все карты были разных мастей; 2) все карты были одной масти; 3) 2 красные и 2 черные.

9. На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку».

10. Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог».

11. Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература».

12. 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: 1) рядом; 2) на краях очереди;

13. 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: 1) два определенных человека А и Б; 2) три определенных человека А, Б и С.

14. Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: 1) все цифры были разными; 2) на последнем месте четная цифра.

15. Из 26 букв латинского алфавита (среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: 1) ровно одна буква «а»; 2) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.

16. Сколько четырехзначных чисел делятся на 5?

17. Сколько четырехзначных чисел с различными цифрами делятся на 25?

19. Брошены 3 игральные кости. В скольких случаях выпала: 1) ровно 1 «шестерка»; 2) хотя бы одна «шестерка».

20. Брошены 3 игральные кости. В скольких случаях будет: 1) все разные; 2) ровно два одинаковых числа очков.

21. Сколько слов с различными буквами можно составить из алфавита а, в, с, d. Перечислить их все в лексикографическом порядке: abcd, abcd….

Рассмотрим множество А = {а1, а2,..., аn}, содержащее n различных элементов, которое будем называть n-множеством
или генеральной совокупностью объема n. Из n-множества можно образовать его части (подмножества).
Определение. Подмножество, состоящее из m элементов n-множества, называют m-подмножеством n-множества или со-
единением из n элементов по m, или выборкой объема m из генеральной совокупности объема n.
Возможны два способа выбора:

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

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

Какие выборки одного и того же объема считать различными и какие одинаковыми, зависит от правил выбора соедине-
ния (подмножества, выборки).
Два соединения могут отличаться либо 1) составом, если они содержат хотя бы по одному различному элементу, либо
2) порядком входящих элементов.
В зависимости от правил выбора соединения делят на три типа: размещения, перестановки, сочетания. В зависимости от
способа выбора (без возвращения или с возвращением) каждый тип соединения может быть без повторений или с повторениями.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно
выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой
можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов,
среди которых есть одинаковые?

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

На языке теории множеств это звучит следующим образом: размещения из n элементов по m – это упорядоченное
m-подмножество n-множества (упорядоченная m-выборка из генеральной совокупности объема n). Термин «упорядоченная»
означает, что порядок следования элементов в выборке существенен: выборки с одними и теми же элементами, но с разным
порядком их следования различны.

Задача . Пусть имеется множество, содержащее 4 буквы:
{А, B, C, D}. Записать все возможные размещения из 4 указанных букв по две:

а) без повторений;

б) с повторениями.

Решение.

а) Таких размещений 12: (АВ), (AC), (АD), (ВС),(ВD), (BA), (CA), (CB), (СD), (DА), (DВ), (DС). Заметим, что
размещения отличаются порядком входящих в них элементов и их составом. Размещения АВ и ВА содержат одинаковые буквы,
но порядок их расположения различен.
б) Таких размещений 16. К приведенным для случая (а)
размещениям добавляются размещения из одинаковых элементов (АА), (BB), (CC), (DD).

Задача . Пусть имеется множество, содержащее 2 буквы:{A, B}. Записать все возможные размещения с повторениями из
4-х букв.
Решение. Таких размещений 16: (AAAA), (BBBB), (AAAB),(AABA), (ABAA), (BAAA), (AABB), (ABAB), (BABA), (BBAA), (ABBA),
(BAAB), (BBBA), (BBAB), (BABB), (ABBB).

Теорема 3. 3.1 Число различных размещений без повторений из n элементов по m равно

для выборки без возвращения.

3.2 Число размещений с повторениями из n элементов по m равноm (2) для выборки с возвращением.

Доказательство. Для доказательства воспользуемся пра- вилом умножения.

Рассмотрим выборки без возвращения. Для выбора первого элемента имеется n возможностей, второго – (n – 1)

(перед вторым выбором в генеральной совокупности ос- талось (n –1) элементов),..., при m-ом выборе (n – m + 1) воз- можностей.

Таким образом, по правилу умножения

Запишем выражение в более удобном виде, умножив и разделив его на (m – n)!

Считается, что 0! = 1, что позволяет использовать эту формулу для случая m = n.

Рассмотрим выборки с возвращением . Для выбора первого элемента имеется n возможностей, второго – тоже n (перед выбо-
ром очередного элемента предыдущий выбранный элемент зафиксирован и возвращен в генеральную совокупность), при m-м вы-
боре тоже n возможностей. Таким образом .

Задача . В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии.

Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение . В данной задаче генеральной совокупностью являются 12 страниц газеты, и выборкой без возвращения 4 выбранные из них страницы для фотографий. В данной задаче важно не только то, какие выбраны страницы, но и в каком порядке (для расположения фотографий). Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Задача . У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих
штампов нанести на все книги пятизначные номера – составить каталог. Сколько различных пятизначных номеров может со-
ставить мальчик?
Решение. Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр {1, 3, 7}. Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

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

Задача . Пусть имеется множество букв {A, B, C}. Записать все возможные перестановки.
Решение. Этому множеству букв соответствует 6 перестановок: (АВС), (ACB), (BAC), (BCA), (CBA), (CAB).

Теорема . Число перестановок n различных элементов равно n!, т. е. Рn = n!

Доказательство. Так как перестановки являются частным случаем размещений, то при n = m получаем

Замечание. При больших n для подсчета факториала исполь- зуют таблицу логарифмов факториалов либо приближенную формулу Стирлинга

Задача . Сколько можно составить четырехбуквенных «слов» из букв слова «брак»?

Решение . Генеральной совокупностью являются 4 буквы слова «брак» {б, р, а, к}.

Число «слов» определяется перестановками этих 4 букв, т. е. Р4 = 4! = 1 x 2 x 3 x 4 = 24.

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

Решение . В исходной генеральной совокупности – 9 разных книг.

Тогда для остальных 6 книг существует Р6 = 6! = 720 перестановок.

Однако четыре определенные книги можно переставить между собой Р4 = 4! = 24 способами.

По правилу умножения имеем Р6 x Р4 = 720 x 24 = 17280.

4. Перестановки с повторениями
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на
n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. есть одинаковые предметы.

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

а1 повторяется n1 раз,
а2 повторяется n2 раз,
. . . . . . . . . . . . . . . . . . .
аn повторяется nk раз
n1 + n2 + ... + nk = n
и которые отличаются друг от друга только порядком расположения различных элементов.

Теорема. Число перестановок с повторениями

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

Задача .

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Решение. Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв.

Следовательно, число перестановок с повторениями равно

5. Сочетания без повторений
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из п различных предметов?
Определение. Сочетаниями из n различных элементов по m называются соединения из n элементов по m (m <=n), которые
отличаются друг от друга только составом элементов.

Задача. Пусть имеется множество, содержащее 4 буквы {A, B, C, D}. Запишем все возможные сочетания из указанных
букв по 3.
Решение. Таких сочетаний 4: ABC, ACD, ABD, BCD.
Здесь в число сочетаний не включены, например, АСВ,ВСА, так как они не отличаются по составу от последовательно-
сти букв АВС, потому что перестановка элементов нового сочетания не дает.

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

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

Вспомним, что и сочетания, и размещения из n элементов по m – это выборки объема m из генеральной совокупности объема n и разница между ними в том, что в случае размещений важен и состав, и порядок элементов, тогда как в случае сочетаний важен только состав элементов. Пусть имеется какое-то одно сочетание. Для того, чтобы образовать все размещения с такими же элементами, нужно осуществить всевозможные перестановки элементов этого сочетания. Поскольку в сочетании m элементов, то существует m! перестановок. Следовательно, одному сочетанию, состоящему из m элементов, соответствует m! размещений с этими элементами. Поэтому

Числа называются биномиальными коэффициентами: они являются коэффициентами в разложении бинома Ньютона

Задача . Необходимо выбрать в подарок 4 из 10 имеющих- ся различных книг. Сколькими способами можно это сделать?

Решение . Генеральной совокупностью является 10 раз- личных книг. Из них нужно выбрать 4, причем порядок выбора книг не играет роли. Нужно найти число сочетаний из 10 элементов по

Задача . Имеется 10 белых и 5 черных шаров. Сколькими способами можно выбрать 7 шаров, чтобы среди них были 3 черных?

Решение . Имеем 15 шаров: 10 белых и 5 черных. Нужно выбрать 7 шаров: 4 белых и 3 черных.

Разобьем 15 шаров на 2 генеральные совокупности:

1) 10 белых шаров;

2) 5 черных шаров.

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

Способами. 3 черных шара будем выбирать из II генеральной совокупности, их можно выбрать

Способами.

Тогда по правилу умножения искомое число способов равно .

Решение этой задачи можно схематически представить следующим образом

Задача . Десять команд участвуют в розыгрыше первенства по футболу, лучшие из которых занимают 1-е, 2-е и 3-е место.

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

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

Решение . Имеется генеральная совокупность объема 10 команд. Из нее будем выбирать 5 команд в 2 этапа:

1) сначала на первые 3 места из 10 с учетом состава и порядка команд;

2) затем на последние 2 места из оставшихся 7 с учетом только состава (порядок выбывших команд не важен).

Первые 3 места могут быть распределены способами.

Число способов исключить 2 команды из оставшихся 7 равно .

Согласно правилу умножения получаем, что число разных результатов неравенства равно 0.

Задача .

Сколько существует вариантов опроса 11 учащихся на одном занятии, если ни одни из них не будет подверг нут опросу дважды и на занятии может быть опрошено любое количество учащихся, причем порядок, в котором опрашивают- ся учащиеся, безразличен?

Решение .

I способ. Имеется генеральная совокупность объема 11 учащихся. Преподаватель может не опросить ни одного из 11 учащихся, что является одним из вариантов. Этому случаю соответствует . Преподаватель может опросить только одного из учащихся, таких вариантов .

Если преподаватель опросит двух учащихся, то число вариантов опроса . Для опроса трех учащихся существует вариантов и т. д.

Наконец, могут быть опрошены все учащиеся. Число вариантов в этом случае .

Число всех возможных вариантов опроса можно найти по пра- вилу сложения

Решение этой задачи можно схематически представить следующим образом:

II способ. Имеется генеральная совокупность, состоящая из 2 элементов:

{а, в}, где а – ученик опрошен, в – ученик не опрошен на данном занятии.

Опыт состоит в 11-кратном выборе с возвращением одного из элементов этого множества – каждый из 11 учеников либо опрошен, либо не опрошен.

В данной задаче важно не только то, какие выбраны элементы множества (сколько учеников опрошено и сколько нет),

но и в каком порядке (т. е. какой именно ученик опрошен или нет).

Число способов такого выбора определяется числом размещений с повторениями из 2 элементов по 11; .

6. Сочетания с повторениями
Рассмотрим задачу о числе сочетаний с повторениями:
имеется по r одинаковых предметов каждого из n различных типов;

сколькими способами можно выбрать m (m <= r) из этих (n x r) предметов?

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

Задача . Имеются 2 буквы А, 2 буквы В, 2 буквы С. Сколькими способами можно выбрать две из этих шести букв?
Решение. Существует 6 способов выбора 2 букв из 6 с повторениями: (АА), (AB), (AC), (BC), (BB), (CC). Порядок следо-
вания букв не учитывается.

Теорема . Число сочетаний с повторениями равно

Доказательство. Пусть имеются предметы n различных типов. Сколько соединений по m элементов можно из них сделать, если не принимать во внимание порядок элементов. Расположим в каждом сочетании элементы по типам (сначала все элементы 1-го типа, потом 2-го и т. д.). После этого перенумеруем все элементы в сочетании, но к номерам элементов второ- го типа прибавим 1, третьего типа – 2 и т. д. Тогда из каждого сочетания с повторениями получится сочетание без повторений, состоящее из чисел 1, 2,..., n + m – 1, причем в каждое сочетание входит m элементов.

Отсюда следует, что

Задача . В технической библиотеке имеются книги по ма- тематике, физике, химии и т. д., всего по 16 разделам науки.

Поступили очередные 4 заказа на литературу. Сколько сущест- вует вариантов такого заказа?

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

Задача . В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

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

7. Комбинаторика разбиений

Рассмотрим в этом классе задач две следующие задачи:

1. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных предметов по k различным группам, если допускаются пустые группы. Ниже покажем, что число способов равно k^n .

2. Даны n различных предметов и k различных групп. Сколькими способами можно распределить n различных пред- метов по k группам, если в первой группе n1 предметов, во второй – n2 , в k-й – nk , где n1 + n2 +... + nk = n . Ниже покажем, что число способов равно

Рассмотрим решение первой задачи. Пусть генеральной совокупностью будет k различных групп {1, 2,..., k}. Можно считать, что опыт состоит в n-кратном выборе с возвращением номера группы для каждого предмета. Заметим, что поскольку предметы разные, то важно не только, какие группы выбираются для предметов, но и в каком порядке выбираются эти группы. Таким образом, число способов раз- бить n различных предметов на k групп определяется числом размещений с повторениями и k элементов по n:

Рассмотрим решение второй задачи.

Разбиение n предметов по k группам можно выполнить следующим образом. Сначала положим все n предметов в ряд. После этого возьмем первые n1 предметов и поместим их в первую группу, вторые n2 предмета – во вторую группу, ..., последние nk предметов в k-ю группу. Ясно, что меняя положение предметов в ряду, можно получить всевозможные разбиения предметов. Так как число перестановок из n элементов равно n!, то число расположения предметов в ряд равно n! При этом заметим, что любая перестановка первых n1 предметов ничего не меняет, так же как и вторых n2, ..., и последних nk. В силу правила произведения получим n1!n2!...nk! перестановок предметов, не меняющих результата раздела. Таким образом, число способов разбиения на группы равно

Формула совпадает с формулой для числа перестановок с повторениями. К этому же результату можно прийти иначе. Первые n1 предметов выбираем из n предметов. Так как порядок выбранных предметов безразличен, то имеет выборов. После этого следующие n2 предмета выбираем из оставшихся n – n1. Это можно сделать способами, и т. д.

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

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

Задача. 7 одинаковых шариков случайным образом рас- сыпаются по 4 лункам (в одну лунку может поместиться любое число шаров). Сколько существует различных способов распре- деления 7 шариков по 4 лункам?

Решение. Мы имеем 7 шариков, которые распределяем по 4 лункам (лунки могут быть пустые), т. е. это соответствует первой задаче о разбиениях, число способов равно 4^7 = 16348

Задача. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Решение. Это задача о разделе 28 костей между 4 игрока- ми по 7 костей. Используя полученную выше формулу для числа способов такого раздела (задача 2), имеем

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

наторные понятия присутствуют в ней в неявной форме. Поэтому после усвоения содержания задачи нужно ее «перевести»
на математический язык.
Для этого необходимо выяснить,
1) что является генеральной совокупностью - она всегда будет присутствовать в задаче, т. е. комбинаторные задачи свя-
заны с выбором объектов, а этот выбор из чего-то (генеральной совокупности) производится; каков объем генеральной сово-
купности;
2) одна или несколько генеральных совокупностей;
3) что является выборкой и каков объем выборки;
4) правила выбора: допустимы или нет повторы, важен ли порядок выбираемых элементов, возможно ли изменение состава.
После этого полезно для себя переформулировать задачу на языке генеральных совокупностей и выборок. В зависимости
от ситуации выбрать нужную формулу (см. таблицу). Иногда в более сложных задачах приходится использовать совместно не-
сколько формул.

В заключение приведем основные свойства чисел .

Прежде всего, построим таблицу таких чисел, используя формулу (3.11).

Таблица чисел имеет треугольную форму и называется треугольником Паскаля по имени математика Блеза Паскаля (1623-1662). Анализируя треугольник Паскаля, легко видеть основные свойства чисел .

Свойства 1 – 2 вытекают из определения сочетания как подмножества, содержащего m элементов множества, имеющего n элементов.

Свойства 3 – 5 доказываются методом математической индукции.

В силу свойства 4 треугольник Паскаля легко продолжить вниз на любое число шагов.

рис 3.2 схема определения вида расстановок и выбора формул