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

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

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

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

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

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

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

\text{[math]}

{n+k-1 \choose k}

{n+k-1 \choose k}

.

ПримечанияПравить

↑ Дональд Кнут. Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: Вильямс, 2007. — С. 832. — ISBN 0-201-89684-2.
↑ Джеймс Питерсон. Обзор теории комплектов // Теория сетей Петри и моделирование систем = Petri Net Theory and The Modelling of Systems. — М.: Мир, 1984. — С. 231—235. — 264 с. — 8400 экз.

ЛитератураПравить

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

[1] Дональд Кнут. Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: Вильямс, 2007. — С. 832. — ISBN 0-201-89684-2.

[2] Джеймс Питерсон. Обзор теории комплектов // Теория сетей Петри и моделирование систем = Petri Net Theory and The Modelling of Systems. — М.: Мир, 1984. — С. 231—235. — 264 с. — 8400 экз.

[1]

[2]