Мультисет
Математический набор с разрешенными повторениями

В математике мультимножество (или мешок , или mset ) — это модификация концепции множества , которая, в отличие от множества, [1] допускает множественные экземпляры для каждого из своих элементов . Количество экземпляров, заданных для каждого элемента, называется кратностью этого элемента в мультимножестве. Как следствие, существует бесконечное число мультимножеств, которые содержат только элементы 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 ] . [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 имеет разложение на простые множители , которое дает мультимножество {2, 2, 2, 3, 5} . 120 = 2 3 3 1 5 1 , {\displaystyle 120=2^{3}3^{1}5^{1},}

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

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

Определение

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

(Также можно допустить кратность 0 или , особенно при рассмотрении подмультимножеств. [16] Эта статья ограничена конечными положительными кратностями.) ∞ {\displaystyle \infty}

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

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

{ а 1 м ( а 1 ) , … , а н м ( а н ) } , {\displaystyle \left\{a_{1}^{m(a_{1})},\ldots ,a_{n}^{m(a_{n})}\right\},\quad } иногда упрощают до а 1 м ( а 1 ) ⋯ а н м ( а н ) , {\displaystyle \quad a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})},}

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

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

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

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

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

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

Поддержка мультимножества в универсуме U — это базовый набор мультимножества. Используя функцию кратности , он характеризуется как А {\displaystyle А} м {\displaystyle м} Супп ⁡ ( А ) := { х ∈ У ∣ м А ( х ) > 0 } . {\displaystyle \operatorname {Supp} (A):=\{x\in U\mid m_{A}(x)>0\}.}

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

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

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

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

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

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

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

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

Значение коэффициентов мультимножества может быть задано явно как где второе выражение является биномиальным коэффициентом; [a] многие авторы на самом деле избегают отдельной записи и просто пишут биномиальные коэффициенты. Таким образом, число таких мультимножеств равно числу подмножеств мощности k множества мощности n + k − 1. Аналогию с биномиальными коэффициентами можно подчеркнуть, записав числитель в приведенном выше выражении как возрастающую факторную степень, чтобы соответствовать выражению биномиальных коэффициентов, использующему убывающую факторную степень: ( ( н к ) ) = ( н + к − 1 к ) = ( н + к − 1 ) ! к ! ( н − 1 ) ! = н ( н + 1 ) ( н + 2 ) ⋯ ( н + к − 1 ) к ! , {\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!},} ( ( н к ) ) = н к ¯ к ! , {\displaystyle \left(\!\!{n \выберите k}\!\!\right)={n^{\overline {k}} \over k!},} ( н к ) = н к _ к ! . {\displaystyle {n \выберите 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 подмножества мощности 3 в множестве {1, 2, 3, 4} мощности 4 ( n + k − 1 ), а именно {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 } (6 a s, 2 b s , 3 c s, 7 d s) в этой форме:

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

Это мультимножество мощности 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 4 − 1 ) = ( 4 + 18 − 1 18 ) = 1330 , {\displaystyle {4+18-1 \выберите 4-1}={4+18-1 \выберите 18}=1330,} ( ( 4 18 ) ) = ( 21 18 ) = 21 ! 18 ! 3 ! = ( 21 3 ) , = 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⋅ 13 ⋅ 14 ⋅ 15 ⋅ 16 ⋅ 17 ⋅ 18 ⋅ 19 ⋅ 20 ⋅ 21 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 ⋅ 10 ⋅ 11 ⋅ 12 ⋅ 13 ⋅ 14 ⋅ 15 ⋅ 16 ⋅ 17 ⋅ 18 , = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋯ 16 ⋅ 17 ⋅ 18 ⋅ 19 ⋅ 20 ⋅ 21 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋯ 16 ⋅ 17 ⋅ 18 ⋅ 1 ⋅ 2 ⋅ 3 , = 19 ⋅ 20 ⋅ 21 1 ⋅ 2 ⋅ 3 . {\displaystyle {\begin{align}\left(\!\!{4 \выберите 18}\!\!\right)&={21 \выберите 18}={\frac {21!}{18!\,3!}}={21 \выберите 3},\\[1ex]&={\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 {красный}{\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{выровнено}}}

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

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

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

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

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

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

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

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

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

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

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

Мультипликативная формула позволяет расширить определение коэффициентов мультимножества, заменив n произвольным числом α (отрицательным, действительным или комплексным): ( ( α k ) ) = α k ¯ k ! = α ( α + 1 ) ( α + 2 ) ⋯ ( α + k − 1 ) k ( k − 1 ) ( k − 2 ) ⋯ 1 for  k ∈ N  and arbitrary  α . {\displaystyle \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), что оправдывает использование отрицательных биномиальных коэффициентов: ( ( α k ) ) {\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)} ( 1 − X ) − α = ∑ k = 0 ∞ ( ( α k ) ) X k . {\displaystyle (1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X^{k}.}

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

( 1 − X ) − α ( 1 − X ) − β = ( 1 − X ) − ( α + β ) and ( ( 1 − X ) − α ) − β = ( 1 − X ) − ( − α β ) , {\displaystyle (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 равны нулю, и бесконечный ряд становится конечной суммой. Однако для других значений α , включая положительные целые числа и рациональные числа , ряд бесконечен.

Приложения

Мультимножества имеют различные применения. [7] Они становятся фундаментальными в комбинаторике . [17] [18] [19] [20] Мультимножества стали важным инструментом в теории реляционных баз данных , которая часто использует синоним bag . [21] [22] [23] Например, мультимножества часто используются для реализации отношений в системах баз данных. В частности, таблица (без первичного ключа) работает как мультимножество, поскольку она может иметь несколько идентичных записей. Аналогично SQL работает с мультимножествами и возвращает идентичные записи. Например, рассмотрим «SELECT name from Student». В случае, если в таблице student есть несколько записей с именем «Sara», все они отображаются. Это означает, что результатом запроса SQL является мультимножество; если бы вместо этого результатом был набор, повторяющиеся записи в результирующем наборе были бы устранены. Другое применение мультимножеств — моделирование мультиграфов . В мультиграфах может быть несколько ребер между любыми двумя заданными вершинами . Таким образом, сущность, определяющая ребра, является мультимножеством, а не множеством.

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

Обобщения

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

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

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

Примечания

  1. ^ Формула ⁠ ⁠ ( n + k − 1 k ) {\displaystyle {\tbinom {n+k-1}{k}}} не работает для n = 0 (где обязательно также k = 0 ), если рассматривать ее как обычный биномиальный коэффициент, поскольку она вычисляется как ⁠ ⁠ ( − 1 0 ) {\displaystyle {\tbinom {-1}{0}}} , однако формула n ( n +1)( n +2)...( n + k  −1)/ k ! работает в этом случае, поскольку числитель является пустым произведением, дающим 1/0! = 1 . Однако ⁠ ⁠ ( n + k − 1 k ) {\displaystyle {\tbinom {n+k-1}{k}}} имеет смысл для n = k = 0, если ее интерпретировать как обобщенный биномиальный коэффициент ; действительно ⁠ ⁠ ( n + k − 1 k ) {\displaystyle {\tbinom {n+k-1}{k}}} рассматриваемый как обобщенный биномиальный коэффициент, равен крайней правой части приведенного выше уравнения.

Ссылки

  1. ^ Кантор, Георг ; Журден, Филип Э.Б. (переводчик) (1895). «beiträge zur begründung der transfiniten Mengenlehre» [вклад в создание теории трансфинитных чисел]. Mathematische Annalen (на немецком языке). XLVI, XLIX. New York Dover Publications (английский перевод 1954 г.): 481–512 , 207–246 . Архивировано из оригинала 10 июня 2011 г. Под множеством (Menge) следует понимать всякую совокупность в целое (Zusammenfassung zu einem Gansen) M определенных и отдельных предметов m (с.85)
  2. ^ Хейн, Джеймс Л. (2003). Дискретная математика . Jones & Bartlett Publishers. С. 29–30. ISBN 0-7637-2210-3.
  3. ^ abc Кнут, Дональд Э. (1998). Получисленные алгоритмы . Искусство программирования . Том 2 (3-е изд.). Эддисон Уэсли . ISBN 0-201-89684-2.
  4. ^ Близард, Уэйн Д. (1989). «Теория мультимножеств». Notre Dame Journal of Formal Logic . 30 (1): 36– 66. doi : 10.1305/ndjfl/1093634995 .
  5. ^ abcde Blizard, Wayne D. (1991). «Развитие теории мультимножеств». Modern Logic . 1 (4): 319–352 .
  6. ^ Рулифсон, Дж. Ф.; Дерксон, Дж. А.; Уолдингер, Р. Дж. (ноябрь 1972 г.). QA4: Процедурное исчисление для интуитивного рассуждения (технический отчет). SRI International. 73.
  7. ^ ab Singh, D.; Ibrahim, AM; Yohanna, T.; Singh, JN (2007). «Обзор приложений мультимножеств». Novi Sad Journal of Mathematics . 37 (2): 73–92 .
  8. ^ Анджелелли, И. (1965). «Неправильное понимание Лейбницем понятия Низолиуса «multitudo»". Notre Dame Journal of Formal Logic (6): 319–322 .
  9. ^ Кирхер, Афанасий (1650). Мусургия Универсалис. Рим: Корбеллетти.
  10. ^ Престе, Жан (1675). Элементы математики . Париж: Андре Пралар.
  11. ^ Уоллис, Джон (1685). Трактат алгебры . Лондон: Джон Плейфорд.
  12. ^ Дедекинд, Ричард (1888). Был ли Sind и Sollen die Zahlen? . Брауншвейг: Просмотрег. п. 114.
  13. ^ ab Syropoulos, Apostolos (2000). "Математика мультимножеств". В Calude, Cristian; Paun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto (ред.). Обработка мультимножеств, математические, компьютерные науки и молекулярные вычисления с точки зрения [Семинар по обработке мультимножеств, WMP 2000, Куртя-де-Арджеш, Румыния, 21–25 августа 2000 г.] . Заметки лекций по информатике. Том 2235. Springer. стр.  347–358 . doi :10.1007/3-540-45523-X_17. ISBN 978-3-540-43063-6.
  14. ^ Уитни, Хасслер (1933). «Характеристические функции и алгебра логики». Annals of Mathematics . 34 (3): 405– 414. doi :10.2307/1968168. JSTOR  1968168.
  15. ^ Монро, терапевт (1987). «Понятие мультимножества». Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 (2): 171–178 . doi :10.1002/malq.19870330212.
  16. ^ См., например, Ричард Бруальди, Введение в комбинаторику , Пирсон.
  17. ^ Айгнер, М. (1979). Комбинаторная теория . Нью-Йорк/Берлин: Springer Verlag.
  18. ^ Андерсон, И. (1987). Комбинаторика конечных множеств . Оксфорд: Clarendon Press. ISBN 978-0-19-853367-2.
  19. ^ Стэнли, Ричард П. (1997). Перечислительная комбинаторика. Том 1. Cambridge University Press. ISBN 0-521-55309-1.
  20. ^ Стэнли, Ричард П. (1999). Перечислительная комбинаторика . Том 2. Cambridge University Press. ISBN 0-521-56069-1.
  21. ^ Grumbach, S.; Milo, T (1996). «К трактуемым алгебрам для сумок». Журнал компьютерных и системных наук . 52 (3): 570–588 . doi : 10.1006/jcss.1996.0042 .
  22. ^ Либкин, Л.; Вонг, Л. (1994). «Некоторые свойства языков запросов для сумок». Труды семинара по языкам программирования баз данных . Springer Verlag. С.  97–114 .
  23. ^ Либкин, Л.; Вонг, Л. (1995). «О представлении и запросе неполной информации в базах данных с сумками». Information Processing Letters . 56 (4): 209– 214. doi :10.1016/0020-0190(95)00154-5.
  24. ^ Близард, Уэйн Д. (1989). «Вещественные мультимножества и нечеткие множества». Нечеткие множества и системы . 33 : 77–97 . doi :10.1016/0165-0114(89)90218-2.
  25. ^ Близард, Уэйн Д. (1990). «Отрицательное членство». Notre Dame Journal of Formal Logic . 31 (1): 346–368 . doi : 10.1305/ndjfl/1093635499 . S2CID  42766971.
  26. ^ Ягер, РР (1986). «О теории сумок». Международный журнал общих систем . 13 : 23–37 . doi :10.1080/03081078608934952.
  27. ^ Гржимала-Буссе, Дж. (1987). «Изучение примеров на основе грубых мультимножеств». Труды 2-го Международного симпозиума по методологиям для интеллектуальных систем . Шарлотт, Северная Каролина. С.  325–332 .{{cite book}}: CS1 maint: location missing publisher (link)
  28. ^ Лёб, Д. (1992). «Наборы с отрицательным числом элементов». Успехи математики . 91 : 64– 74. doi : 10.1016/0001-8708(92)90011-9 .
  29. ^ Миямото, С. (2001). "Нечеткие мультимножества и их обобщения". Обработка мультимножеств . Конспект лекций по информатике. Том 2235. С.  225–235 . doi :10.1007/3-540-45523-X_11. ISBN 978-3-540-43063-6.
  30. ^ Альхазалех, С.; Саллех, А.Р.; Хассан, Н. (2011). «Теория мягких мультимножеств». Прикладные математические науки . 5 (72): 3561– 3573.
  31. ^ Alkhazaleh, S.; Salleh, AR (2012). «Нечеткая мягкая теория мультимножеств». Abstract and Applied Analysis . 2012 : 1– 20. doi : 10.1155/2012/350603 .
  32. ^ Бергин, Марк (1990). «Теория именованных множеств как фундаментальная основа математики». Структуры в математических теориях . Сан-Себастьян. С.  417–420 .
  33. ^ Бергин, Марк (1992). «О концепции мультимножества в кибернетике». Кибернетика и системный анализ . 3 : 165–167 .
  34. ^ Бергин, Марк (2004). «Единые основы математики». arXiv : math/0403186 .
  35. ^ Burgin, Mark (2011). Теория именованных множеств . Математические исследовательские разработки. Nova Science Pub Inc. ISBN 978-1-61122-788-8.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Multiset&oldid=1268226782#Counting_multisets"