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

Пусть дано некоторое множество $S = \{s_1, s_2, ..., s_n\}$, $|S| = n$.

Определение:

Мультимножеством $M$ на множестве $S$ назовем всюду определенную функцию $\varphi: S\rightarrow \mathbb{N}_0,$ где $\mathbb{N}_0$ — множество неотрицательных целых чисел.

Будем писать $M = \{s_1^{\varphi(s_1)}, s_2^{\varphi(s_2)}, ..., s_n^{\varphi(s_n)}\}$, имея в виду, что элемент $s_i$ множества $S$ встречается в мультимножестве $M$ ровно $\varphi(s_i)$ раз.

Мощность мультимножества $M$ положим равной сумме количеств вхождений в $M$ элементов $s_i$: $|M| = \sum_{i=1}^n \varphi(s_i)$.

Пусть $S = \{1,2,3,4,5\}$ и задана функция $\varphi$:

[math]\displaystyle{ \begin{array}{c|ccccc} x & 1 & 2 & 3 & 4 & 5\\ \hline \varphi(x) & 1 & 0 & 2 & 1 & 3 \end{array}. }[/math]

Тогда мультимножество имеет вид $M = \{1^1, 2^0, 3^2, 4^1, 5^3\}$. То есть элементы 1 и 4 входят в мультимножество $M$ по одному разу, элемент 3 входит в него 2 раза, элемент 5 — три раза и элемент 2 множества $S$ не входит в мультимножество $M$.

Мощность мультимножества равна $|M| = 1+0+2+1+3 = 7$.

Как можно видеть, мультимножество над множеством $S$ — это неупорядоченная выборка с повторениями (сочетание с повторениями).

Определение:

Множество всех мультимножеств на множестве $S$ мощности $k$ будем обозначать $\bigl(\binom{S}{k}\bigr)$.

Пусть $S = \{1,2,3\}$. Тогда множество всех мультимножеств мощности 2 над множеством $S$ будет иметь вид:
$\bigl(\binom{S}{2}\bigr) =$ $\{\{1^2, 2^0, 3^0\},$
$\{1^1, 2^1, 3^0\},$
$\{1^1, 2^0, 3^1\},$
$\{1^0, 2^2, 3^0\},$
$\{1^0, 2^1, 3^1\},$
$\{1^0, 2^0, 3^2\}\}.$

Посчитаем, сколько возможно различных выборок с повторениями мощности $k$ над множеством из $n$ элементов. Положим $\left(\binom{n}{k}\right) = \left|\left(\binom{S}{k}\right)\right|$.

Пусть $k, n\in\mathbb{N}$. [math]\displaystyle{ \left(\binom{n}{k}\right) = \binom{n+k-1}{k} }[/math]

Справа в формуле стоит мощность множества всех подмножеств мощности $k$ множества мощности $n+k-1$. Рассмотрим множество $\{1,2,...,n+k-1\}$ и его произвольное $k$-подмножество $\{a_1, a_2, ..., a_k\}$. Не умаляя общности можно считать, что элементы $a_i$ выстроены в порядке возрастания: $1\leq a_1 < a_2 < ... < a_k\leq n+k-1$ (*).

Положим по определению $b_i = a_i-i+1$, $i=\overline{1,k}$. Тогда $b_1 = a_1\geq 1$; $b_k = a_k -k+1\leq n+k-1 -k+1 = n$; $b_{i+1}-b_i = a_{i+1} - (i+1) +1 - (a_i -i +1) = a_{i+1}-a_i -1 \geq 0, \quad i=\overline{1,k-1}$.

Следовательно, $1\leq b_1 \leq b_2 \leq ... \leq b_k \leq n$ (**), то есть $b_1$, $b_2$, ..., $b_k$ задают некоторое мультимножество мощности $k$ над множеством $\{1,2,...,n\}$.

Аналогично показывается обратное соответствие. Слева в формуле $\left(\binom{n}{k}\right) = \binom{n+k-1}{k}$ стоит число мультимножеств мощности $k$ множества мощности $n$. Рассмотрим произвольное мультимножество мощности $k$ над множеством $\{1,2,...,n\}$. Не умаляя общности, считаем, что элементы мультимножества расположены в порядке неубывания и выполнена формула (**).

Положим по определению $a_i = b_i+i-1$, $i=\overline{1,k}$. Тогда $a_1 = b_1\geq 1$; $a_k = b_k +k-1\leq n +k-1$; $a_{i+1}-a_i = b_{i+1} + (i+1) -1 - (b_i +i -1) = b_{i+1}-b_i +1 > 0, i=\overline{1,k-1}$. Следовательно, выполняется условие $(*)$.

Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$ над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.

Рис. 1. Мультимножество [math]\displaystyle{ \{1^1,2^0,3^2\} }[/math] даёт неубывающую последовательность [math]\displaystyle{ b=(1,3,3) }[/math]. Сдвиг [math]\displaystyle{ a_i=b_i+i-1 }[/math] превращает её в строго возрастающую [math]\displaystyle{ (1,4,5) }[/math] — подмножество из [math]\displaystyle{ \{1,\ldots,5\} }[/math]; таких подмножеств [math]\displaystyle{ C(5,3)=10 }[/math].

Связь мультимножеств и (0,1)-векторов

Каждому (0,1)-вектору из $n$ элементов с ровно $k$ единицами однозначно соответствует некоторое сочетание из $n$ элементов по $k$.

Каждому мультимножеству мощности $k$ на $n$-элементном множестве $S = \{s_1, s_2, ..., s_n\}$ можно поставить в соответствие такой (0,1)-вектор длины $n+k-1$ из $k$ нулей и $n-1$ единицы, что число нулей, находящихся между $i-1$-й и $i$-й единицами, будет равно числу вхождений в мультимножество элемента $s_i$, $2\leq i\leq n-1$; число нулей перед первой единицей равно числу вхождений в мультимножество элемента $s_1$; число нулей после $n-1$-й единицы равно числу вхождений в мультимножество элемента $s_n$.

Это соответствие между множеством $\bigl(\binom{S}{k}\bigr)$ и множеством (0,1)-векторов длины $n+k-1$ c $n-1$-й единицей является взаимно-однозначным.

Таким образом, каждому (0,1)-вектору длины $n+k-1$ с $n-1$-й единицей однозначно соответствует сочетание из $n+k-1$ по $n-1$ и в тоже время ему соответствует мультимножество мощности $k$ на $n$-элементном множестве. Следовательно, мы установили взаимно-однозначное соответствие между множеством всех сочетаний из $n+k-1$ по $n-1$ и множеством всех мультимножеств мощности $k$ на $n$-элементном множестве. Значит, $\binom{n+k-1}{k} =\binom{n+k-1}{n-1}= \left(\binom{n}{k}\right)$.

Рис. 1. Мультимножество с количествами [math]\displaystyle{ 2, 1, 1 }[/math] кодируется вектором [math]\displaystyle{ 0,0,1,0,1,0 }[/math]: нули — вхождения, единицы — перегородки. Нулей [math]\displaystyle{ k=4 }[/math], единиц [math]\displaystyle{ n-1=2 }[/math], длина [math]\displaystyle{ n+k-1=6 }[/math].

Конспект: Дискретная математика