Сколько собственных подмножеств имеет множество содержащее 9 элементов

Количество подмножеств данного множества

Напомним понятие подмножества, введенное в главе 1. Если каждый элемент множества В принадлежит множеству А, то В называется подмножеством множества А: АВ или ВА.

Считается, что пустое множество Ø является подмножеством любого множества: Ø  А. Для всякого множества А имеет место соотношение АА. Если В  А, А  В, то А = В. Подмножество В множества А называется собственным, если В ≠ А и В ≠ Ø .

Если задано некоторое множество А, то можно рассматривать новое множество М(А) — множество всех его подмножеств. Через М_k(А) будем обозначать множество всех подмножеств множества А, которые имеют k элементов:

В  М_k(А), если |В| = k.

Поставим вопрос: сколько разных подмножеств имеет множество, состоящее из n элементов, сколько разных k-элементных подмножеств имеет это множество. В принятых обозначениях эти вопросы состоят в вычислении

|М(А)| и |М_k(А)|, если |А| = n

Пример. Пусть А = <а,b,с>, тогда

Покажем, что число всех подмножеств множества из n элементов равно 2 n . Действительно, переномеруем все элементы множества А, построим последовательность длины n из нулей и единиц по следующему принципу: на k-ом месте пишем 1, если элемент с номером k входит в подмножество, и 0, если элемент с номером k не входит в подмножество. Итак, каждому подмножеству соответствует своя последовательность длины n из нулей и единиц. Число всех возможных последовательностей длины n, составленных из нулей и единиц, равно по правилу умножения, 2×2×2× . ×2. Следовательно и число всех подмножеств множества А равно 2 n . Этот результат также очевиден, если представить себе, что процесс набора некоторого подмножества множества А эквивалентен разбиению множества А на две части, тогда для каждого из n элементов множества А есть две возможности: попасть в одну часть (подмножество) или попасть в другую часть (остаться в исходном множестве) и потому всего подмножеств 2 n — число разбиений множества А на две части.

Найдем теперь число всех k-элементных подмножеств множества А, т.е. |М_k(А)|. Чтобы построить k-элементное подмножество множества А, нужно к (k — 1)-элементному подмножеству присоединить один из (n — k + 1) элементов, не входящих в это подмножество.

Поскольку (k — 1)-элементных подмножеств имеется |М_k-1(А)| и каждое из них можно сделать k-элементным (n — k + 1) способами, то таким образом получим (n – k + l) |М_k-1(A)| подмножеств. Но не все они будут разными, так как каждое k-элементное подмножество можно построить k способами. Поэтому полученнок число в k раз больше, чем число k-элементных подмножеств. Следовательно,

|M_k(A)| = |М_k-1(А)| = |М_k-2(А)| = …= |М₁(А)|

В этой формуле |М₁(А)| — число одноэлементных подмножеств множества А, но это число равно количеству элементов в множестве А, то есть n. Подставляя вместо |М₁(А)|число n, получим:

|M_k(A)| = .

Таким образом, мы установили, что число k-элементных подмножеств множества А, состоящего из n элементов, равно числу сочетаний из n по k. Так как все подмножества состоят из всевозможных k-элементных подмножеств множества А, то приходим к уже известной нам формуле:

.

Обобщим теперь рассмотренную задачу о подмножествах следующим образом. Поставим вопрос: сколькими способами можно разложить множество А, состоящее из n элементов, на сумму из m подмножеств:

так, чтобы |А₁| = n₁, |А₂| = n₂, …, |А_m| = n_m, n_i > 0, ,

n₁ + n₂ +n₃ +. + n_m = n, множества A_i, , не имеют общих элементов. Очевидно, рассмотренный ранее вопрос о подмножествах множества А есть частный случай рассматриваемой ситуации при m = 2.

Все описанные разбиения множества А на m групп

А₁, А₂, А₃, …….,А_m можно получить так: возьмем произвольное n₁-элементное подмножество A₁ множества А (это можно сделать способами); среди (n – n₁) оставшихся элементов возьмем n₂-элементное подмножество А₂ (это можно сделать способами); и т.д. Общее число способов выбора различных множеств А₁, А₂, А₃, …….,А_m по правилу умножения равно

Такие выражения, как уже было сказано ранее, называются полиномиальными коэффициентами.

Теперь стало возможным ответить и на вопрос о полном числе способов разложения множества на сумму m подмножеств. Очевидно, полное число способов есть сумма по всем возможным способам разложения, то есть по всем n1, n2, n3. , nm = n, n_i > 0, , таким что n₁ + n₂ +n₃ +. + n_m =n.

Итак, полное число способов разложения множества А, состоящего из n элементов, определяется выражением

При m = 2 мы получаем общее число подмножеств множества А = 2 n .

Упражнения и задачи

Задача 1. На вершину горы ведет 9 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? Дайте ответ на этот же вопрос, если подъем и спуск осуществляются различными путями.

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

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

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

дискретная-математика — Количество разбиений

Разбиение множества A — это такое семейство его подмножеств, что каждый элемент A входит ровно в одно подмножество семейства. Найдите количество разбиений 9-элементного множества на три 3- элементные множества. (Из определения следует, что несущественен ни порядок элементов внутри подмножеств, ни порядок подмножеств внутри семейства.)

задан 12 Дек ’22 16:57

Очевидно это количество равно $%\frac<3!>=280$%

2 ответа

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

Рассмотрим сначала вариант, когда части пронумерованы. Тогда первую часть выбираем $%C_9^3$% способами, вторую $%C_6^3$%, а третья однозначно определяется. Теперь, если $%k$% — ответ для задачи из условия, то пронумеровать равноправные части можно $%3!=6$% способами, откуда $%6k=C_9^3C_6^3$%, и далее находим $%k$%.

Это стандартный способ решения, но есть другой способ, в котором все вычисления устные. Элементы множества у нас пронумерованы числами от 1 до 9. На первом этапе обладатель наименьшего номера (равного 1) выбирает себе двоих из оставшихся для набора в группу. Он делает это $%C_8^2=28$% способами. Остаётся 6 элементов, и пусть на втором этапе обладатель наименьшего номера среди оставшихся (мы не знаем, чему равен этот номер, но это не важно) набирает себе в группу каких-то двоих. Он делает это $%C_5^2=10$% способами, и разбиение готово. Ответом будет $%28\cdot10=280$%. Здесь уже никакого деления производить не надо.

отвечен 12 Дек ’22 18:08

@falcao Спасибо за второй способ (я раньше не знал о нём). Понятно, что этот способ годится для любого множества, не обязательно состоящего из чисел.

@Юрий Николаевич: я часто применяю этот способ при разборе задач. Даже для самого простого случая разбиения (2n)-элементного множества на две n-элементных части, вместо $%C_<2n>^n/2$% лучше брать $%C_<2n-1>^$%. Множества там, конечно, любые — мы их элементы только нумеруем.

Существует общая формула. Для ее вывода удобно закодировать разбиение множества заполнениями диаграммы Юнга.

Пусть имеется множество $%X,\ |X|=n$%, и мы хотим разбить его в дизъюнктное объединение $%k$% непустых непересекающихся подмножеств $$X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k.$$ Рассмотрим диаграмму Юнга $%\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$%, где $%\lambda_i=|X_i|$% и $%\lambda_1\geqslant\lambda_2\geqslant\dots\geqslant\lambda_k$%. При этом за $%m_i$% обозначим число строк длины $%i$% в диаграмме $%\lambda$%.
Будем называть заполнением диаграммы $%\lambda$% множеством $%X$% диаграмму $%\lambda$%, в клетки которой записаны все элементы множества $%X$% без повторений и считать, что заполненная диаграмма Юнга отвечает за такое разбиение множества $%X$%, в котором элементы, записанные в $%i$%-той строке принадлежат множеству $%X_i$%. Ясно, что теперь у нас имеется сюръективное отображение из множества разбиений множества $%X$% нужной нам формы и заполнениями диаграммы Юнга $%\lambda$%.
Всего заполнений диаграммы $%n!$% штук. Различные заполнения дают одинаковые разбиения в том случае, когда в диаграмме переставляются элементы одной строки между собой, и когда строки равной длины переставляются между собой как единое целое. Перестановок первого типа имеется $%\displaystyle\prod_^k\lambda_i!=\prod_^n(i!)^$% штук. Перестановок второго типа имеется $%\displaystyle\prod_^nm_i!$% штук.

Таким образом, всего разбиений множества $%X,\ |X|=n$% в дизъюнктное объединение $%m_1$% подмножеств из $%1$% элемента, $%m_2$% подмножеств из $%2$% элементов, . $%m_n$% подмножеств из $%n$% элементов имеется $$\dfrac<\displaystyle\prod_^n(i!)^m_i!>$$ штук.

Для данного примера у нас $%n=9,\ m_3=3$%, а все остальные $%m_i=0$%. По формуле получаем (с учетом того, что из произведения в знаменателе лишь третий множитель отличен от единицы), что число разбиений равно $$\dfrac<9!><(3!)^3\cdot3!>=\frac<9!><6^4>=280.$$

Калькулятор расчета подмножеств в множестве

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

Множество

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

Несобственные подмножества

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

Собственные подмножества

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

Из этого следует, что для набора из 3 элементов существует 2 3 — 2 = 6 собственных подмножеств, из 4 членов — 2 4 — 2 = 14 собственных подмножеств и так далее. К примеру, для множества существуют следующие подмножества:

1. ;
2. ;
3. ;
4. ;
5. ;
6. .

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

где n — количество элементов.

Это означает, что для того же набора добавятся также пустое множество и оно само.

Подмножества и парадоксы

Канторовская теория множеств зашла в тупик, когда ее постулаты породили парадоксы. Наиболее известной проблемой наивной теории множеств считается парадокс Рассела. Известный британский философ и ученый Бертран Рассел рассмотрел бесконечные множества как абстрактные объекты. Если любое множество считается подмножеством самого себя, то верно выражение A Î A. Допустим, существует глобальное множество S, содержащее в себе все наборы объектов, которые не включают самих себя.

Далее возникает вопрос, верно ли, что S Î S? Если верно, то выходит, что S не содержит самого себя, так как изначально набор S содержит все множества, не содержащие себя, следовательно, S Î S. Если неверно, значит, набор S не соответствует первичному определению, следовательно, S Î S.

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

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

Пример работы калькулятора

Допустим, у нас есть множество последовательных натуральных чисел мощностью 4. Это означает, что наш объект выглядит как А = <1, 2, 3, 4,>. Согласно формуле, для A существует 2 4 = 16 подмножества: 14 собственных и 2 несобственных. При помощи калькулятора рассчитаем эти составляющие. Мы получим:

• пустое множество — <>;
• одноэлементные наборы — <1>, <2>, <3>, <4>;
• двухэлементные — <1, 2>, <1, 3>, <1, 4>, <2, 3>, <2, 4>, <3, 4>;
• трехэлементные — <1, 2, 3>, <1, 2, 4>, <1, 3, 4>, <2, 3, 4>;
• само множество — <1, 2, 3, 4>.

Точно также вы можете рассчитать количество подмножеств для множества произвольной мощности.

Заключение

Множество — это элементарный математический объект, с которым можно осуществлять разные арифметические операции. Используйте наши онлайн-калькуляторы для работы с множественными объектами.