Multiset - Multiset

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

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

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

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

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

История

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

Практическая потребность в этой структуре привела к тому, что мультимножества переоткрывались несколько раз, появляясь в литературе под разными именами.^[4]:323 Например, они были важны в ранних языках искусственного интеллекта, таких как QA4, где они назывались сумки, термин, приписываемый Питеру Дойчу.^[5] Мультимножество также называется агрегатом, кучей, связкой, выборкой, взвешенным набором, набором вхождений и набором огней (набор с конечным числом повторений).^[4]:320[6]

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

Мультимножества явным образом появились в работе Ричард Дедекинд.^[11]:114[12]

Другие математики формализовали мультимножества и начали изучать их как точные математические структуры в 20 веке. Например, Уитни (1933) описал обобщенные множества ("наборы", чьи характеристические функции может принимать любое целое значение - положительное, отрицательное или нулевое).^{[4]:326[13]:405} Монро (1987) исследовал категория Mul мультимножеств и их морфизмов, определяя мультимножество как множество с отношением эквивалентности между элементами "одного и того же Сортировать", и морфизм между мультимножествами как функция, которая учитывает сортирует. Он также представил многозначный: функция f (x) из мультимножества в натуральные числа, давая множественность элемента Икс в мультимножестве. Монро утверждал, что концепции мультимножества и многозначности часто смешиваются без разбора, хотя оба они полезны.^{[4]:327–328[14]}

Примеры

Один из самых простых и естественных примеров - мультимножество основной факторы числа п. Здесь базовым набором элементов является набор простых делители из п. Например, число 120 имеет простые множители

${ displaystyle 120 = 2 ^ {3} 3 ^ {1} 5 ^ {1}}$

что дает мультимножество {2, 2, 2, 3, 5}.

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

Частным случаем из вышеперечисленного являются собственные значения матрицы, кратность которой обычно определяется как их кратность как корней характеристический многочлен. Однако две другие кратности естественно определяются для собственных значений, их кратности как корни минимальный многочлен, а геометрическая кратность, который определяется как измерение ядра А – λI (куда λ является собственным значением матрицы А). Эти три кратности определяют три мультимножества собственных значений, которые могут быть разными: Пусть А быть п×п матрица в Нормальная форма Джордана имеющий единственное собственное значение. Его кратность п, его кратность как корня минимального многочлена равна размеру наибольшей жордановой клетки, а ее геометрическая кратность - количеству жордановых блоков.

Определение

А мультимножество можно формально определить как 2-кортеж (А, м) куда А это базовый набор мультимножества, сформированного из его отдельных элементов, и ${ displaystyle m двоеточие A to mathbb {N} _ { geq 1}}$ это функция из А к набору положительный целые числа, давая множественность, то есть количество вхождений элемента а в мультимножестве как число м(а).

Представление функции м своим график, то есть набор заказанные пары ${ Displaystyle влево { влево (а, м влево (а вправо) вправо): а в А вправо },}$ позволяет записывать мультимножество {а, а, б} в качестве ({а, б}, {(а, 2), (б, 1)}), и мультимножество {а, б} в качестве ({а, б}, {(а, 1), (б, 1)}). Однако это обозначение обычно не используется, и используются более компактные обозначения.

Если ${ Displaystyle А = {а_ {1}, ldots, а_ {п} }}$ это конечный набор, мультимножество (А, м) часто представляется как

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

где верхние индексы, равные 1, опущены. Например, мультимножество {а, а, б} может быть написано ${ Displaystyle {а ^ {2}, б }}$ или же ${ displaystyle a ^ {2} b.}$ Если элементами мультимножества являются числа, возможна путаница с обычными арифметические операции, их обычно можно исключить из контекста. С другой стороны, последнее обозначение согласуется с тем фактом, что простые множители положительного целого числа является однозначно определенным мультимножеством, как утверждается основная теорема арифметики. Также одночлен это мультимножество неопределенный.^{[требуется дальнейшее объяснение ]}

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

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

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

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

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

В поддерживать мультимножества ${ displaystyle A}$ во вселенной U - базовый набор мультимножества. Используя функцию кратности ${ displaystyle m}$, он характеризуется как

${ displaystyle operatorname {Supp} (A): = left {x in U mid m_ {A} (x)> 0 right }}$.

Мультимножество конечный если его носитель конечен, или, что то же самое, если его мощность

${ displaystyle | A | = sum _ {x in operatorname {Supp} (A)} m_ {A} (x) = sum _ {x in U} m_ {A} (x)}$

конечно. В пустой мультимножество является уникальным мультимножеством с пустым носителем (базовым набором) и, следовательно, мощностью 0.

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

• Включение: А входит в B, обозначенный А ⊆ B, если

${ displaystyle forall x in U, m_ {A} (x) leq m_ {B} (x).}$

• Пересечение: в пересечение (в некоторых контекстах называется инфимум или же наибольший общий делитель) из А и B это мультимножество C с функцией кратности

${ Displaystyle m_ {C} (x) = min (m_ {A} (x), m_ {B} (x)) quad forall x in U.}$

• Союз: в союз (в некоторых контекстах называется максимум или же наименьшее общее кратное) из А и B это мультимножество C с функцией кратности

${ Displaystyle m_ {C} (x) = max (m_ {A} (x), m_ {B} (x)) quad forall x in U.}$^{[нужна цитата ]}

• Сумма: сумму мультимножеств можно рассматривать как обобщение несвязный союз наборов, и определяется

${ Displaystyle m_ {C} (x) = m_ {A} (x) + m_ {B} (x) quad forall x in U.}$

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

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

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

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

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

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

Значение коэффициентов мультимножества может быть явно задано как

${ displaystyle left (! ! {n выбрать k} ! ! right) = {n + k-1 выбрать k} = { frac {(n + k-1)!} {k ! , (n-1)!}} = {n (n + 1) (n + 2) cdots (n + k-1) over k!},}$

где второе выражение представляет собой биномиальный коэффициент; многие авторы фактически избегают отдельных обозначений и просто пишут биномиальные коэффициенты. Таким образом, количество таких мультимножеств совпадает с количеством подмножеств мощности k в наборе мощности п + k − 1. Аналогию с биномиальными коэффициентами можно подчеркнуть, записав числитель в приведенном выше выражении как возрастающая факторная мощность

${ displaystyle left (! ! {n выберите k} ! ! right) = {n ^ { overline {k}} над k!},}$

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

${ displaystyle {n choose k} = {n ^ { underline {k}} over k!}.}$

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

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

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

Это мультимножество мощности k = 18 из элементов набора мощности п = 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. Это

${ displaystyle {4 + 18-1 choose 4-1} = {4 + 18-1 choose 18} = 1330,}$

таким образом, это значение коэффициента мультимножества и его эквивалентов:

${ displaystyle left (! ! {4 choose 18} ! ! right) = {21 choose 18} = { frac {21!} {18! , 3!}} = {21 choose 3} = left (! ! {19 choose 3} ! ! right),}$

${ Displaystyle = { frac {{ color {красный} { 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}}}}}} ,}$

${ displaystyle = { 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 , times , mathbf {1 cdot 2 cdot 3 quad}}},}$

${ displaystyle = { frac {19 cdot 20 cdot 21} {1 cdot 2 cdot 3}}.}$

Можно определить обобщенный биномиальный коэффициент

${ displaystyle {n choose k} = {n (n-1) (n-2) cdots (n-k + 1) over k!}}$

в котором п не обязательно должно быть неотрицательным целым числом, но может быть отрицательным, нецелым или ненастоящим комплексное число. (Если k = 0, то значение этого коэффициента равно 1, потому что это пустой продукт.) Тогда количество мультимножеств мощности k в наборе мощности п является

${ displaystyle left (! ! {n choose k} ! ! right) = (- 1) ^ {k} {- n choose k}.}$

Отношение рецидива

А отношение повторения для мультимножества коэффициенты могут быть заданы как

${ Displaystyle left (! ! {n выберите k} ! ! right) = left (! ! {n выберите k-1} ! ! right) + left ( ! ! {n-1 выберите k} ! ! right) quad { mbox {for}} n, k> 0}$

с

${ Displaystyle left (! ! {n выберите 0} ! ! right) = 1, quad n in mathbb {N}, quad { mbox {и}} quad left (! ! {0 choose k} ! ! Right) = 0, quad k> 0.}$

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

Теперь рассмотрим случай, когда п,k > 0. Мультимножество мощности k с элементами из [п] может содержать или не содержать какой-либо экземпляр последнего элемента п. Если все-таки появится, то, удалив п один раз остается мультимножество мощности k - 1 элементов из [п], и может возникнуть любое такое мультимножество, что в сумме дает

${ displaystyle left (! ! {п выберите k-1} ! ! right)}$ возможности.

Если п не появляется, то наше исходное мультимножество равно мультимножеству мощности k с элементами из [п − 1], из которых есть

${ displaystyle left (! ! {n-1 выберите k} ! ! right).}$

Таким образом,

${ Displaystyle left (! ! {п выбрать k} ! ! right) = left (! ! {n выбрать k-1} ! ! right) + left ( ! ! {n-1 выберите k} ! ! right).}$

Генерация серии

В производящая функция коэффициентов мультимножества очень просто, будучи

${ displaystyle sum _ {d = 0} ^ { infty} left (! ! {n select d} ! ! right) t ^ {d} = { frac {1} {( 1-t) ^ {n}}}.}$

Поскольку мультимножества находятся во взаимно однозначном соответствии с одночленами, ${ displaystyle left (! ! {п выберите d} ! ! right)}$ также количество мономы степени d в п неопределенный. Таким образом, вышеуказанная серия также является Ряд Гильберта из кольцо многочленов ${ displaystyle k [x_ {1}, ldots, x_ {n}].}$

В качестве ${ displaystyle left (! ! {п выберите d} ! ! right)}$ является многочленом от п, он определен для любого сложный значение п.

Обобщение и связь с отрицательным биномиальным рядом

Мультипликативная формула позволяет расширить определение коэффициентов мультимножества, заменив п произвольным числом α (отрицательный, реальный, сложный):

${ displaystyle left (! ! { alpha выберите 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 {и произвольно}} alpha.}$

С помощью этого определения можно обобщить формулу отрицательного бинома (с одной из переменных, установленной в 1), что оправдывает вызов ${ displaystyle left (! ! { alpha выберите k} ! ! right)}$ отрицательные биномиальные коэффициенты:

${ displaystyle (1-X) ^ {- alpha} = sum _ {k = 0} ^ { infty} left (! ! { alpha select k} ! ! right) X ^ {k}.}$

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

${ displaystyle (1-X) ^ {- alpha} (1-X) ^ {- beta} = (1-X) ^ {- ( alpha + beta)} quad { text {и} } quad ((1-X) ^ {- alpha}) ^ {- beta} = (1-X) ^ {- (- alpha beta)}}$,

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

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

Приложения

Мультимножества имеют различные применения.^[6] Они становятся фундаментальными в комбинаторика.^{[15][16][17][18]} Мультимножества стали важным инструментом в теории реляционные базы данных, который часто использует синоним мешок.^[19][20][21] Например, мультимножества часто используются для реализации отношений в системах баз данных. В частности, таблица (без первичного ключа) работает как мультимножество, поскольку в ней может быть несколько одинаковых записей. По аналогии, SQL работает с мультимножествами и возвращает идентичные записи. Например, рассмотрим «ВЫБРАТЬ имя от студента». В случае, если в таблице учеников есть несколько записей с именем «sara», отображаются все они. Это означает, что результирующий набор SQL - это мультимножество. Если это был набор, повторяющиеся записи в наборе результатов удалялись. Еще одно применение мультимножества - моделирование мультиграфы. В мультиграфах между любыми двумя заданными вершинами может быть несколько ребер. Таким образом, объект, показывающий ребра, является мультимножеством, а не набором.

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

Обобщения

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (июнь 2013)

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

• Мультимножества с действительными значениями (в которых кратность элемента может быть любым действительным числом)^[22][23]

Это кажется простым, поскольку многие определения для нечетких множеств и мультимножеств очень похожи и могут быть приняты для мультимножеств с действительными значениями, просто заменив диапазон значений характеристической функции ([0, 1] или₀ = {0, 1, 2, 3, ...} соответственно) на ℝ₀⁺ = [0, ∞ [. Однако этот подход не может быть легко расширен для обобщенных нечетких множеств, которые используют посеть или же решетка вместо простой степени членства.Было разработано несколько других подходов к нечетким мультимножествам, которые не имеют этого ограничения.

• Нечеткие мультимножества^[24]
• Грубые мультимножества^[25]
• Гибридные наборы^[26]
• Мультимножества, кратность которых представляет собой любую действительную ступенчатую функцию^[27]
• Мягкие мультимножества^[28]
• Мягкие нечеткие мультимножества^[29]
• Именованные множества (объединение всех обобщений множеств)^{[30][31][32][33]}

Смотрите также

• Частота (статистика) как аналог множественности
• Квази-множества
• Теория множеств
• Разделы мультимножеств

Рекомендации