Мультисет

Эта статья о математической концепции. Информацию о структуре данных информатики см. в разделе Multiset (абстрактный тип данных) .

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

• Набор { a , b } содержит только элементы a и b , каждый из которых имеет кратность 1, когда { a , b } рассматривается как мультимножество.
• В мультимножестве { a , a , b } элемент a имеет кратность 2, а элемент b имеет кратность 1.
• В мультимножестве { a , a , a , b , b , b } кратность a и b равна 3.

Все эти объекты различны, если рассматривать их как мультимножества, хотя они представляют собой один и тот же набор, поскольку все они состоят из одних и тех же элементов. Как и в случае с множествами, в отличие от кортежей , порядок перечисления элементов не имеет значения при распознавании мультимножеств, поэтому { a , a , b } и { a , b , a } обозначают одно и то же мультимножество. Чтобы различать наборы и мультимножества, иногда используются обозначения, включающие квадратные скобки: мультимножество { a , a , b } может обозначаться [ a , a , b ] .

Мощность мультимножества — это сумма кратностей всех его элементов. Например, в мультимножестве { a , a , b , b , b , c } кратности членов a , b и c равны соответственно 2, 3 и 1, и, следовательно, мощность этого мультимножества равна 6.

Николаас Говерт де Брейн придумал слово «мультмножество» По словам Дональда Кнута, в 1970-х годах . раньше появления слова « мультмножество» Однако концепция мультимножества возникла на много столетий . Сам Кнут приписывает первое исследование мультимножеств индийскому математику Бхаскарачарье , который описал перестановки мультимножеств около 1150 года. Для этой концепции были предложены или использованы другие названия, в том числе список , группа , мешок , куча , образец , взвешенный набор , коллекция и люкс .

История

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

Практическая потребность в этой структуре привела к тому, что мультимножества несколько раз открывались заново, появляясь в литературе под разными названиями. Например, они были важны в ранних языках искусственного интеллекта , таких как QA4, где их называли « , мешками» — термином приписываемым Питеру Дойчу . Мультинабор также называют агрегатом, кучей, группой, выборкой, взвешенным набором, набором вхождений и набором элементов (конечно повторяющимся набором элементов).

Хотя мультимножества использовались неявно с древних времен, их явное исследование произошло гораздо позже. Первое известное исследование мультимножеств приписывается индийскому математику Бхаскарачарье около 1150 года, который описал перестановки мультимножеств. Работа Мариуса Низолиуса (1498–1576) содержит еще одно раннее упоминание концепции мультимножеств. Афанасий Кирхер нашел количество мультимножественных перестановок, при которых один элемент может повторяться. Жан Престе опубликовал общее правило для перестановок мультимножеств в 1675 году. Джон Уоллис более подробно объяснил это правило в 1685 году.

Мультимножества явно появились в работах Ричарда Дедекинда .

Другие математики формализовали мультимножества и начали изучать их как точные математические структуры в 20 веке. Например, Уитни (1933) описал обобщенные множества («множества», характеристические функции которых могут принимать любое целое значение — положительное, отрицательное или нулевое). Монро (1987) исследовал категорию Mul мультимножеств и их морфизмы , определив мультимножество как множество с отношением эквивалентности между элементами «одного и того же сорта », а морфизм между мультимножествами как функцию , которая учитывает сортировку . Он также ввел мультичисло : функцию f ( x ) от мультимножества до натуральных чисел , задающую кратность элемента x в мультимножестве. Монро утверждал, что понятия мультимножества и мультичисла часто смешивают без разбора, хотя оба они полезны.

Примеры

Одним из самых простых и естественных примеров является мультимножество простых делителей натурального числа n . Здесь базовым набором элементов является набор простых множителей числа n . Например, число 120 имеет простую факторизацию. $$120=2^{3}3^{1}5^{1}$$что дает мультимножество {2, 2, 2, 3, 5} .

Похожий пример — мультимножество решений алгебраического уравнения . решения . Например, квадратное уравнение имеет два Однако в некоторых случаях их число одинаково. Таким образом, мультимножеством решений уравнения может быть {3, 5} или {4, 4} . В последнем случае оно имеет решение кратности 2. В более общем смысле теорема алгебры утверждает, что комплексные решения полиномиального уравнения степени d фундаментальная всегда образуют мультимножество мощности d .

Частным случаем вышеизложенного являются собственные значения матрицы как , кратность которых обычно определяется как их кратность корней характеристического многочлена . кратности естественным образом определяются для собственных значений: их кратность как корни минимального многочлена и геометрическая кратность , которая определяется как размерность ядра матрицы A Однако две другие − λI (где λ — собственное значение матрицы A ). Эти три кратности определяют три мультимножества собственных значений, которые могут быть разными: пусть A — матрица размера n × n в жордановой нормальной форме , имеющая одно собственное значение. Его кратность равна n , его кратность как корня минимального многочлена — это размер наибольшего жорданового блока, а его геометрическая кратность — это количество жордановых блоков.

Определение

Мультимножество и может быть формально определено как упорядоченная пара ( A , m ), где A — базовый набор мультимножества, сформированный из его отдельных элементов, $m\colon A\to \mathbb {Z} ^{+}$ — это функция от A до набора положительных целых чисел, задающая кратность — то есть количество вхождений — элемента a в мультимножестве как число m ( a ) .

(Также возможно разрешить кратность 0 или $\infty$, особенно при рассмотрении субмультимножеств. Эта статья ограничена конечными положительными кратностями.)

Представив функцию m ее графиком (множеством упорядоченных пар $\{(a,m(a)):a\in A\}$) позволяет записать мультимножество { a , a , b } как ({ a , b }, {( a , 2), ( b , 1)}) , а мультимножество { a , b } как ({ a , b }, {( а , 1), ( б , 1)}) . Однако это обозначение обычно не используется; используются более компактные обозначения.

Если $A=\{a_{1},\ldots ,a_{n}\}$ — конечное множество , мультимножество ( A , m ) часто представляется как

$\left\{a_{1}^{m(a_{1})},\ldots ,a_{n}^{m(a_{n})}\right\},\quad$ иногда упрощается до $\quad a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})},$

где верхние индексы, равные 1, опущены. Например, мультимножество { a , a , b } может быть записано $\{a^{2},b\}$ или $a^{2}b.$ Если элементами мультимножества являются числа, возможна путаница с обычными арифметическими операциями , их обычно можно исключить из контекста. С другой стороны, последнее обозначение согласуется с тем фактом, что простая факторизация положительного целого числа представляет собой однозначно определенное мультимножество, как утверждается фундаментальной теоремой арифметики . Кроме того, моном представляет собой мультимножество неопределенных чисел ; например, моном x ³ и ² соответствует мультимножеству { x , x , x , y , y }.

Мультимножество соответствует обычному набору, если кратность каждого элемента равна 1. Индексированное семейство ( a _i ) _{i ∈ I} , где i меняется в пределах некоторого набора индексов I , может определять мультимножество, иногда обозначаемое { a _i } . С этой точки зрения базовый набор мультимножества задается образом семейства , а кратность любого элемента x — это количество значений индекса i таких, что $a_{i}=x$. В этой статье кратности считаются конечными, так что ни один элемент не встречается в семействе бесконечное количество раз; даже в бесконечном мультимножестве кратности являются конечными числами.

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

Основные свойства и операции

Элементы мультимножества обычно помещаются в фиксированный набор U , иногда называемый вселенной , который часто представляет собой набор натуральных чисел . Говорят, что элемент U , не принадлежащий данному мультимножеству, имеет кратность 0 в этом мультимножестве. Это расширяет функцию кратности мультимножества до функции от U до множества $\mathbb {N}$ неотрицательных целых чисел. Это определяет взаимно однозначное соответствие между этими функциями и мультимножествами, элементы которых находятся в U .

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

Поддержка ​ мультимножества $A$ во вселенной U является базовым набором мультимножества. Использование функции кратности $m$, оно характеризуется как $$\operatorname {Supp} (A):=\{x\in U\mid m_{A}(x)>0\}.$$

Мультимножество конечно , если его носитель конечен или, что то же самое, если его мощность $$|A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)$$конечно. Пустое мультимножество — это уникальное мультимножество с пустой опорой (базовым множеством) и, следовательно, мощностью 0.

Обычные операции с множествами можно распространить на мультимножества с помощью функции кратности аналогично использованию индикаторной функции для подмножеств. Далее A и B являются мультимножествами в данной вселенной U с функциями кратности $m_{A}$ и $m_{B}.$

• Включение: A входит в , B обозначается A ⊆ B , если $$m_{A}(x)\leq m_{B}(x)\quad \forall x\in U.$$
• : объединение Объединение (в некоторых контекстах называемое максимальным или наименьшим общим кратным ) A и B представляет собой мультимножество C с функцией кратности. $$m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \forall x\in U.$$
• Пересечение: пересечение представляет (в некоторых контекстах называемое нижней границей или наибольшим общим делителем ) A и B собой мультимножество C с функцией кратности. $$m_{C}(x)=\min(m_{A}(x),m_{B}(x))\quad \forall x\in U.$$
• Сумма: сумма представляет собой A . и B мультимножество C с функцией кратности $$m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \forall x\in U.$$ Его можно рассматривать как обобщение несвязного объединения множеств. Он определяет коммутативную моноидную структуру на конечных мультимножествах в данной вселенной. Этот моноид является свободным коммутативным моноидом , в основе которого лежит Вселенная.
• Разница: разница представляет собой A . и B мультимножество C с функцией кратности $$m_{C}(x)=\max(m_{A}(x)-m_{B}(x),0)\quad \forall x\in U.$$

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

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

Подсчет мультимножеств

Биекция между 3-подмножествами 7-множества (слева)
и 3-мультимножества с элементами из 5-множества (справа)
Итак, это иллюстрирует то, что ${\textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right).}$

См. Также: Звезды и бруски (комбинаторика).

Число мультимножеств мощности k с элементами, взятыми из конечного множества мощности n , иногда называют коэффициентом мультимножества или числом мультимножества . Это число записывается некоторыми авторами как $\textstyle \left(\!\!{n \choose k}\!\!\right)$, обозначение, напоминающее обозначение биномиальных коэффициентов ; оно используется, например, в (Stanley, 1997) и может произноситься как « n multichoose k », чтобы напоминать « n select k » для ${\tbinom {n}{k}}.$ Подобно биномиальному распределению , включающему биномиальные коэффициенты, существует отрицательное биномиальное распределение , в котором встречаются коэффициенты мультимножества. Коэффициенты мультимножества не следует путать с несвязанными полиномиальными коэффициентами , которые встречаются в полиномиальной теореме .

Значение коэффициентов мультимножества можно указать явно как $$\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},$$где второе выражение представляет собой биномиальный коэффициент; многие авторы фактически избегают отдельных обозначений и просто пишут биномиальные коэффициенты. Таким образом, количество таких мультимножеств совпадает с количеством подмножеств мощности k множества мощности n + k − 1 . Аналогию с биномиальными коэффициентами можно подчеркнуть, записав числитель в приведенном выше выражении как возрастающую факториальную степень. $$\left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},$$чтобы сопоставить выражение биномиальных коэффициентов с использованием падающей факториальной степени: $${n \choose k}={n^{\underline {k}} \over k!}.$$

Например, существует 4 мультимножества мощности 3 с элементами, взятыми из множества {1, 2} мощности 2 ( n = 2 , k = 3 ), а именно {1, 1, 1} , {1, 1, 2} , {1, 2, 2} , {2, 2, 2} . также есть 4 подмножества В множестве {1, 2, 3, 4} мощности 4 ( n + k − 1 ) мощности 3 , а именно {1, 2, 3} , {1, 2, 4} , {1 , 3, 4} , {2, 3, 4} .

Один простой способ доказать равенство коэффициентов мультимножества и биномиальных коэффициентов, приведенных выше, включает представление мультимножеств следующим образом. Во-первых, рассмотрим обозначения для мультимножеств, которые будут представлять { a , a , a , a , a , a , b , b , c , c , c , d , d , d , d , d , d , d } (6 a с, 2 б с, 3 в с, 7 д с) в таком виде:

 •  •  •  •  •  •  |  •  •  |  •  •  •  |  •  •  •  •  •  •  •

Это мультимножество мощности k = 18, составленное из элементов множества мощности n = 4 . Количество символов, включая точки и вертикальные линии, используемые в этом обозначении, составляет 18 + 4 − 1 . Количество вертикальных линий равно 4–1. Тогда количество мультимножеств мощности 18 представляет собой количество способов расположить 4–1 вертикальные линии среди 18 + 4–1 символов и, таким образом, является количеством подмножеств мощности 4. − 1 из множества мощности 18 + 4 − 1 . Эквивалентно, это количество способов расположить 18 точек среди 18 + 4 - 1 символов, что представляет собой количество подмножеств мощности 18 набора мощности 18 + 4 - 1 . Это $${4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,$$таким образом, это значение коэффициента мультимножества и его эквивалентов: $${\begin{aligned}\left(\!\!{4 \choose 18}\!\!\right)&={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3},\\[1ex]&={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},\\[1ex]&={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;1\cdot 2\cdot 3\quad } }},\\[1ex]&={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.\end{aligned}}$$

Из связи между биномиальными коэффициентами и коэффициентами мультимножества следует, что количество мультимножеств мощности k в множестве мощности n можно записать $$\left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.$$Кроме того, $$\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).$$

Рекуррентное отношение

Рекуррентное соотношение для коэффициентов мультимножества может быть задано как $$\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{for }}n,k>0$$с $$\left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{and}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.$$

Вышеупомянутое повторение можно интерпретировать следующим образом.Позволять $[n]:=\{1,\dots ,n\}$ быть исходным набором. Всегда существует ровно один (пустой) мультимножество размера 0, и если n = 0, мультимножеств большего размера нет, что дает начальные условия.

Теперь рассмотрим случай, когда n , k > 0 . Мультимножество мощности k с элементами из [ n ] может содержать или не содержать экземпляр последнего элемента n . Если он действительно появляется, то, удалив n один раз, останется мультимножество мощности k − 1 элементов из [ n ] , и любое такое мультимножество может возникнуть, что дает в общей сложности $$\left(\!\!{n \choose k-1}\!\!\right)$$ возможности.

Если n не появляется, то наше исходное мультимножество равно мультимножеству мощности k с элементами из [ n − 1] , из которых есть $$\left(\!\!{n-1 \choose k}\!\!\right).$$

Таким образом, $$\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right).$$

Создание серии

коэффициентов Производящая функция мультимножества очень проста: $$\sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{(1-t)^{n}}}.$$Поскольку мультимножества находятся во взаимно однозначном соответствии с мономами , $\left(\!\!{n \choose d}\!\!\right)$ также является числом мономов степени d от n неопределенных чисел. Таким образом, указанный ряд является также рядом Гильберта многочленов кольца $k[x_{1},\ldots ,x_{n}].$

Как $\left(\!\!{n \choose d}\!\!\right)$ является полиномом от n , он и производящая функция корректно определены для любого комплексного значения n .

Обобщение и подключение к отрицательному биномиальному ряду

Мультипликативная формула позволяет расширить определение коэффициентов мультимножества, заменив n произвольным числом α (отрицательным, действительным или комплексным): $$\left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .$$

Это определение дает обобщение формулы отрицательного бинома (с одной из переменных, установленной в 1), что оправдывает наименование формулы $\left(\!\!{\alpha \choose k}\!\!\right)$ отрицательные биномиальные коэффициенты: $$(1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X^{k}.$$

Эта формула ряда Тейлора действительна для всех комплексных чисел α и X с | Х | < 1 . Его также можно интерпретировать как тождество формальных степенных рядов в X , где на самом деле оно может служить определением произвольных степеней ряда с постоянным коэффициентом, равным 1; Дело в том, что с этим определением сохраняются все тождества, которые можно ожидать от возведения в степень , в частности

$$(1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{and}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )},$$и подобные формулы можно использовать для доказательства тождества коэффициентов мультимножества.

Если α — неположительное целое число n , то все члены с k > − n равны нулю, и бесконечный ряд становится конечной суммой. Однако для других значений α , включая целые положительные и рациональные числа , ряд бесконечен.

Приложения

Мультисеты имеют различные применения. Они становятся фундаментальными в комбинаторике . Мультимножества стали важным инструментом в теории реляционных баз данных , в которой часто используется термин « мешок синонимов» . Например, мультимножества часто используются для реализации отношений в системах баз данных. В частности, таблица (без первичного ключа) работает как мультимножество, поскольку в ней может быть несколько одинаковых записей. Аналогично, SQL работает с мультимножествами и возвращает идентичные записи. Например, рассмотрим «ВЫБРАТЬ имя из ученика». Если в таблице учащихся имеется несколько записей с именем «Сара», отображаются все они. Это означает, что результатом запроса SQL является мультимножество; если бы результатом был набор, повторяющиеся записи в наборе результатов были бы исключены. Другое применение мультимножеств — моделирование мультиграфов . может быть несколько ребер В мультиграфах между любыми двумя заданными вершинами . Таким образом, объект, отображающий ребра, является мультимножеством, а не набором.

Есть и другие приложения. Например, Рихард Радо использовал мультимножества как инструмент для исследования свойств семейств множеств. Он писал: «Понятие множества не принимает во внимание многократное появление любого из его членов, и тем не менее именно такого рода информация часто имеет важное значение. Нам нужно только подумать о множестве корней многочлена f. ( x ) или спектр линейного оператора ».

Обобщения

Различные обобщения мультимножеств были введены, изучены и применены для решения задач.

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

См. также

• Частота (статистика) как аналог множественности
• Квази-множества
• Теория множеств
• Модель «Мешок слов»
• Учебные материалы по разделам мультимножеств в Викиверситете