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

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

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

Формальное определение

Мультимножество на множестве $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}$

Литература

• Петровский А.Б. Пространства множеств и мультимножеств. – М.: Едиториал УРСС, 2003. – 248 с.