Подмножества по k элементов конечного множества s из n элементов в которых каждый элемент
Перейти к содержимому

Подмножества по k элементов конечного множества s из n элементов в которых каждый элемент

Подмножества по k элементов конечного множества s из n элементов в которых каждый элемент

Поочередный и одновременный выбор

    а) одновременно вынимают две карты из колоды: б) наугад зачеркивают 6 чисел из 49: в) случайно отбирают трех человек из 25:
    1-й способ : На роль капитана может быть выбран любой из 30 учащихся, а его заместитель – любой из 29 оставшихся учеников. Таким образом, получаем 30·29 = 870 способов. 2-й способ : Порядок важен, тогда по формуле числа размещений имеем способов.
    1-й способ : Нам не важно, кто капитан, а кто заместитель, нам нужны всего лишь два участника, поэтому получаем, что у нас каждая пара учащихся в произведении повторяется два раза. Поэтому ответом для второй задачи будет (30·29):2 =435 . 2-й способ : Без учета порядка применим формулу числа сочетаний .
    а) Порядок важен: А 27 3 = 27·26·25 = 17 550 б) Порядок неважен: .
Перейти к выполнению теста: Тест. Поочередный и одновременный выбор

Подмножества по k элементов конечного множества s из n элементов в которых каждый элемент

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

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

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

Дальнейшее развитие комбинаторика получила в работах Я. Бернулли, Г. Лейбница и Л. Эйлера.

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

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

Правило суммы и правило произведения

Правило суммы для выбора 2 объектов. Если объект А можно выбрать n способами, а объект В – другими m способами, то выбор «или А, или В» можно осуществить n + m способами.

При использовании правила суммы необходимо осознавать, что множество способов выбора объекта А и множество способов выбора объекта В не должно иметь общей части, в противном случае из суммы n + m нужно вычесть величину общей части множеств А и В.

Пример 5.3. Преступник может проникнуть в квартиру либо через входную дверь, либо через окно. Число способов проникновения через дверь – 4, через окно – 3. Сколько всего существует способов проникновения в квартиру?

Решение. Так как способы проникновения в квартиру через окно и через дверь различны, то мы можем воспользоваться правилом суммы. Тогда количество способов проникновения либо через окно, либо через дверь, т.е. количество различных способов проникновения в квартиру, будет равно 4+3=7.

Правило суммы для выбора m объектов. Если объект можно выбрать способами, объект другими способами, объект отличными от первых двух способами, и т.д., объект — способами, отличными от первых ( m -1), то выбор одного из объектов: или объекта , или объекта , …, или объекта можно осуществить + +…+ способами.

Правило произведения для выбора 2 объектов. Если объект А можно выбрать n способами и после этого действия объект В можно выбрать другими m способами, то выбор пары объектов (А, В) можно осуществить способами.

Действительно, каждый из n способов выбора объекта А можно скомбинировать с различными m способами выбора объекта В. А это и приводит к способам выбора пары (А, В). Правило произведения можно представить с помощью следующей таблицы:

где , i = 1, …, n способы выбора объекта А, , j = 1, …, m способы выбора объекта B и выбор объекта В не зависит от выбора объекта А.

Пример 5.4. Во взводе 25 курсантов. Сколько существует способов назначения командира взвода и его заместителя.

Решение . Сначала выберем командира взвода. Число способов выбора равно 25, так как каждый курсант может быть назначен на эту должность. После этого остается 24 курсанта, из которых может быть назначен заместитель командира взвода. Т.е. число способов назначения заместителя командира – 24. По правилу произведения количество способов назначения пары курсантов на указанные должности = 600.

Правило произведения для выбора m объектов. Если объект можно выбрать способами, после каждого такого выбора объект можно выбрать другими способами, после этого объект можно выбрать способами, и т.д., после выбора каждого из ( m -1) объектов -й может быть выбран способами, то выбор всех элементов ( , , …, ) в указанном порядке можно осуществить ž ž … ž способами.

Пример 5.5. Для запирания некоторых автоматических камер хранения, кейсов применяют цифровые кодовые замки, которые отпираются при наборе заданной комбинации цифр. Замок состоит из 4 дисков, на каждом из которых нанесены все цифры. Сколько времени необходимо злоумышленнику для перебора всех комбинаций замка, если на одну комбинацию он тратит 2 секунды.

Решение. При кодировании и открывании замка каждую цифру можно выбрать 10 способами. Всего цифр — 4, причем в комбинации важен порядок расположения цифр. Значит, по правилу произведения общее число комбинаций равно . Таким образом, для перебора всех комбинаций необходимо потратить секунд или 5 часов 33 минуты и 20 секунд непрерывной работы. Заметим, что найденное время необходимо для перебора всех комбинаций. Но нужная комбинация может вовсе и не быть последней.

Сочетания

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

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

Обозначим курсантов следующим образом: a , b , c , d , e . Из пяти курсантов составим всевозможные пары для несения службы в патруле:

Т.к., к примеру, пара ab и b а идентичны, то всего получается 10 различных вариантов наряда.

Такой способ решения является весьма нерациональным. Ведь если было бы необходимо выбрать наряд в 7 курсантов из 20, то (как это будет показано ниже) количество различных вариантов наряда составило бы более 77 тысяч. А попытка получить решение подобным образом окончилась бы полным провалом.

Для вывода общих формул комбинаторики рассмотрим вопрос: что общего и в чем заключаются отличия в примерах 5.4 и 5.6. Итак, в этих примерах идет речь о некотором конечном множестве элементов и о количестве его подмножеств, удовлетворяющих заданным требованиям. Так, в примере 5.4 рассматривалось множество курсантов учебной группы, состоявшее из 25 элементов (курсантов), и требовалось найти количество подмножеств, состоящих из 2 элементов (командир взвода и его заместитель). В примере 5.6 из пятиэлементного множества выделялись двухэлементные подмножества (наряды) и подсчитывалось их число.

Различие примеров заключалось в том, что в примере 5.6 подмножества различались лишь составом курсантов, а порядок элементов не имел значения. Действительно, наряд, состоящий из курсантов Иванова и Петрова, ни чем не отличался от наряда, состоящего из курсантов Петрова и Иванова. В примере 5.4, напротив, подмножества отличались не только своим составом, но и порядком расположения элементов. Назначение Иванова – командиром взвода, а Петрова – заместителем командира взвода отличается от комбинации выбора: Петров – командир взвода, Иванов – его заместитель.

Если подмножества различаются не только составом элементов, но и порядком следования элементов, то они называются упорядоченными. Неупорядоченные подмножества различаются только составом входящих в них элементов. Так, у множества, состоящего из 5 элементов, имеется 10 неупорядоченных подмножеств, состоящих из 2 элементов (см. пример 5.6), и 20 упорядоченных.

Пусть имеется множество, состоящее из n элементов. Каждое его неупорядоченное подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов . Из определения вытекает, что .

Сочетания из n элементов по k элементов – все k — элементные подмножества n – элементного множества, различающиеся только составом элементов. Подмножества, отличающиеся друг от друга порядком следования элементов, не считаются различными. Например, для четырехэлементного множество a , b , c , d сочетаниями из 4 элементов по 3 элемента являются подмножества: abc , abd, acd, bcd.

Число всех сочетаний из n по k элементов обозначается специальным символом . (Читается: «число сочетаний из n по k » или «С из n по k »). C – первая буква французского слова « combinasion » — «сочетание».

Число сочетаний из n по k элементов определяется следующей формулой:

Здесь мы использовали функцию факториала:

Запись читается: « n факториал».

1!=1, 2!=1 2, 3!=1 2 3=6, 4!=1 2 3 4=24, 5!=1 2 3 4 5=120, 6!=1 2 3 4 5 6=720 и т.д.

Из приведенных выше вычислений факториала ряда чисел очевидно следующее равенство:

n !=( n -1)! n для n >0.

Представив n ! в виде n !=( n k )! ( nk +1) ( n k +2) … ( n -1 ) n и сократив числитель и знаменатель формулы (5.2) на ( n k )!, получим следующую формулу для числа сочетаний из n по k элементов:

Если k =0, то . Действительно, существует только одно пустое (не содержащее элементов) подмножество множества из n элементов.

Пример 5.7. Сколько различных нарядов, состоящих из 7 курсантов, можно составить из взвода численностью 20 курсантов?

Решение. Количество различных нарядов равно числу сочетаний из 20 по 7 — . По формуле (5.3) получим

Итак, количество различных нарядов равно 77520.

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

Решение. Должно состояться столько поединков, сколько существует двухэлементных подмножеств у множества, состоящего из 15 элементов, т.е. их число равно . По формуле (5.3) получаем .

Итак, при встрече каждого из 15 спортсменов с каждым должно состояться 105 поединков.

Размещения

Пусть имеется множество, состоящее из n элементов. Каждое его упорядоченное подмножество, содержащее k элементов, называется размещением из n элементов по k элементов . Из определения вытекает, что .

Размещения из n элементов по k элементов – все k -элементные подмножества n – элементного множества, различающиеся не только составом элементов, но и порядком их следования. Например, для четырехэлементного множества a , b , c , d размещениями из 4 элементов по 3 элемента являются подмножества:

abc, acb, bac, bca, cab, cba,

abd, adb, bad, bda, dab, dba,

acd, adc, cad, cda, dac, dca,

bcd, bdc, cbd, cdb, dbc, dcb.

Число всех размещений из n по k элементов обозначается символом . (Читается: «число размещений из n по k » или «А из n по k »). А – первая буква французского слова « arrangement », что означает размещение, приведение в порядок.

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

Используя снова равенство n !=( n k )! ( nk +1) ( n k +2) … ( n -1 ) n и сократив числитель и знаменатель формулы (5.4) на ( n k )!, получим следующую формулу для числа размещений из n по k элементов:

Пример 5.9. Сколько различных нарядов, состоящих из 7 курсантов, можно составить из взвода численностью 20 курсантов, если каждый курсант в наряде отличается от другого своими обязанностями?

Решение. Теперь уже количество различных нарядов равно не числу сочетаний из 20 курсантов по 7 курсантам, а числу размещений из 20 по 7 — . По формуле (5.5) вычисляем = 390 700 800.

Пример 5.10. Сколько существует различных цифровых номеров автомашин, цифры которых не повторяются?

Решение. Если цифры номера машины не повторяются, то количество комбинаций номеров равно числу размещений из 10 (общее количество цифр) по 3 (количество цифр в номере автомашины), т.е. равно

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

Перестановками из n элементов называются размещения из n элементов по n элементов.

Перестановки являются частным случаем размещения. Так как каждая перестановка содержит все n элементов множества, то различные перестановки различаются только порядком следования элементов. Число перестановок из n элементов обозначают символом . Р – первая буква французского слова « permutation » — «перестановка».

Для того, чтобы вычислить число перестановок, подставим k = n в формулу (5.4) для нахождения размещений из n по n элементов:

Значит, число перестановок из n элементов . Т.е. множество из n элементов можно упорядочить n ! способами.

Еще раз перепишем формулы (5.2), (5.4) и (5.6) в виде:

Отсюда очевидно, что . Число размещений из n элементов по k элементов равно числу сочетаний из n элементов по k элементов, умноженному на число перестановок из k элементов.

Пример 5.11. С колько существует вариантов проведения собрания учебной группы, если количество выступающих на собрании – 4?

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

Комбинаторные объекты

Примером перестановки может служить задача о рассадке [math]n[/math] человек за стол по [math]n[/math] местам.

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

Определение:
Перестановки с повторениями (англ. permutations with repetitions) — те же перестановки, однако некоторые элементы могут встречаться несколько раз.

В пример можно привести следующую задачу: имеется набор книг [math]\[/math] , каждая из которых имеется в [math]k_1, k_2, \ldots, k_n[/math] экземплярах соответственно. Сколько существует способов переставить книги на полке?

Размещения

Определение:
Размещение [2] (англ. arrangement) из [math]n[/math] по [math]k[/math] — упорядоченный набор из [math]k[/math] различных элементов некоторого [math]n[/math] -элементного множества.

Примером размещения может служить задача о рассадке [math]k[/math] человек за стол по [math]n[/math] местам, где [math]n \gt k[/math] .

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

Определение:
Размещение с повторениями (англ. arrangement with repetitions), составленное из данных [math]n[/math] элементов по [math]k[/math] — отображение множества [math]k[/math] первых натуральных чисел [math]1, 2, \ldots, k[/math] в данное множество [math]\[/math] .

В пример можно привести следующую задачу: имеется [math]n[/math] книг, каждая в [math]k[/math] экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

Сочетания

Определение:
Сочетания [3] (англ. combinations) из [math]n[/math] по [math]k[/math] — набор [math]k[/math] элементов, выбранных из данных [math]n[/math] элементов.

Примером сочетания может служить задача о выборе [math]k[/math] книг из [math]n[/math] вариантов.

Сочетания с повторениями

Определение:
Сочетания с повторениями (англ. combinations with repetitions) — те же сочетания, только теперь даны [math]n[/math] типов элементов, из которых нужно выбрать [math]k[/math] элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.

В пример можно привести следующую задачу: имеется [math]n[/math] пирожных. Сколько способов купить [math]k[/math] пирожных?

Разбиение на неупорядоченные слагаемые

Определение:
Разбиение числа на неупорядоченные слагаемые (англ. partition) — представление числа [math]n[/math] в виде суммы слагаемых.

Основная статья: Нахождение количества разбиений числа на слагаемые

Разбиение на подмножества

Основная статья: Числа Стирлинга второго рода

Число комбинаторных объектов

Тип объекта Число объектов
Битовые векторы [math]2^[/math]
Перестановки [math]P_n = n![/math]
Перестановки с повторениями [math]\frac<(k_1 + k_2 + \ldots + k_n)!>[/math]
Размещения [math]A^_n = \frac<(n - k)!>[/math]
Размещения с повторениями [math]n^k[/math]
Сочетания [math]C^_n = \frac[/math]
Сочетания с повторениями [math]\widetilde^k_n = \frac<(n + k - 1)!> = C^k_[/math]
Разбиение на неупорядоченные слагаемые Нахождение количества разбиений числа на слагаемые
Разбиение на подмножества Числа Стирлинга второго порядка

Соответствующие доказательства

Число различных битовых векторов длины [math]n[/math] равно [math]2^[/math] .
Число различных перестановок из [math]n[/math] элементов равно [math]P_n = n![/math]

Число различных перестановок с повторениями из [math]k[/math] элементов с [math]n[/math] группами одинаковых элементов равно [math]\overline (k_1, k_2, \ldots, k_n) = \frac<(k_1 + k_2 + \ldots + k_n)!>[/math] , где [math]k_i[/math] — это количество одинаковых элементов в [math]i[/math] —ой группе.

Пусть нужно найти количество перестановок с повторениями на множестве [math]A[/math] из [math]k[/math] элементов. Будем учитывать, что в этом множестве [math]n[/math] групп одинаковых элементов. Количество перестановок из [math]k[/math] элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равно [math]k![/math] .

В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из [math]k_i[/math] . Таким образом количество перестановок с одинаковым первым элементом будет равно [math]k_1![/math] , для второго элемента — [math]k_2![/math] . Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок [math]k_1! \cdot k_2! \cdot \ldots \cdot k_n![/math] . Ответом будем являться частное количества всех перестановок и количества одинаковых.

Число различных размещений из [math]n[/math] элементов по [math]k[/math] равно [math]A^_n = \frac<(n - k)!>[/math]

Доказательство по индукции. База [math]k = 1[/math] , тогда количество размещений из [math]n[/math] по [math]1[/math] равно [math]n[/math] .

Число различных размещений с повторениями из [math]n[/math] элементов по [math]k[/math] равно [math]\overline = n^k[/math]

Докажем по индукции. База: [math]k = 1[/math] . Тогда [math] \overline = n[/math] .

Число различных сочетаний из [math]n[/math] элементов по [math]k[/math] равно [math]C^_n = \frac[/math]

Всего размещений из [math]n[/math] элементов по [math]k[/math] равно [math]A_n^k = \frac<(n - k)!>[/math] . В каждом размещении выбраны [math]k[/math] элементов из данного множества. Если игнорировать порядок этих выбранных [math]k[/math] элементов, мы получим некоторые сочетания из данного множества по [math]k[/math] . Другими словами, размещение с одним и тем же набором выбранных [math]k[/math] элементов задают одно и то же сочетание по [math]k[/math] элементов.

Число различных сочетаний с повторениями из [math]n[/math] элементов по [math]k[/math] равно [math]\overline = \frac<(n + k - 1)!> = C^k_[/math]

Рассмотрим двоичный вектор из [math](n+k-1)[/math] координат, в котором [math](n-1)[/math] нулей и [math]k[/math] единиц.

Будем считать нули разделителями, которые делят этот вектор на [math]n[/math] частей.

Тогда предположим, что число единиц в [math]i[/math] —м блоке — это число элементов [math]k_i[/math] в сочетании с повторением, которое соответствует этому вектору, где [math]k_i[/math] — это элемент из изначального множества с номером i.

Пример: Если у нас есть набор элементов 1 1 2 2 3, то [math]k_2[/math] = 2.

Получаем, что каждому сочетанию с повторениями из [math]n[/math] по [math]k[/math] соответствует некоторый вектор из нулей и единиц с [math](n+k-1)[/math] координатами, в котором [math](n-1)[/math] нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из [math]n[/math] по [math]k[/math] совпадает с числом таких векторов.

См. также

  • Генерация комбинаторных объектов в лексикографическом порядке
  • Получение следующего объекта
  • Получение номера по объекту
  • Получение объекта по номеру

Примечания

  1. ↑Википедия — Перестановки
  2. ↑Википедия — Размещения
  3. ↑Википедия — Сочетания

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

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

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

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

Теория множеств

Теория множеств
14.06.2012, 19:43

Пожалуйста, подскажите, как одолеть следующие доказательства?

$ A \subset B \subseteq C $

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

Я размышлял так (может, неправильно). Зафиксируем множество В. Тем самым мы зафиксируем некоторые k элементов из n. Соответственно n-k останется, и каждый из них может поучаствовать в формировании множества С. Рассмотрим множества, получаемые из множества В присоединением одного из n-k элементов. Таких множеств может быть создано $ C_^ $ штук. Множеств С, получаемых путём присоединения двух элементов, может быть создано $ C_^ $ штук. И так далее, вплоть до самого множества В — оно же единственное из $ C_^ $ множеств С, получаемых из В добавлением всех n-k элементов.

$C_</p> <p>Тогда ответ ^ + C_^ + . + C_^ = \sum_^ C_^$» />. Правилен ли он? И если да, то можно ли решать проще?</p> <p>4) Пусть А — непустое конечное множество. Подмножеств множества А, имеющих чётную мощность, столько же, сколько имеющих нечётную.</p> <p>Первый вопрос: учитываем ли мы пустое множество? Ведь его можно считать как множество нулевой, то есть чётной мощности, а можно не учитывать вообще. Мне кажется, что учитывать нужно. Как Вы считаете?</p> <p>Что до решения, то я сначала пробовал как-то через сочетания, но не вышло. В книжке дано указание зафиксировать некоторый элемент а из А и объединять в пары подмножества, которые отличаются только в точке а. Ну, зафиксировали мы его. Вот первые два множества: «чётное» и «нечётное»: <img decoding=и

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *