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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править вики-текст]

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

Примеры[править | править вики-текст]

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

120 = 2^3 3^1 5^1\,,

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

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

Число мультимножеств[править | править вики-текст]

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

{n+k-1 \choose k}

Примечания[править | править вики-текст]

  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 экз.

Литература[править | править вики-текст]