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

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

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

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

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

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

${\displaystyle {n+k-1 \choose k}}$ .

Примечания

Литература

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