Комбинаторика: размещения и сочетания
Размещения
Рассмотрим следующую задачу.
Задача. 9 карточек пронумерованы числами 1, 2, 3, 4, 5, 6, 7, 8, 9. Из этих карточек четыре наугад взятых карточки выкладываем в ряд. Сколько при этом можно получить различных четырехзначных чисел?
Решение. Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое.
На первое место можно положить одну из 9 карточек. Для этого есть 9 способов. В каждом из этих 9 способов на второе место можно положить одну из оставшихся 8 карточек. Таким образом, существует
способа, чтобы положить карточки на первое и второе места. В каждом из этих 72 способов на третье место можно положить одну из оставшихся 7 карточек. Следовательно, существует
способа, чтобы положить карточки на первое, второе и третье места. В каждом из этих 504 способов на четвертое место можно положить одну из оставшихся 6 карточек. Отсюда вытекает, что существует
различных способа, чтобы выложить в ряд 4 карточки из набора, состоящего из 9 пронумерованных карточек. Таким образом, при выкладывании карточек можно получить 3024 различных четырехзначных числа.
Ответ: 3024.
При решении задачи мы провели подсчет числа способов раскладывания карточек, который является частным случаем общего метода подсчета числа размещений и заключается в следующем.
Определение 1. Рассмотрим множество, содержащее 
элементов, и все его упорядоченные подмножества, содержащие 
элементов. Каждое из этих подмножеств называют размещением из элементов по элементов.
Если обозначить символом 
число размещений из элементов по элементов, то будет справедлива формула:
 |
(1) |
В соответствии с определением факториала, формулу (1) можно также записать в виде:
В задаче множеством из элементов является исходный набор из 9 пронумерованных карточек, а упорядоченным подмножеством из элементов - 4 карточки, выложенные в ряд.
Таким образом, при решении задачи мы на частном примере подсчитали, чему равно число размещений из 9 элементов по 4 элемента, т.е. число 
В соответствии с формулой (1),
что и было получено в задаче.
Замечание 1. Введенные в данном разделе размещения также называют размещениями без повторений.
Замечание 2. Из формул для числа перестановок и числа размещений вытекает формула
смысл которой заключается в следующем.
Утверждение. Размещение из элементов по элементов является перестановкой из элементов.
Сочетания
Определение 2. Рассмотрим множество, состоящее из элементов. Каждое его подмножество, содержащее элементов, называют сочетанием из элементов по элементов.
Число сочетаний из элементов по элементов обозначается символом 
Замечание 3. Важно отметить, что, в отличие от определения размещений, рассмотренные в определении сочетаний подмножества, содержащие элементов, не являются упорядоченными. Поэтому, если в каждом подмножестве, содержащем элементов (из определения 2), совершить всевозможные перестановки, количество которых равно 
, то мы получим все размещения.
Таким образом, справедлива формула:
Следовательно,
откуда вытекает формула
 |
(2) |
Теперь рассмотрим несколько примеров подсчета числа сочетаний, которые непосредственно вытекают из формулы (2):
В заключение приведем часто используемое равенство, также непосредственно вытекающее из формулы (2):
Замечание 4. С разделом справочника «Сочетания» близко связан раздел «Бином Ньютона», где приведены и доказаны свойства чисел сочетаний.
С понятиями факториала числа и перестановок из элементов можно познакомиться в разделе «Комбинаторика: факториалы и перестановки» нашего справочника.
На нашем сайте можно также ознакомиться с разработанными преподавателями учебного центра "Резольвента" учебными материалами для подготовки к ЕГЭ и ГИА по математике.
Приглашаем школьников (можно вместе с родителями) на бесплатное тестирование по математике, позволяющее выяснить, какие разделы математики и навыки в решении задач являются для ученика "проблемными".
Запись по телефону (495) 509-28-10. |
На нашем сайте можно также ознакомиться с разработанными преподавателями учебного центра "Резольвента" учебными материалами для подготовки к ЕГЭ и ГИА по математике.
Для школьников, желающих хорошо подготовиться и сдать ЕГЭ или ГИА по математике, физике или русскому языку на высокий балл, учебный центр "Резольвента"
проводит
У нас также для школьников организованы
МОСКВА, СВАО, Учебный центр "РЕЗОЛЬВЕНТА"
