В математике мультимножество (или мешок , или mset ) — это модификация концепции множества , которая, в отличие от множества, [1] допускает множественные экземпляры для каждого из его элементов . Количество экземпляров, заданных для каждого элемента, называется кратностью этого элемента в мультимножестве. Как следствие, существует бесконечное количество мультимножеств, которые содержат только элементы a и b , но различаются по кратности своих элементов:
Все эти объекты различны, если рассматривать их как мультимножества, хотя они представляют собой один и тот же набор, поскольку все они состоят из одних и тех же элементов. Как и в случае с множествами, в отличие от кортежей , порядок перечисления элементов не имеет значения при различении мультимножеств, поэтому { a , a , b } и { a , b , a } обозначают одно и то же мультимножество. Чтобы различать наборы и мультимножества, иногда используются обозначения, включающие квадратные скобки: мультимножество { a , a , b } может обозначаться [ a , a , b ] . [2]
Мощность мультимножества — это сумма кратностей всех его элементов. Например, в мультимножестве { a , a , b , b , b , c } кратности членов a , b и c соответственно равны 2, 3 и 1, и, следовательно, мощность этого мультимножества равна 6.
По словам Дональда Кнута , Николаас Говерт де Брейн придумал слово «мультмножество» в 1970-х годах . [3] : 694 Однако концепция мультимножеств на много столетий предшествует появлению слова «мультмножество» . Сам Кнут приписывает первое исследование мультимножеств индийскому математику Бхаскарачарье , который описал перестановки мультимножеств около 1150 года. Для этой концепции предлагались или использовались и другие названия, в том числе список , группа , мешок , куча , образец , взвешенный набор , коллекция и люкс . [3] : 694
Уэйн Близард проследил мультимножества до самого происхождения чисел, утверждая, что «в древние времена число n часто представлялось набором из n штрихов, меток или единиц». [4] Эти и подобные коллекции объектов можно рассматривать как мультимножества, поскольку штрихи, метки или единицы измерения считаются неразличимыми. Это показывает, что люди неявно использовали мультимножества еще до появления математики.
Практическая потребность в этой структуре привела к тому, что мультимножества несколько раз открывались заново, появляясь в литературе под разными названиями. [5] : 323 Например, они были важны в ранних языках искусственного интеллекта , таких как QA4, где их называли «мешками» — термином, приписываемым Питеру Дойчу . [6] Мультинабор также называют агрегатом, кучей, группой, выборкой, взвешенным набором, набором вхождений и набором элементов (конечно повторяющимся набором элементов). [5] : 320 [7]
Хотя мультимножества неявно использовались с древних времен, их явное исследование произошло гораздо позже. Первое известное исследование мультимножеств приписывается индийскому математику Бхаскарачарье около 1150 года, который описал перестановки мультимножеств. [3] : 694 Работа Мариуса Низолиуса (1498–1576) содержит еще одно раннее упоминание концепции мультимножеств. [8] Афанасий Кирхер нашел количество мультимножествовых перестановок, когда один элемент может повторяться. [9] Жан Престе опубликовал общее правило для мультимножественных перестановок в 1675 году. [10] Джон Уоллис объяснил это правило более подробно в 1685 году. [11]
Мультимножества явно появились в работах Ричарда Дедекинда . [12] [13]
Другие математики формализовали мультимножества и начали изучать их как точные математические структуры в 20 веке. Например, Уитни (1933) описал обобщенные множества («множества», характеристические функции которых могут принимать любое целое значение — положительное, отрицательное или нулевое). [5] : 326 [14] : 405 Монро (1987) исследовал категорию Mul мультимножеств и их морфизмы , определяя мультимножество как множество с отношением эквивалентности между элементами «одного и того же вида » и морфизмом между мультимножествами как функция , которая учитывает сортировку . Он также ввел мультичисло : функцию f ( x ) от мультимножества до натуральных чисел , задающую кратность элемента x в мультимножестве. Монро утверждал, что понятия мультимножества и мультичисла часто смешивают без разбора, хотя оба они полезны. [5] : 327–328 [15]
Одним из самых простых и естественных примеров является мультимножество простых делителей натурального числа n . Здесь базовым набором элементов является набор простых множителей числа n . Например, число 120 имеет простую факторизацию.
Похожий пример — мультимножество решений алгебраического уравнения . Например, квадратное уравнение имеет два решения . Однако в некоторых случаях их число одинаково. Таким образом, мультимножеством решений уравнения может быть {3, 5} или {4, 4} . В последнем случае оно имеет решение кратности 2. В более общем смысле фундаментальная теорема алгебры утверждает, что комплексные решения полиномиального уравнения степени d всегда образуют мультимножество мощности d .
Частным случаем вышесказанного являются собственные значения матрицы , кратность которых обычно определяется как их кратность как корней характеристического многочлена . Однако две другие кратности естественным образом определяются для собственных значений: их кратность как корни минимального многочлена и геометрическая кратность , которая определяется как размерность ядра матрицы A − λI (где λ — собственное значение матрицы A ). Эти три кратности определяют три мультимножества собственных значений, которые могут быть разными: пусть A — матрица размера n × n в жордановой нормальной форме , имеющая одно собственное значение. Его кратность равна n , его кратность как корня минимального многочлена — это размер наибольшего жорданового блока, а его геометрическая кратность — это количество жордановых блоков.
Мультимножество может быть формально определено как упорядоченная пара ( A , m ) , где A — базовый набор мультимножества, сформированный из его отдельных элементов, и функция от A до набора положительных целых чисел, дающая кратность — то есть , количество вхождений – элемента a в мультимножестве как число m ( a ) .
(Также возможно разрешить кратность 0 или , особенно при рассмотрении подмультимножеств. [16] Эта статья ограничена конечными положительными кратностями.)
Представление функции m ее графиком (набором упорядоченных пар ) позволяет записать мультимножество { a , a , b } как ({ a , b }, {( a , 2), ( b , 1)}) и мультимножество { a , b } как ({ a , b }, {( a , 1), ( b , 1)}) . Однако это обозначение обычно не используется; используются более компактные обозначения.
Если — конечное множество , мультимножество ( A , m ) часто представляется как
где верхние индексы, равные 1, опущены. Например, мультимножество { a , a , b } может быть записано или Если элементами мультимножества являются числа, возможна путаница с обычными арифметическими операциями , которые обычно можно исключить из контекста. С другой стороны, последнее обозначение согласуется с тем фактом, что простая факторизация положительного целого числа представляет собой однозначно определенное мультимножество, как утверждается фундаментальной теоремой арифметики . Кроме того, моном — это мультимножество неопределенных ; например, моном x 3 y 2 соответствует мультимножеству { x , x , x , y , y }.
Мультимножество соответствует обычному набору, если кратность каждого элемента равна 1. Индексированное семейство ( a i ) i ∈ I , где i меняется в пределах некоторого набора индексов I , может определять мультимножество, иногда обозначаемое { a i } . С этой точки зрения основной набор мультимножества задается образом семейства , а кратность любого элемента x — это количество значений индекса i таких, что . В этой статье кратности считаются конечными, так что ни один элемент не встречается в семействе бесконечное количество раз; даже в бесконечном мультимножестве кратности являются конечными числами.
Можно расширить определение мультимножества, разрешив кратностям отдельных элементов быть бесконечными кардиналами вместо положительных целых чисел, но не все свойства переносятся в это обобщение.
Элементы мультимножества обычно помещаются в фиксированный набор U , иногда называемый вселенной , который часто представляет собой набор натуральных чисел . Говорят, что элемент U , не принадлежащий данному мультимножеству, имеет кратность 0 в этом мультимножестве. Это расширяет функцию кратности мультимножества до функции от U до набора неотрицательных целых чисел. Это определяет взаимно однозначное соответствие между этими функциями и мультимножествами, элементы которых находятся в U .
Эту расширенную функцию множественности обычно называют просто функцией множественности , и ее достаточно для определения мультимножеств, когда вселенная, содержащая элементы, фиксирована. Эта функция множественности является обобщением индикаторной функции подмножества и имеет с ней некоторые общие свойства.
Поддержка мультимножества в юниверсе U является базовым набором мультимножества. Используя функцию кратности , она характеризуется как
Мультимножество конечно , если его носитель конечен или, что то же самое, если его мощность
Обычные операции с множествами можно распространить на мультимножества с помощью функции кратности аналогично использованию индикаторной функции для подмножеств. Далее A и B являются мультимножествами в данной вселенной U с функциями кратности и
Два мультимножества не пересекаются , если их носители являются непересекающимися множествами . Это эквивалентно утверждению, что их пересечение является пустым мультимножеством или что их сумма равна их объединению.
Для конечных мультимножеств существует принцип включения-исключения (аналогичный принципу для множеств ), утверждающий, что конечное объединение конечных мультимножеств есть разность двух сумм мультимножеств: в первой сумме мы рассматриваем все возможные пересечения нечетного числа заданные мультимножества, а во второй сумме рассматриваются все возможные пересечения четного числа данных мультимножеств. [ нужна цитата ]
Число мультимножеств мощности k с элементами, взятыми из конечного множества мощности n , иногда называют коэффициентом мультимножества или числом мультимножества . Это число записывается некоторыми авторами как обозначение, которое должно напоминать обозначение биномиальных коэффициентов ; оно используется, например, в (Stanley, 1997) и может произноситься как « n multichoose k », чтобы напоминать « n select k » для Подобно биномиальному распределению , включающему биномиальные коэффициенты, существует отрицательное биномиальное распределение , в котором встречаются коэффициенты мультимножества. . Коэффициенты мультимножества не следует путать с несвязанными полиномиальными коэффициентами , которые встречаются в полиномиальной теореме .
Значение коэффициентов мультимножества можно указать явно как
Например, существует 4 мультимножества мощности 3 с элементами, взятыми из множества {1, 2} мощности 2 ( n = 2 , k = 3 ), а именно {1, 1, 1} , {1, 1, 2} , {1, 2, 2} , {2, 2, 2} . В множестве {1, 2, 3, 4} мощности 4 ( n + k − 1 ) также есть 4 подмножества мощности 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 . Это
Из связи между биномиальными коэффициентами и коэффициентами мультимножества следует, что количество мультимножеств мощности k в множестве мощности n можно записать
Рекуррентное соотношение для коэффициентов мультимножества может быть задано как
Вышеупомянутое повторение можно интерпретировать следующим образом. Пусть это исходный набор. Всегда существует ровно один (пустой) мультимножество размера 0, и если n = 0 , мультимножеств большего размера нет, что дает начальные условия.
Теперь рассмотрим случай, когда n , k > 0 . Мультимножество мощности k с элементами из [ n ] может содержать или не содержать экземпляр последнего элемента n . Если он появляется, то, удалив n один раз, останется мультимножество мощности k − 1 элементов из [ n ] , и любое такое мультимножество может возникнуть, что дает в общей сложности
Если n не появляется, то наше исходное мультимножество равно мультимножеству мощности k с элементами из [ n − 1] , из которых есть
Таким образом,
Производящая функция коэффициентов мультимножества очень проста:
Поскольку это полином от n , он и производящая функция четко определены для любого комплексного значения n .
Мультипликативная формула позволяет расширить определение коэффициентов мультимножества, заменив n произвольным числом α (отрицательным, действительным или комплексным):
Благодаря этому определению получается обобщение формулы отрицательного бинома (с одной из переменных, установленной в 1), что оправдывает использование отрицательных биномиальных коэффициентов:
Эта формула ряда Тейлора действительна для всех комплексных чисел α и X с | Х | < 1 . Его также можно интерпретировать как тождество формального степенного ряда в X , где на самом деле оно может служить определением произвольных степеней ряда с постоянным коэффициентом, равным 1; Дело в том, что с этим определением сохраняются все тождества, которые можно ожидать от возведения в степень , в частности
Если α — неположительное целое число n , то все члены с k > − n равны нулю, и бесконечный ряд становится конечной суммой. Однако для других значений α , включая целые положительные и рациональные числа , ряд бесконечен.
Мультисеты имеют различные применения. [7] Они становятся фундаментальными в комбинаторике . [17] [18] [19] [20] Мультимножества стали важным инструментом в теории реляционных баз данных , в которой часто используется синоним « мешок» . [21] [22] [23] Например, мультимножества часто используются для реализации отношений в системах баз данных. В частности, таблица (без первичного ключа) работает как мультимножество, поскольку в ней может быть несколько одинаковых записей. Аналогично, SQL работает с мультимножествами и возвращает идентичные записи. Например, рассмотрим «ВЫБРАТЬ имя из ученика». Если в таблице учащихся имеется несколько записей с именем «Сара», отображаются все они. Это означает, что результатом запроса SQL является мультимножество; если бы результатом был набор, повторяющиеся записи в наборе результатов были бы исключены. Другое применение мультимножеств — моделирование мультиграфов . В мультиграфах между любыми двумя заданными вершинами может быть несколько ребер . Таким образом, объект, отображающий ребра, является мультимножеством, а не набором.
Есть и другие приложения. Например, Рихард Радо использовал мультимножества как инструмент для исследования свойств семейств множеств. Он писал: «Понятие множества не принимает во внимание многократное появление любого из его членов, и тем не менее именно такого рода информация часто имеет важное значение. Нам нужно только подумать о множестве корней многочлена f . ( x ) или спектр линейного оператора ». [5] : 328–329.
Различные обобщения мультимножеств были введены, изучены и применены для решения задач.
Под множеством (Menge) следует понимать всякую совокупность в целое (Zusammenfassung zu einem Gansen) M определенных и отдельных предметов m (с.85)
{{cite book}}
: CS1 maint: location missing publisher (link)