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

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

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

Формально, мультимножество на множестве $A$ определяется как упорядоченная пара $(A,m)$, где $m: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$, может быть вычислено по следующей формуле, как биномиальный коэффициент:

$(\genfrac{}{}{0ex}{}{n+k-1}{k})$.

Литература

• Шаблон:Книга