Мультимножества - История изменений

СВ в 13:25, 24 октября 2026

2026-10-24T13:25:59Z

← Предыдущая		Версия 13:25, 24 октября 2026
Строка 72:		Строка 72:
	Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$		Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$
	над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.		над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.

			[[Файл:p19-01-multiset-subset-bijection.svg\|frame\|none\|800px\|alt=Мультимножество {1¹,2⁰,3²}, последовательность 1,3,3 и подмножество {1,4,5} после сдвига\|Рис. 1. Мультимножество <math>\{1^1,2^0,3^2\}</math> даёт неубывающую последовательность <math>b=(1,3,3)</math>. Сдвиг <math>a_i=b_i+i-1</math> превращает её в строго возрастающую <math>(1,4,5)</math> — подмножество из <math>\{1,\ldots,5\}</math>; таких подмножеств <math>C(5,3)=10</math>.]]

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

			[[Файл:p20-01-stars-and-bars.svg\|frame\|none\|800px\|alt=Вектор 0,0,1,0,1,0 с группами нулей для количеств 2,1,1 и та же запись звёздами и перегородками\|Рис. 1. Мультимножество с количествами <math>2, 1, 1</math> кодируется вектором <math>0,0,1,0,1,0</math>: нули — вхождения, единицы — перегородки. Нулей <math>k=4</math>, единиц <math>n-1=2</math>, длина <math>n+k-1=6</math>.]]

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

СВ в 19:38, 9 октября 2026

2026-10-09T19:38:01Z

← Предыдущая		Версия 19:38, 9 октября 2026
Строка 72:		Строка 72:
	Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$		Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$
	над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.		над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.

			== Связь мультимножеств и (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)$.

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

СВ в 19:37, 9 октября 2026

2026-10-09T19:37:22Z

← Предыдущая		Версия 19:37, 9 октября 2026
Строка 72:		Строка 72:
	Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$		Таким образом, установлено взаимно-однозначное соответствие между множеством сочетаний из $n+k-1$ по $k$ и множеством мультимножеств мощности $k$
	над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.		над множеством из $n$ элементов. Следовательно, мощности этих множеств равны.

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

СВ: Новая страница: «Пусть дано некоторое множество $S = \{s_1, s_2, ..., s_n\}$, $|S| = n$. {{Определение |definition=Мультимножес...»

2026-10-09T19:37:02Z

Новая страница: «Пусть дано некоторое множество $S = \{s_1, s_2, ..., s_n\}$, $|S| = n$. {{Определение |definition=Мультимножес...»

Новая страница

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

{{Определение
|definition=Мультимножеством $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>
\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$ {{---}} это неупорядоченная выборка с повторениями (сочетание с повторениями).
{{Определение
|definition=
Множество всех мультимножеств на множестве $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>
\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$ элементов. Следовательно, мощности этих множеств равны.