Мультимножество

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

Идея мультимножества неявно используется со времён древности (Кнут приводит в пример Бхаскару II из XII века, изучавшего перестановки мультимножеств), но введение понятия и фиксацию термина относят к де Брёйну (1970-е годы). Используется в основном в приложениях (информатике, искусственном интеллекте, теории принятия решений), в применении к теории сетей Петри мультимножество называется комплектом. В различных приложениях используют значительно различающуюся разную нотацию.

Определение

Мультимножество на множестве <math>A</math> — это упорядоченная пара <math>(A, m)</math>, где <math>m \colon A \to \mathbb{N}</math> — это функция, сопоставляющая каждому элементу множества <math>A</math> некоторое натуральное число, называемое кратностью этого элемента.

Примеры

Один из самых простых примеров — мультимножество простых множителей целого числа. Так, например, разложение числа 120 на простые множители имеет вид:

<math>120 = 2^3 3^1 5^1\,,</math>

поэтому его мультимножество простых делителей — <math>\{2, 2, 2, 3, 5\}</math>.

Другой пример — мультимножество корней алгебраического уравнения. Например, уравнение <math>x^3 - 5x^2 + 8x - 4 = 0</math> имеет корни <math>\{1, 2, 2\}</math>.

Число мультимножеств

Число различных мультимножеств мощности <math>k</math>, состоящих из элементов, выбранных из множества мощности <math>n</math>, может быть вычислено по следующей формуле, как биномиальный коэффициент:

<math>{n+k-1 \choose k}</math>

Литература

• А. Б. Петровский. [www.raai.org/about/persons/petrovsky/pages/Petrovsky_2003.pdf Пространства множеств и мультимножеств]. — М.: Едиториал УРСС, 2003. — С. 248. — ISBN 5-7262-0633-9.

Отрывок, характеризующий Мультимножество

Когда человек видит умирающее животное, ужас охватывает его: то, что есть он сам, – сущность его, в его глазах очевидно уничтожается – перестает быть. Но когда умирающее есть человек, и человек любимый – ощущаемый, тогда, кроме ужаса перед уничтожением жизни, чувствуется разрыв и духовная рана, которая, так же как и рана физическая, иногда убивает, иногда залечивается, но всегда болит и боится внешнего раздражающего прикосновения.
После смерти князя Андрея Наташа и княжна Марья одинаково чувствовали это. Они, нравственно согнувшись и зажмурившись от грозного, нависшего над ними облака смерти, не смели взглянуть в лицо жизни. Они осторожно берегли свои открытые раны от оскорбительных, болезненных прикосновений. Все: быстро проехавший экипаж по улице, напоминание об обеде, вопрос девушки о платье, которое надо приготовить; еще хуже, слово неискреннего, слабого участия болезненно раздражало рану, казалось оскорблением и нарушало ту необходимую тишину, в которой они обе старались прислушиваться к незамолкшему еще в их воображении страшному, строгому хору, и мешало вглядываться в те таинственные бесконечные дали, которые на мгновение открылись перед ними.
Только вдвоем им было не оскорбительно и не больно. Они мало говорили между собой. Ежели они говорили, то о самых незначительных предметах. И та и другая одинаково избегали упоминания о чем нибудь, имеющем отношение к будущему.
Признавать возможность будущего казалось им оскорблением его памяти. Еще осторожнее они обходили в своих разговорах все то, что могло иметь отношение к умершему. Им казалось, что то, что они пережили и перечувствовали, не могло быть выражено словами. Им казалось, что всякое упоминание словами о подробностях его жизни нарушало величие и святыню совершившегося в их глазах таинства.
Беспрестанные воздержания речи, постоянное старательное обхождение всего того, что могло навести на слово о нем: эти остановки с разных сторон на границе того, чего нельзя было говорить, еще чище и яснее выставляли перед их воображением то, что они чувствовали.

Но чистая, полная печаль так же невозможна, как чистая и полная радость. Княжна Марья, по своему положению одной независимой хозяйки своей судьбы, опекунши и воспитательницы племянника, первая была вызвана жизнью из того мира печали, в котором она жила первые две недели. Она получила письма от родных, на которые надо было отвечать; комната, в которую поместили Николеньку, была сыра, и он стал кашлять. Алпатыч приехал в Ярославль с отчетами о делах и с предложениями и советами переехать в Москву в Вздвиженский дом, который остался цел и требовал только небольших починок. Жизнь не останавливалась, и надо было жить. Как ни тяжело было княжне Марье выйти из того мира уединенного созерцания, в котором она жила до сих пор, как ни жалко и как будто совестно было покинуть Наташу одну, – заботы жизни требовали ее участия, и она невольно отдалась им. Она поверяла счеты с Алпатычем, советовалась с Десалем о племяннике и делала распоряжения и приготовления для своего переезда в Москву.