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

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

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

Формально, мультимножество на множестве

A

{\displaystyle A}

определяется как упорядоченная пара

(

A

,

m

)

{\displaystyle (A,m)}

, где

m

:

A

→

N

{\displaystyle m\colon A\to \mathbb {N} }

— это функция, сопоставляющая каждому элементу множества

A

{\displaystyle A}

некоторое натуральное число, называемое кратностью этого элемента.

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

120

=

2

3

3

1

5

1

{\displaystyle 120=2^{3}3^{1}5^{1}}

, поэтому его мультимножество простых делителей —

{

2

,

2

,

2

,

3

,

5

}

{\displaystyle \{2,2,2,3,5\}}

.

Другой пример — мультимножество корней алгебраического уравнения. Например, уравнение

x

3

−

5

x

2

+

8

x

−

4

=

0

{\displaystyle x^{3}-5x^{2}+8x-4=0}

имеет корни

{

1

,

2

,

2

}

{\displaystyle \{1,2,2\}}

.

Число различных мультимножеств мощности

k

{\displaystyle k}

, состоящих из элементов, выбранных из множества мощности

n

{\displaystyle n}

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

(

n

+

k

−

1

k

)

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

.

Источник: Википедия