Сочетания и перестановки. Перестановки

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

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

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

Пример 1

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

Решение

Первая монета имеет альтернативы – либо орел, либо решка. Для второй монеты также есть альтернативы и т.д., т.е. .

Искомое количество способов:

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

Если любые две группы и не имеют общих элементов, то выбор одного элемента или из , или из , …или из можно осуществить способами.

Пример 2

На полке 30 книг, из них 20 математических, 6 технических и 4 экономических. Сколько существует способов выбора одной математической или одной экономической книги.

Решение

Математическая книга может быть выбрана способами, экономическая - способами.

По правилу суммы существует способа выбора математической или экономической книги.

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

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

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

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

Пример 3

Расписание дня состоит из 5 различных уроков. Определите число вариантов расписания при выборе из 11 дисциплин.

Решение

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

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

Пример 4

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

Решение

Каждый вариант рассадки отличается только порядком участников, то есть является перестановкой из 4 элементов:

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

Общее число различных способов, которыми можно произвести выбор с возвращением элементов из генеральной совокупности объема , равно

Пример 5

Лифт останавливается на 7 этажах. Сколькими способами могут выйти на этих этажах 6 пассажиров, находящихся в кабине лифта?

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

Решение

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

Сочетания

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

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

Число сочетаний из элементов по равно:

Пример 6

В ящике 9 яблок. Сколькими способами можно выбрать 3 яблока из ящика?

Решение

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

Количество способов, которыми можно выбрать 3 яблока из 9:

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

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

Пример 7

На почте продают открытки 3 видов. Сколькими способами можно купить 6 открыток?

Это задача на отыскание числа сочетаний с повторениями из 3 по 6:

Разбиение множества на группы

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

Число разбиений на групп, когда в первую попадают элементов, во вторую - элементов, в k-ю группу - элементов, равно:

Пример 8

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

Решение

Здесь

Число разбиений на 3 подгруппы:

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

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

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

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

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

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

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

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

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

Итого : 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 человека. Сколькими способами можно выбрать старосту и его заместителя?

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

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

Сформулируем следующие определения:

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

Размещением без повторения из n элементов по m N , содержащее m различных элементов .

Из определения следует, что два размещения отличаются друг от друга, как элементами, так и их порядком, даже если элементы одинаковы.

Теорема 3 . Число размещений без повторения равно произведению m сомножителей, наибольшим из которых является число n . Записывают:

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

Перестановками из n элементов называются различные упорядочения множества N .

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

Теорема 4 . Число различных перестановок без повторений вычисляется по формуле

Сочетания без повторений

Сочетанием без повторения из n элементов по m называется любое неупорядоченное подмножество множества N , содержащее m различных элементов.

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

Теорема 5 . Число сочетаний без повторений вычисляют по одной из следующих формул:

Пример 1 . В комнате 5 стульев. Сколькими способами можно разместить на них

а) 7 человек; б) 5 человек; в) 3 человека?

Решение: а) Прежде всего надо выбрать 5 человек из 7 для посадки на стулья. Это можно сделать
способом. С каждым выбором конкретной пятерки можно произвести
перестановок местами. Согласно теореме умножения искомое число способов посадки равно.

Замечание: Задачу можно решать, используя только теорему произведения, рассуждая следующим образом: для посадки на 1-й стул имеется 7 вариантов, на 2-й стул-6 вариантов, на 3-й -5, на 4-й -4 и на 5-й -3. Тогда число способов посадки 7 человек на 5 стульев равно . Решения обоими способами согласуются, так как

б) Решение очевидно -

в) - число выборов занимаемых стульев.

- число размещений трех человек на трех выбранных стульях.

Общее число выборов равно .

Не трудно проверить формулы
;

;

Число всех подмножеств множества, состоящего из n элементов.

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

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

Число размещений с повторением обозначают и вычисляют по формуле, представляющей собой следствие из теоремы умножения:

Пример 2 . Пусть дано множество из трех букв N = {a, b, c}. Назовем словом любой набор из букв, входящих в это множество. Найдем количество слов длиной 2, которые можно составить из этих букв:
.

Замечание: Очевидно, размещения с повторением можно рассматривать и при
.

Пример 3 . Требуется из букв {a, b}, составить всевозможные слова длиной 3. Сколькими способами это можно сделать?

Ответ :

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

Размещения .

Определение 1. Размещением без повторений из n элементов по k называется всякое упорядоченное подмножество данного множества M={a 1 ,a 2 ,¼,a n }, содержащее k элементов.

Отметим, что из определения сразу следует, что, во-первых, все элементы в размещении без повторений различны (в противном случае найдется два одинаковых элемента), во-вторых, k£ n , в-третьих, два различных размещения без повторений различаются либо составом входящих в них элементов, либо порядком их расположения. То есть порядок следования существенен.

Теорема 1. Число различных размещений без повторений из n элементов по k (k£ n) равно

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

Пусть M ={a 1 ,a 2 ,¼,a n }. Требуется определить число различных строк вида (x 1 ,x 2 ,¼,x k ), где все элементы x 1 ,x 2 ,¼,x k ÎM и различны. Первый элемент x 1 можно выбрать n способами. Если x 1 уже выбран, то для выбора x 2 осталось n-1 элементов. Аналогично, x 3 можно выбрать n -2 способами и т.д. Последний элемент x k можно выбрать n-k+1 способами. Перемножая эти числа, получим формулу (4).Теорема доказана.

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

Число всевозможных вариантов расписания есть, очевидно, число различных размещений из 12 элементов по 5, то есть

Важным частным случаем, является случай, когда n=k , то есть когда в строке (x 1 ,x 2 ,¼,x n) участвуют все элементы множества M . Строки без повторений, составленные из n элементов множества M называют перестановками из n элементов. Напомним, что в математике через n! обозначают произведение всех натуральных чисел от 1 до n, то есть ¼и по определению считают, что 0!=1.

Следствие 1 . Пользуясь формулой (4), находим, что число различных перестановок P n из n элементов равно P n = n !.

Определение 2. Размещением с повторениями из n элементов по k называется любая упорядоченная строка из k элементов множества M={a 1 ,a 2 ,¼,a n }, некоторые из которых могут повторяться.

Например, слово “мама” есть размещение с повторениями из 2-х элементов M ={м, а} по 4.

Теорема 2. Число различных размещений с повторениями из n элементов по k

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

Первый элемент в строку из k элементов может быть выбран n способами, поскольку |M|=n. Точно также 2-й, 3-й, …,k-й элементы могут быть выбраны n способами. Перемножая эти числа, получим

k раз

Теорема доказана.

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

В этой задаче M ={1, 2, 3, 4, 5}, n=5, k=2.Поэтому ответом является число

Пример 3. Сколькими способами k пассажиров могут распределиться по n вагонам, если для каждого пассажира существенным является только номер вагона, а не занимаемое им в вагоне место?

Перенумеруем всех пассажиров. Пусть x 1 - номер вагона, выбранного первым пассажиром, x 2 - номер вагона второго пассажира, …, x k - номер вагона k -го пассажира. Строка (x 1 ,x 2 ,¼,x k ) полностью характеризует распределение пассажиров по вагонам. Каждое из чисел x 1 ,x 2 ,¼,x k может принимать любое целое значение от 1 до n. Поэтому в этом примере

M ={1, 2,…,n} и различных распределений по вагонам будет столько же, сколько строк длиной k можно составить из элементов множества M , то есть

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

Сочетания (без повторения ).

Определение 3. Пусть M={a 1 ,a 2 ,¼,a n }. Любое подмножество X мно-жества M , содержащее k элементов, называется сочетанием k элементов из n.

Отметим сразу, что в этом определении порядок следования элементов множества X несущественен и, что k£n , поскольку k=½X½, n=½M½ и XÍM .

Теорема 3. Число различных сочетаний k элементов из n равно

. (6)

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

Каждое сочетание k элементов из n порождает k! различных размещений без повторений из n по k с помощью различных перестановок (см. следствие 1). Таким образом, все сочетаний из k элементов из n после различных k! перестановок порождают все размещений без повторений из n по k . Поэтому . Следовательно,