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

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

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

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

Один из самых простых примеров — мультимножество простых множителей целого числа. Так, например, разложение числа 120 на простые множители имеет вид: [math]\displaystyle{ 120 = 2^3 3^1 5^1 }[/math], поэтому его мультимножество простых делителей — [math]\displaystyle{ \{2, 2, 2, 3, 5\} }[/math].

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

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

[math]\displaystyle{ {n+k-1 \choose k} }[/math].

Литература

• А. Б. Петровский. Пространства множеств и мультимножеств. — М.: Едиториал УРСС, 2003. — С. 248. — ISBN 5-7262-0633-9.