Число размещений из n по k формула. Задачи по комбинаторике

Прежде всего, разберем основные понятия комбинаторики - выборки и их типы: перестановки, размещения и сочетания. Знать их необходимо для решения большой части ЕГЭ 2019 по математике обоих уровней, а также девятиклассникам для сдачи ОГЭ. Начнём с примера.

Перестановки. Подсчет числа перестановок.

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

"Расставьте 4 книги на полке так, чтобы бордовый и синий тома не стояли рядом. Покажите мне все варианты расстановки. Я выберу наиболее предпочтительный."

Что вы станете делать? Вероятнее всего, начнете расставлять и показывать. Однако, чтобы не запутаться, не пропустить ни одного из возможных вариантов и не повторяться, нужно делать это по какой-нибудь системе.

Например, сначала оставляем на первом месте бордовый том, рядом с ним может находиться зеленый или оранжевый. Если на втором месте стоит зеленый том, то далее могут стоять либо оранжевый и синий, либо синий и оранжевый. Если на втором месте стоит оранжевый том, то далее могут стоять либо зеленый и синий, либо синий и зеленый. Итого, получается 4 возможных варианта.

На первом месте может стоять любой из 4-ёх томов, значит описанную процедуру надо повторить еще 3 раза. Случай, когда на первом месте стоит синий том, получается такими же рассуждениями.

А следующие два случая отличаются тем, что на оставшихся трёх местах должны находиться бордовый и синий тома, но не рядом. Например, когда на первом месте стоит зеленый том, оранжевый том должен стоять на третьем месте, чтобы разделять бордовый и синий тома, которые могут занимать, соответственно, либо второе и четвертое места, либо четвертое и второе.

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

А теперь представьте себе, что у заказчика книг больше, чем 4. Ну хотя бы 5. Понятно, что и вариантов расстановки будет больше, и реально переставлять их с места на место дольше, и запутаться и начать повторяться легче... Значит бросаться в бой без подготовки уже не стоит. Нужно сначала запланировать варианты на бумаге. Для краткости занумеруем наши цветные тома и будем переставлять на бумаге их номера. Чтобы меньше ошибаться, сначала выпишем все варианты перестановки, а затем вычеркнем те из них, которые подпадают под ограничение. Итак:

"Расставьте 5 книг на полке так, чтобы 1-й и 2-й тома не стояли рядом. Покажите все варианты перестановок."

У нас 5 книг (или 5 цифр), каждая из которых может стоять на первом месте. Сделаем для каждого из этих 5-ти случаев свою табличку. На втором месте может стоять любая из оставшихся 4-ёх цифр, для каждой из них зарезервируем столбик в табличке.

В каждом столбике помещаем пары строк, в которых на третьем месте стоит одна из оставшихся 3-ёх цифр, а две последние цифры меняются местами. Таким образом мы аккуратно выписываем все варианты перестановок. Подсчитаем их общее число.

5 (таблиц)×4 (столбика)×3 (пары строк)×2 (строки)×1(вариант) = 120 (вариантов).

И, наконец, вычеркнем из всех таблиц варианты, содержащие "12" или "21". Таких оказалось по 6 в первой и второй табличках и по 12 в оставшихся 3-ёх, всего 48 вариантов, не удовлетворяющих ограничению. Значит заказчику надо показать 120 − 48 = 72 варианта расположения 5-ти книг. На это уйдет больше часа, даже если тратить на обсуждение каждого варианта только минуту.

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

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

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

Формула для числа перестановок.

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

Если перестановки производятся на множестве из n элементов, их число определяется по формуле
P n = n ·(n −1)·(n −2)...3·2·1 = n !

n ! - обозначение, которое используют для краткой записи произведения всех натуральных чисел от 1 до n включительно и называют "n -факториал" (в переводе с английского "factor" - "множитель").

Таким образом, общее число перестановок 5-ти книг P 5 = 5! = 1·2·3·4·5 = 120, что мы и получили выше. Фактически мы выводили эту формулу для маленького примера. Теперь решим пример побольше.

Задача 1 .

На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом 1-й и 2-й тома не стояли рядом?

Решение.

Определим общее число перестановок из 30 элементов по формуле P 30 =30!
Чтобы вычислить число "лишних" перестановок, сначала определим, сколько вариантов, в которых 2-й том находится рядом с 1-ым справа от него. В таких перестановках 1-ый том может занимать места с первого по 29-е, а 2-й со второго по 30-е - всего 29 мест для этой пары книг. И при каждом таком положении первых двух томов остальные 28 книг могут занимать остальные 28 мест в произвольном порядке. Вариантов перестановки 28 книг P 28 =28! Всего "лишних" вариантов при расположении 2-го тома справа от 1-го получится 29·28! = 29!.
Аналогично рассмотрим случай, когда 2-й том расположен рядом с 1-ым, но слева от него. Получается такое же число вариантов 29·28! = 29!.
Значит всего "лишних" перестановок 2·29!, а нужных способов расстановки 30!−2·29! Вычислим это значение.
30! = 29!·30; 30!−2·29! = 29!·(30−2) = 29!·28.
Итак, нам нужно перемножить все натуральные числа от 1 до 29 и еще раз умножить на 28.
Ответ: 2,4757335·10 32 .

Это очень большое число (после двойки еще 32 цифры). Даже если затратить секунду на каждую перестановку, то потребуются миллиарды лет. Стоит ли выполнять такое требование заказчика, или лучше уметь обоснованно возразить ему и настоять на применении дополнительных ограничений?

Перестановки и теория вероятностей.

Еще чаще необходимость подсчёта числа вариантов возникает в теории вероятностей. Продолжим книжную тему следующей задачей.

Задача 2 .

На книжной полке стояло 30 томов. Ребенок уронил книги с полки, а затем расставил их в случайном порядке. Какова вероятность того, что он не поставил 1-й и 2-й тома рядом?

Решение.

Сначала определим вероятность события А, состоящего в том, что ребенок поставил 1-й и 2-й тома рядом.
Элементарное событие - некая расстановка книг на полке. Понятно, что общее число всех элементарных событий будет равно общему числу всех возможных перестановок P 30 =30!.
Число элементарных событий, благоприятствующих событию А, равно числу перестановок, в которых 1-й и 2-й тома стоят рядом. Мы рассматривали такие перестановки, решая предыдущую задачу, и получили 2·29! перестановок.
Вероятность определяем делением числа благоприятствующих элементарных событий на число всех возможных элементарных событий:
P(A) = 2·29!/30! = 2·29!/(29!·30) = 2/30 = 1/15.
Событие В - ребенок не поставил 1-й и 2-й тома рядом - противоположно событию A, значит его вероятность P(B) = 1 − P(A) = 1−1/15 = 14/15 = 0,9333
Ответ: 0,9333.

Замечаниe: Если непонятно, как сокращаются дроби с факториалами, то вспомните, что факториал это краткая запись произведения. Её всегда можно расписать длинно и зачеркнуть повторяющиеся множители в числителе и в знаменателе.

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

Размещения. Подсчет числа размещений.

Теперь предположим, что у заказчика много книг и невозможно разместить их все на открытых полках. Его просьба состоит в том, что нужно выбрать определенное количество каких-либо книг и разместить их красиво. Красиво получилось или некрасиво это вопрос вкуса заказчика, т.е. он опять хочет посмотреть все варианты и принять решение сам. Наша задача состоит в том, чтобы посчитать количество всех возможных вариантов размещения книг, обоснованно переубедить его и ввести разумные ограничения.

Чтобы разобраться в ситуации, давайте сначала считать, что "много" - это 5 книг, что у нас всего одна полка, и что на ней вмещается лишь 3 тома. Что мы будем делать?
Выбираем одну из 5-ти книг и ставим на первое место на полке. Это мы можем сделать 5-ю способами. Теперь на полке осталось два места и у нас осталось 4 книги. Вторую книгу мы можем выбрать 4-мя способами и поставить рядом с одной из 5-ти возможных первых. Таких пар может быть 5·4. Осталось 3 книги и одно место. Одну книгу из 3-ёх можно выбрать 3-мя способами и поставить рядом с одной из возможных 5·4 пар. Получится 5·4·3 разнообразных троек. Значит всего способов разместить 3 книги из 5-ти 5·4·3 = 60.

На рисунке представлены только 4 варианта размещения из 60 возможных. Сравните картинки. Обратите внимание, что размещения могут отличаться друг от друга либо только порядком следования элементов, как первые две группы, либо составом элементов, как следующие.

Формула для числа размещений.

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

Число размещений из n по m обозначается A n m и определяется по формуле
A n m = n ·(n − 1)·(n − 2)·...·(n − m + 1) = n !/(n − m) !

Попробуем вычислить по этой формуле A n n , т.е. число размещений из n по n .
A n n = n ·(n -1)·(n -2)·...·(n -n + 1) = n ·(n -1)·(n -2)· ... ·1 = n !
Таким образом, A n n = P n = n !

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

Задача 3 .

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

Решение.

Определим общее число размещений из 30 элементов по 15 по формуле
A 30 15 = 30·29·28·...·(30−15+1) = 30·29·28·...·16 = 202843204931727360000.
Ответ: 202843204931727360000.

Будете размещать реальные книги? Удачи! Посчитайте, сколько жизней потребуется, чтобы перебрать все варианты.

Задача 4 .

Сколькими способами можно расставить 30 книг на двух полках, если на каждой из них помещается только по 15 томов?

Решение.

Способ I.
Представим себе, что первую полку мы заполняем так же, как в предыдущей задаче. Тогда вариантов размещения из 30-ти книг по 15 будет A 30 15 = 30·29·28·...·(30−15+1) = 30·29·28·...·16.
И при каждом размещении книг на первой полке мы еще P 15 = 15! способами можем расставить книги на второй полке. Ведь для второй полки у нас осталось 15 книг на 15 мест, т.е. возможны только перестановки.
Всего способов будет A 30 15 ·P 15 , при этом произведение всех чисел от 30 до 16 еще нужно будет умножить на произведение всех чисел от 1 до 15, получится произведение всех натуральных чисел от 1 до 30, т.е. 30!
Способ II.
Теперь представим себе, что у нас была одна длинная полка на 30 мест. Мы расставили на ней все 30 книг, а затем распилили полку на две равные части, чтобы удовлетворить условию задачи. Сколько вариантов расстановки могло быть? Столько, сколько можно сделать перестановок из 30 книг, т.е. P 30 = 30!
Ответ: 30!.

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

Размещения и теория вероятностей.

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

Задача 5 .

На книжной полке находится собрание сочинений одного автора в 6 томах. Книги одинакового формата расположены в произвольном порядке. Читатель, не глядя, берет 3 книги. Какова вероятность того, что он взял первые три тома?

Решение.

Событие A - у читателя первые три тома. С учетом порядка выбора он мог взять их 6-ю способами. (Это перестановки из 3-ёх элементов P 3 = 3! = 1·2·3 = 6, которые легко перечислить 123, 132, 213, 231, 312, 321.)
Таким образом, число благоприятствующих элементарных событий равняется 6.
Общее число возможных элементарных событий равно числу размещений из 6-ти по 3, т.е. A 6 3 = 6·...·(6−3+1) = 6·5·4 = 120.
P(A) = 6/120 = 1/20 = 0,05.
Ответ: 0,05.

Сочетания. Подсчет числа сочетаний.

И последний случай - все книги заказчика одного цвета и одного размера, но на полке помещается лишь часть из них. Казалось бы проблем у дизайнера нет совсем, выбирай столько книг из общего числа, сколько нужно, и расставляй их на полке в произвольном порядке, ведь книги внешне неразличимы. Но они различаются, и существенно! Эти книги разные по содержанию. И заказчику, возможно, не всё равно, где находятся трагедии Шекспира, а где детективы Рекса Стаута, на открытой полке или в шкафу. Таким образом, у нас возникает ситуация, когда важен состав элементов выборки, но несущественен порядок их расположения.

На рисунке показаны две выборки из "собрания сочинений одного автора в 5 томах". Первая больше понравится заказчику, если он чаще перечитывает ранние произведения этого автора, помещенные в первых трёх томах, вторая - если чаще обращается к поздним произведениям, помещенным в последних томах. Смотрятся обе группы одинаково красиво (или одинаково некрасиво) и неважно, будет ли группа расположена как 123 или как 321...

Формула для числа сочетаний.

Неупорядоченные выборки называются из n элементов по m и обозначаются С n m .
Число сочетаний определяется по формуле С n m = n! /(n − m)!/m!

В этой формуле присутствуют два делителя и в качестве знака деления использован символ "/ ", который более удобен для веб-страницы. Но деление можно также обозначать двоеточием ": " или горизонтальной чертой "−−−". В последнем случае формула выглядит как обыкновенная дробь, в которой последовательное деление представлено двумя сомножителями в знаменателе . Для тех, кому более понятно представление в виде дроби, все формулы продублированы в начале и в самом конце страницы. Разбирая решения задач сравнивайте мою запись с привычной для себя.
Кроме того, все множители и делители в этой формуле представляют собой произведения последовательных натуральных чисел, поэтому дробь хорошо сокращается, если её расписать подробно. Но подробное сокращение я в задачах пропускаю, его легко проверить самостоятельно.

Понятно, что для одинаковых исходных множеств из n элементов и одинаковых объёмов выборок (по m элементов) число сочетаний должно быть меньше, чем число размещений. Ведь при подсчёте размещений для каждой выбранной группы мы еще учитываем все перестановки выбранных m элементов, а при подсчёте сочетаний перестановки не учитываем: С n m = A n m /P m = n! /(n−m )!/m!

Задача 6 .

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

Решение.

Мы решаем эту задачу в контексте работы дизайнера интерьеров, поэтому порядок следования на полке 15-ти выбранных внешне одинаковых книг не имеет значения. Нужно определить общее число сочетаний из 30 элементов по 15 по формуле
С 30 15 = 30! /(30 − 15)!/15! = 155117520.
Ответ: 155117520.

Задача 7 .

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

Если мы снова отвечаем на этот вопрос с точки зрения дизайнера интерьеров, то порядок следования книг на каждой из полок несущественен. Но заказчику может быть важно или неважно, как книги распределены между полками.
1) Например, если обе полке находятся рядом, обе открыты, обе на одинаковой высоте, то заказчик может сказать, что это неважно. Тогда ответ очевиден - 1 способ, так как при расстановке используется всё множество из 30-ти книг, и никакие перестановки не учитываются.
2) Но когда одна из полок находится слишком высоко, заказчику важно какие книги на ней расположены. В этом случае ответ будет такой же, как в предыдущей задаче - 155117520 способов, потому что первую полку заполняем выборками-сочетаниями из 30 по 15, а на вторую помещаем остальные 15 книг без учёта перестановок.

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

Сочетания и теория вероятностей.

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

Задача 8 .

На книжной полке находится собрание сочинений одного автора в 6 томах. Книги одинаково оформлены и расположены в произвольном порядке. Читатель берет наугад 3 книги. Какова вероятность того, что он взял первые три тома?

Решение.

Событие A - у читателя первые три тома. Это 1-й, 2-й и 3-й тома. Без учета порядка, в котором он выбирал книги, а только по конечному результату, он мог взять их одним способом. Число благоприятствующих элементарных событий - 1.
Общее число возможных элементарных событий равно числу групп из 6-ти по 3, образованных без учета порядка следования элементов в группе, т.е. равно числу сочетаний С 6 3 = 6!/3!/(6 - 3)! = 4·5·6/(1·2·3) = 4·5 = 20.
P(A) = 1/20 = 0,05.
Ответ: 0,05.

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

Заключительные замечания.

Для строгого вывода всех формул (который я здесь не приводила) используются два основных правила комбинаторики :

Правило умножения (правило «и »). Согласно ему, если элемент A можно выбрать n способами, и при любом выборе A элемент B можно выбрать m способами, то пару A и B можно выбрать n·m способами.

Это правило обобщается на произвольную длину последовательности.

Правило сложения (правило «или »). Оно утверждает, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.

Эти правила нужны и для решения задач.

Понятие факториал также распространяется на ноль: 0! = 1 , так как считается, что пустое множество можно упорядочить единственным способом.

Вычислять факториалы больших чисел прямым умножением на калькуляторе очень долго, а очень больших чисел - и на компьютере не быстро. А как же справлялись с этим до создания компьютеров и калькуляторов? Еще в начале 18-го века Дж.Стирлингом и независимо от него А.Муавром была получена формула для приближенного вычисления факториалов, которая тем точнее, чем больше число n . Сейчас эта формула называется формулой Стирлинга:

Заключительная задача.

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

Задача 9 .

Из аквариума, в котором 6 сазанов и 4 карпа, сачком выловили 5 рыб. Какова вероятность того, что среди них окажется 2 сазана и 3 карпа?

Решение.

Элементарное событие - "в сачке группа из 5 рыб". Событие A - "среди 5 пойманных рыб оказалось 3 карпа и 2 сазана".
Пусть n - общее число всех возможных элементарных событий, оно равно числу способов сгруппировать по 5 рыб. Всего рыб в аквариуме 6 + 4 = 10. В процессе ловли сачком рыбы внешне неразличимы. (Мы не знаем, выловили ли мы рыбу по имени Баська или по имени Коська. Более того, пока мы не вытащили сачок наверх и не заглянули в него, мы даже не знаем сазан это или карп.) Таким образом, "выловить 5 рыб из 10" означает сделать выборку типа сочетания из 10 по 5.
n = С 10 5 = 10!/5!/(10 - 5)!
Вытащив сачок и заглянув в него, мы можем определить благоприятствующий это исход или нет, т.е. состоит ли улов из двух групп - 2 сазана и 3 карпа?
Группа сазанов могла сформироваться выбором из 6 сазанов по 2. Причем всё равно, кто из них первым забрался в сачок, а кто вторым, т.о. это выборка типа сочетания из 6 по 2. Обозначим общее число таких выборок m 1 и вычислим его.
m 1 = С 6 2 = 6!/2!/(6 - 2)!
Аналогично общее число возможных групп по 3 карпа определяется числом сочетаний из 4 по 3. Обозначим его m 2 .
m 2 = С 4 3 = 4!/3!/(4 - 3)!
Группы карпов и сазанов формируются в сачке независимо друг от друга, поэтому для подсчёта числа элементарных событий, благоприятствующих событию A, используем правило умножения ("и"-правило) комбинаторики. Итак, общее число благоприятствующих элементарных событий
m = m 1 ·m 2 = С 6 2 ·С 4 3
Вероятность события А определяем по формуле P(A) = m/n = С 6 2 ·С 4 3 /С 10 5
Подставляем в эту формулу все значения, расписываем факториалы, сокращаем дробь и получаем ответ:
P(A) = 6!·4!·5!·(10 - 5)!/2!/(6 - 2)!/3!/(4 - 3)!/ 10! = 5/21 ≈ 0,238

Замечания.
1) Сочетания обычно встречаются в задачах, где неважен процесс формирования группы, а важен только результат. Сазану Баське без разницы первым он попал в сачок или последним, но ему очень важно, в какой группе он оказался в итоге - среди тех, кто в сачке, или среди тех, кто на свободе.
2) Обратите внимание, мы используем "и-правило", потому что союз "и" стоит непосредственно в описании события А, для которого нужно вычислить вероятность совместного улова двух групп. Однако, применяем его только после того, как убедились в независимости выборок. В самом деле, не может же сазан, подплывая к сачку, пересчитать там своих собратьев, и сказать карпу: "Твоя очередь, наших там уже двое". Да и согласится ли карп лезть в сачок в угоду сазану? Но если бы они могли договориться, то это правило применять было бы уже нельзя. Надо было бы обратиться к понятию условная вероятность.

Ответ: 0,238.

Показать решение.

Если вы выпускник школы и будете сдавать ЕГЭ, то после изучения этого раздела, вернитесь (10 для базового и 4 для профильного уровней ЕГЭ 2019 по математике), которые можно решать с использованием элементов комбинаторики и без неё (например, на бросание монеты). Какой из возможных способов решения задачи нравится вам больше теперь?

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

План:

1. Элементы комбинаторики.

2. Общие правила комбинаторики.

4. Применение графов (схем) при решении комбинаторных задач.

1. Комбинаторика и ее возникновение.

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

Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры (карты, кости). Широко были распространены лотереи. Первоначально комбинаторные задачи касались в основном азартных игр: сколькими способами можно получить данное число очков, бросая 2 или 3 кости или сколькими способами можно получить 2-ух королей в некоторой карточной игре. Эти и другие проблемы азартных игр являлись движущей силой в развитии комбинаторики и далее в развитии теории вероятностей.

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

Теоретическое исследование вопросов комбинаторики предприняли в XVII веке французские математики Блез Паскаль и Ферма. Исходным пунктом их исследований были так же проблемы азартных игр.

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

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

2. Общие правила комбинаторики.

Правило суммы: Если некоторый объект А может быть выбран m способами, а объект В- k способами, то объект «либо А, либо В» можно выбрать m +k способами.

Примеры:

1. Допустим, что в ящике находится n разноцветных шаров. Произвольным образом вынимается 1 шарик. Сколькими способами это можно сделать?

Ответ: n способами.

Распределим эти n шариков по двум ящикам: в первый- m шариков, во второй- k шариков. Произвольным образом из произвольно выбранного ящика вынимается 1 шарик. Сколькими способами это можно сделать?

Решение: Из первого ящика шарик можно вынуть m способами, из второго- k способами. Тогда всего способов m+k=n .

2. Морской семафор.

В морском семафоре каждой букве алфавита соответствует определенное положение относительно тела сигнальщика двух флажков. Сколько таких сигналов может быть?

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

Правило произведения: Если объект А можно выбрать m способами, а после каждого такого выбора другой объект В можно выбрать (независимо от выбора объекта А) k способами, то пары объектов «А и В» можно выбрать m *k способами.

Примеры:

1. Сколько двузначных чисел существует?

Решение: Число десятков может быть обозначено любой цифрой от 1 до 9. Число единиц может быть обозначено любой цифрой от 0 до 9. Если число десятков равно 1, то число единиц может быть любым (от 0 до 9). Таким образом, существует 10 двузначных чисел, с числом десятков- 1.Аналогично рассуждаем и для любого другого числа десятков. Тогда можно посчитать, что существует 9 *10 = 90 двузначных чисел.

2. Имеется 2 ящика. В одном лежит m разноцветных кубиков, а в другом- k разноцветных шариков. Сколькими способами можно выбрать пару «Кубик-шарик»?

Решение: Выбор шарика не зависит от выбора кубика, и наоборот. Поэтому, число способов, которыми можно выбрать данную пару равно m *k .

3. Генеральная совокупность без повторений и выборки без повторений.

Генеральная совокупность без повторений - это набор некоторого конечного числа различных элементов a 1 , a 2 , a 3 , ..., a n .

Пример: Набор из n разноцветных лоскутков.

Выборкой объема k (k n ) называется группа из m элементов данной генеральной совокупности.

Пример: Пестрая лента, сшитая из m разноцветных лоскутков, выбранных из данных n .

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

- число размещений из n по k .

Число размещений из n по k можно определить следующим способом: первый объект выборки можно выбрать n способами, далее второй объект можно выбрать n -1 способом и т.д.

Преобразовав данную формулу, имеем:

Следует помнить, что 0!=1.

Примеры:

1. В первой группе класса А первенства по футболу участвует 17 команд. Разыгрываются медали: золото, серебро и бронза. Сколькими способами они могут быть разыграны?

Решение: Комбинации команд-победителей отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 17 по 3.

2. Научное общество состоит из 25-ти человек. Необходимо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами это можно сделать?

Решение: Комбинации руководящего состава общества отличаются друг от друга составом и порядком следования элементов, т.е. являются размещениями из 25 по 4.

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

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

Примеры:

1. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что они должны состоять из различных цифр?

Решение: Имеем перестановки из 5 элементов. 2. Сколькими способами можно собрать 6 разноцветных лоскутков в пеструю ленту?
Решение: Имеем перестановки из 6 элементов.

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

- число сочетаний из n по k

Элементы каждого из сочетаний можно расставить способами. Тогда Примеры:

1. Если в полуфинале первенства по шахматам участвует 20 человек, а в финал выходят лишь трое, то сколькими способам и можно определить эту тройку?

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки, вышедшие в финал, являются сочетаниями из 20 по 3.

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

Решение: В данном случае порядок, в котором располагается эта тройка, не существенен. Поэтому тройки делегатов являются сочетаниями из 10 по 3.

Конспект:

4.Применение графов (схем) при решении комбинаторных задач.

В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева». Сначала из одной точки проводят столько отрезков, сколько различных выборов можно сделать на первом шагу. Из конца каждого отрезка проводят столько отрезков, сколько можно сделать выборов на втором шагу, если на первом шагу был выбран данный элемент и т.д.

Задача:

При составлении команд космического корабля учитывается вопрос и психологической совместимости участников путешествия. Необходимо составить команду космического корабля из 3 человек: командира, инженера и врача. На место командира есть 4 кандидата: a 1 , a 2 , a 3 , a 4 .На место инженера- 3: b 1 , b 2 , b 3 . На место врача- 3: c 1 , c 2 , c 3 . Проведенная проверка показала, что командир a 1 психологически совместим с инженерами b 1 и b 3 и врачами c 1 и c 3 . Командир a 2 - с инженерами b 1 и b 2 . и всеми врачами. Командир a 3 - с инженерами b 1 и b 2 и врачами c 1 и c 3 . Командир a 4 -со всеми инженерами и врачом c 2 . Кроме того, инженер b 1 не совместим с врачом c 3 , b 2 - с врачом c 1 и b 3 - с врачом c 2 . Сколькими способами при этих условиях может быть составлена команда корабля?

Решение:

Составим соответствующее «дерево».

Ответ: 10 комбинаций.

Такое дерево является графом и применяется для решения комбинаторных задач.

Число размещений без повторений из 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….

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

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

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

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

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

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

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

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

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

Итого : 6 комбинаций или 6 перестановок .

Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!

Никаких мучений - 3 объекта можно переставить способами.

Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?

Зачем выбирать? Так нагуляли же аппетит в предыдущем пункте - для того, чтобы съесть! а) Один фрукт можно выбрать, очевидно, тремя способами - взять либо яблоко, либо грушу, либо банан.

Формальный подсчёт проводится по формуле количества сочетаний :

Запись в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»

б) Перечислим все возможные сочетания двух фруктов:

яблоко и груша;
яблоко и банан;
груша и банан.

Количество комбинаций легко проверить по той же формуле:

Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».

в) И, наконец, три фрукта можно выбрать единственным способом:

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

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.

Для ответа на следующий вопрос мне требуется два добровольца… …Ну что же, раз никто не хочет, тогда буду вызывать к доске =)

Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе?

Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:

яблоко и груша;
яблоко и банан;
груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей - Наташу;
либо наоборот - груша достанется Даше, а яблоко - Наташе.

И такая перестановка возможна для каждой пары фруктов.

В данном случае работает формула количества размещений :

Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.

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

Также напоминаю, что сейчас речь идёт о множестве с различными объектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными .

Остановимся на каждом виде комбинаций подробнее:

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

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

Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все объектов. Например, дружная семья:

Задача 1

Сколькими способами можно рассадить 5 человек за столом?

Решение : используем формулу количества перестановок:

Ответ : 120 способами

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

Задача 2

Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9?

Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны! ) , и это очень важная предпосылка для применения формулы Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, … стоп, а всё ли тут в порядке? ;-)

Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач - в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами. Нет, конечно, я не призываю тупо прорабатывать другие разделы математики, однако должен заметить, что те же интегралы можно научиться решать чисто механически.

Решение и ответ в конце урока.

Увеличиваем обороты:

Сочетания

В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой:

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

Задача 3

В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

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

В задаче речь идёт о выборке из 4-х деталей, в которой не имеет значения их «дальнейшая судьба» - грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:

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

Способами можно взять 4 детали из ящика.

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

Ответ : 1365 способами

Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: . Применительно к разобранной задаче:

Единственным способом можно взять ни одной детали;
способами можно взять 1 деталь (любую из 15-ти);
способами можно взять 14 деталей (при этом какая-то одна из 15-ти останется в ящике);
- единственным способом можно взять все пятнадцать деталей.

Рекомендую внимательно ознакомиться с биномом Ньютона и треугольником Паскаля , по которому, к слову, очень удобно выполнять проверку вычислений при небольших значениях «эн».

Задача 4

Сколькими способами из колоды в 36 карт можно выбрать 3 карты?

Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью - главное, разобраться в сути. И суть, бывает, открывается с различных сторон. Разберём весьма поучительный пример:

Задача 4

В шахматном турнире участвует человек и каждый с каждым играет по 1-й партии. Сколько всего партий сыграно в турнире?

Поскольку я сам играю в шахматы и неоднократно принимал участие в круговых турнирах, то сразу же сориентировался по турнирной таблице размером клеток, в которой результат каждой партии учитывается дважды и, кроме того, затушёвываются клетки «главной диагонали» (т.к. участники не играют сами с собой) . Исходя из проведённых рассуждений, общее количество сыгранных партий рассчитывается по формуле . Такое решение полностью корректно (см. соответствующий файл банка готовых решений ) и на долгое время я забыл о нём по принципу «решено, да и ладно».

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

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

Ну а вывода тут два:

Во-первых, не всё очевидное - очевидно;

И во-вторых, не бойтесь решать задачи «нестандартно»!

Большое спасибо за ваши письма, они помогают улучшить качество учебных материалов!

Размещения

Или «продвинутые» сочетания. Размещениями называют различные комбинации из объектов, которые выбраны из множества различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком . Количество размещений рассчитывается по формуле

Что наша жизнь? Игра:

Задача 5

Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт)

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

Способами можно раздать 3 карты игрокам.

Есть и другая схема решения, которая, с моей точки зрения, даже понятнее:

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

Теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик, 9 червей, 7 червей. Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей способами:

КП, 9Ч, 7Ч;
КП, 7Ч, 9Ч;
9Ч, КП, 7Ч;
9Ч, 7Ч, КП;
7Ч, КП, 9Ч;
7Ч, 9Ч, КП.

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

Способами можно сдать по одной карте 3-м игрокам.

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

Ответ : 42840

Возможно, у вас остался вопрос, а кто же раздавал карты? …Наверное, преподаватель =)
И чтобы никому не было обидно, в следующей задаче примет участие вся студенческая группа:

Задача 6

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

Задача о «размещении» должностей в коллективе встречается очень часто и является самым настоящим баяном. Краткое решение и ответ в конце урока.

Задача . Определить количество всех упорядоченных наборов длиныr , которые можно составить из элементов множестваX (
), если выбор каждого элемента
, производится из всего множестваX .

Упорядоченный набор
– это элемент декартова произведения
, состоящего изr одинаковых множителейX . По правилу произведения количество элементов множества
равно
. Мы вывели формулу
.

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

Здесь
, и количество телефонных номеров равно

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

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

Первый элемент можно выбратьn способами. Если первый элемент уже выбран, то второй элементможно выбрать лишь
способами, а если уже выбран
элемент
, то элементможно выбрать
способами (повторение уже выбранного элемента не допускается). По правилу произведения получаем

Эта формула записывается иначе с использованием обозначения
. Так как

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

Здесь
, искомым является число

2.1.6. Перестановки без повторений

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

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

2.1.7. Перестановки с повторениями

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

Пример . Из букв
запишем перестановку с повторением состава
. Ее длина
, причем букваa входит 2 раза,b – 2 раза,c – один раз. Такой перестановкой будет, например,
или
.

Выведем формулу количества перестановок с повторениями. Занумеруем все одинаковые элементы, входящие в перестановку, различными индексами, т.е. вместо перестановки
получим
. Теперь все элементы перестановки различны, а количество таких перестановок равно
. Первый элемент встречается в выборкераз. Уберем индексы у первого элемента (в нашем примере получим перестановку
), при этом число различных перестановок уменьшится в раз, т.к. при изменении порядка одинаковых элементов наша выборка не изменится. Уберем индексы у второго элемента – число перестановок уменьшится в раз. И так далее, до элемента с номеромk – число перестановок уменьшится в раз. Получим формулу

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

В этом слове буквы “е” и “а” встречаются два раза, остальные по одному разу. Речь идет о перестановке с повторением состава
длины. Количество таких перестановок равно

2.1.8. Сочетания

Задача . Сколько различных множеств изr элементов можно составить из множества, содержащегоn элементов?

Будем составлять вначале упорядоченные наборы по r элементов в каждом. Количество таких наборов (это размещения изn элементов поr ) равно
. Теперь учитываем, что порядок записи элементов нам безразличен. При этом изразличных размещений, отличающихся только порядком элементов, получим одно сочетание. Например, два различных размещения
и
из двух элементов соответствуют одному сочетанию
. Таким образом, число сочетанийвраз меньше числа размещений: