Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сочетания. В ряде комбинаторных задач требуется определить число k-элементных подмножеств множества из n элементов
В ряде комбинаторных задач требуется определить число k-элементных подмножеств множества из n элементов. В этом случае порядок следования компонентов несущественен, т.е. производится неупорядоченная выборка. В результате получают так называемые сочетания без повторения. Сочетаниями без повторений из n элементов по k называются отличающиеся друг от друга хотя бы одним элементом выборки длины k, составленные из n элементного множества. Число сочетаний без повторений из n элементов по k, обозначаемое как определяется, исходя из числа размещений без повторений с учетом того, что различных неупорядоченных векторов (подмножеств исходного множества) будет меньше в число раз, соответствующее числу перестановок без повторений из k элементов: . Пример. Определить число двухэлементных подмножеств множества, состоящего из трех элементов. Перечисляем все двухэлементные подмножества множества Х={х1, х2, х3}: {х1, х2}, {х1, х3}, {х2, х3}. Здесь мы имеем дело с сочетаниями из 3-х по 2: . Это величина в 2! раза меньше, чем число размещений из , поскольку компоненты двухэлементных векторов можно переставить Р2=2! способами. Пример. Сколькими способами можно выбрать 3 различных комбайна из 5 имеющихся? Число размещений из 5 по 3 без повторений: =5× 4× 3=60. Один и тот же набор комбайнов можно получить различными способами, например, векторы (а, b, с) и (b, а, с) дают один и тот же набор. Поскольку три элемента можно переставить Р3=3! =6 способами, то число способов выбора различных 3 комбайнов равно . В ряде комбинаторных задач требуется подсчитывать число различных составов векторов длины k из n элементного множества. Такие векторы-составы называются сочетаниями с повторениями из n элементов по k. Например, требуется составить механизированные бригады из 3 комплексов 2 типов и определить количество таких бригад. Порядок следования комплексов в векторе бригады роли не играет, а каждая бригада задается вектором длины 3 из 2 элементов, порядок компонент которого роли не играет. Получаем сочетания с повторениями из 2 элементов по 3: (m1, m1, m1), (m1, m2, m2), (m1, m1, m2), (m2, m2, m2), где m означает тип комплекса. Итак, возможно построить бригаду из трех комплексов первого типа, трех комплексов второго типа, двух комплексов второго типа и одного первого и, наконец, двух комплексов первого типа и одного второго, т.е. четырьмя способами. Определение числа сочетаний с повторениями можно произвести следующим образом [24]. Каждому сочетанию с повторениями из 2 по 3 ставится в однозначное соответствие вектор длины n+k-1=2+3-1=4, состоящий из 3 нулей и n-1=1 единицы:
В таком случае число сочетаний с повторениями, которое обозначается , равно числу перестановок с повторениями данного состава (вектор имеет одну единицу и три нуля), т.е. Р(3, 1)= =4. В общем случае, это выражение имеет вид , что соответствует выражению . Например, требуется составить подразделения из 6 рабочих 4 специальностей и определить количество способов формирования таких подразделений. Получаем сочетания с повторениями из 4-х элементов по 6: .
|