Сочетания - История изменений

СВ: /* Алгоритм перебора сочетаний */

2026-10-24T13:22:20Z

Алгоритм перебора сочетаний

← Предыдущая		Версия 13:22, 24 октября 2026
Строка 75:		Строка 75:
	Увеличим <math>x_i</math> на единицу, а для всех <math>x_t, t=\overline{i+1,k}</math>, присваиваем значения <math>x_t = x_i+(t-i)</math>.		Увеличим <math>x_i</math> на единицу, а для всех <math>x_t, t=\overline{i+1,k}</math>, присваиваем значения <math>x_t = x_i+(t-i)</math>.
	Повторяем процесс нужное число раз.		Повторяем процесс нужное число раз.

			[[Файл:p17-01-combination-step.svg\|frame\|none\|800px\|alt=Два шага перебора: (1,2,3)→(1,2,4) и (1,4,5)→(2,3,4) с подсветкой изменённых позиций\|Рис. 1. Если последний элемент можно увеличить, он увеличивается: <math>(1,2,3)\to(1,2,4)</math>. Если хвост уже максимален, находится ближайшая слева позиция, которую можно увеличить, а хвост переназначается: <math>(1,4,5)\to(2,3,4)</math>.]]


	=== Пример ===		=== Пример ===

СВ: /* Связь сочетаний и (0,1)-векторов */

2026-10-24T13:20:36Z

Связь сочетаний и (0,1)-векторов

← Предыдущая		Версия 13:20, 24 октября 2026
Строка 106:		Строка 106:
	Тогда произвольному пути в $n$ шагов из точки $(0,0)$ в точку $(n-k,k)$ взаимно-однозначно соответствует (0,1)-вектор длины $n$ с $k$ единицами.		Тогда произвольному пути в $n$ шагов из точки $(0,0)$ в точку $(n-k,k)$ взаимно-однозначно соответствует (0,1)-вектор длины $n$ с $k$ единицами.
	Таким образом, мы получили взаимно-однозначное соответствие между множеством сочетаний из $n$ по $k$ и множеством путей на прямоугольной решетке.		Таким образом, мы получили взаимно-однозначное соответствие между множеством сочетаний из $n$ по $k$ и множеством путей на прямоугольной решетке.

			[[Файл:p16-01-combination-vector-path.svg\|frame\|none\|900px\|alt=Сочетание {1,3,4}, вектор 1 0 1 1 0 и путь из (0,0) в (2,3) на сетке\|Рис. 1. Сочетанию <math>\{1,3,4\}</math> соответствует вектор <math>(1,0,1,1,0)</math>, а ему — путь из <math>(0,0)</math> в <math>(2,3)</math>: единица — шаг вниз, ноль — шаг вправо. Все три множества равномощны.]]

	Заметим, что все множество путей из точки $(0,0)$ в точку $(n-k,k)$		Заметим, что все множество путей из точки $(0,0)$ в точку $(n-k,k)$

СВ: /* Свойства числа сочетаний */

2026-10-23T22:28:27Z

Свойства числа сочетаний

← Предыдущая		Версия 22:28, 23 октября 2026
Строка 61:		Строка 61:

	[[Файл:p14-04-triple-partition.svg\|frame\|none\|900px\|alt=Множество из пяти элементов разбито на части размерами 1, 2 и 2; две цепочки выбора дают по 30 разбиений\|Рис. 4. Разбиение на три части размерами <math>l</math>, <math>k-l</math> и <math>n-k</math>. Слева сначала выбирают <math>k</math>, затем <math>l</math>; справа сначала <math>l</math>, затем <math>k-l</math> из оставшихся — получаются одни и те же разбиения. Для <math>n=5</math>, <math>k=3</math>, <math>l=1</math>: <math>10\cdot 3 = 5\cdot 6 = 30</math>.]]		[[Файл:p14-04-triple-partition.svg\|frame\|none\|900px\|alt=Множество из пяти элементов разбито на части размерами 1, 2 и 2; две цепочки выбора дают по 30 разбиений\|Рис. 4. Разбиение на три части размерами <math>l</math>, <math>k-l</math> и <math>n-k</math>. Слева сначала выбирают <math>k</math>, затем <math>l</math>; справа сначала <math>l</math>, затем <math>k-l</math> из оставшихся — получаются одни и те же разбиения. Для <math>n=5</math>, <math>k=3</math>, <math>l=1</math>: <math>10\cdot 3 = 5\cdot 6 = 30</math>.]]


	== Алгоритм перебора сочетаний ==		== Алгоритм перебора сочетаний ==

СВ в 22:27, 23 октября 2026

2026-10-23T22:27:26Z

← Предыдущая		Версия 22:27, 23 октября 2026
Строка 25:		Строка 25:
	Тогда <math>\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>.		Тогда <math>\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>.
	}}		}}

			[[Файл:p14-02-combinations-collapse.svg\|frame\|none\|900px\|alt=Три сочетания из трёх элементов по два и шесть соответствующих им размещений: каждому сочетанию отвечают два порядка\|Рис. 2. Каждому сочетанию соответствуют <math>k! = 2! = 2</math> размещения — все порядки его элементов. Поэтому <math>C_3^2 = A_3^2/2! = 6/2 = 3</math>.]]

			Очевидным следствием из формулы является равенство
			<math>
			\binom{n}{k} = \binom{n}{n-k}.
			</math>

			Интуитивно эту формулу можно было бы обосновать следующим рассуждением.
			Выбирая $k$ элементов из $n$, мы тем самым выбираем $n-k$ элементов из $n$, которые не попадают в нашу выборку. Проще говоря, мы разбиваем наше множество
			мощности $n$ на два подмножества мощностей $k$ и $n-k$ соответственно.

			[[Файл:p14-03-complement-symmetry.svg\|frame\|none\|800px\|alt=Пять элементов разделены на три выбранных и два оставшихся; выбор трёх равносилен указанию двух оставшихся, поэтому оба числа способов равны 10\|Рис. 3. Выбрать <math>k</math> элементов из <math>n</math> — то же, что указать <math>n-k</math> элементов, которые останутся. Для <math>S=\{1,\dots,5\}</math> и <math>k=3</math>: <math>C_5^3 = C_5^2 = 10</math>.]]


	== Свойства числа сочетаний ==		== Свойства числа сочетаний ==
Строка 45:		Строка 59:
	Правая часть равенства соответствует выбору сначала <math>l</math> элементов из <math>n</math>,		Правая часть равенства соответствует выбору сначала <math>l</math> элементов из <math>n</math>,
	а затем <math>k-l</math> элементов из оставшихся <math>n-l</math>. Получим те же варианты подмножеств.		а затем <math>k-l</math> элементов из оставшихся <math>n-l</math>. Получим те же варианты подмножеств.

			[[Файл:p14-04-triple-partition.svg\|frame\|none\|900px\|alt=Множество из пяти элементов разбито на части размерами 1, 2 и 2; две цепочки выбора дают по 30 разбиений\|Рис. 4. Разбиение на три части размерами <math>l</math>, <math>k-l</math> и <math>n-k</math>. Слева сначала выбирают <math>k</math>, затем <math>l</math>; справа сначала <math>l</math>, затем <math>k-l</math> из оставшихся — получаются одни и те же разбиения. Для <math>n=5</math>, <math>k=3</math>, <math>l=1</math>: <math>10\cdot 3 = 5\cdot 6 = 30</math>.]]


	== Алгоритм перебора сочетаний ==		== Алгоритм перебора сочетаний ==

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

2026-10-09T19:25:15Z

← Предыдущая		Версия 19:25, 9 октября 2026
Строка 1:		Строка 1:
			== Определение ==
	{{Определение		{{Определение
	\|id=def1		\|id=def1

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

2026-10-09T19:24:48Z

← Предыдущая		Версия 19:24, 9 октября 2026
Строка 76:		Строка 76:
	Таким образом, мы перебрали все сочетания из 5 по 3.		Таким образом, мы перебрали все сочетания из 5 по 3.
	}}		}}

			== Связь сочетаний и (0,1)-векторов ==

			С каждым сочетанием из $n$ по $k$ можно связать вектор из нулей и единиц,
			в котором число единиц равно $k$: позиции единиц указывают числа, которые должны
			войти в сочетание. Другими словами, установлено взаимооднозначное соответствие
			между множеством сочетаний из $n$ по $k$ и множеством (0,1)-векторов длины $n$ с $k$ единицами.

			В свою очередь, каждый (0,1)-вектор длины $n$ с $k$ единицами соответствует пути на прямоугольной решетке длины $n-k$ и высоты $k$.

			Можно сопоставить каждому шагу вниз единицу, а каждому шагу вправо {{---}} ноль.
			Тогда произвольному пути в $n$ шагов из точки $(0,0)$ в точку $(n-k,k)$ взаимно-однозначно соответствует (0,1)-вектор длины $n$ с $k$ единицами.
			Таким образом, мы получили взаимно-однозначное соответствие между множеством сочетаний из $n$ по $k$ и множеством путей на прямоугольной решетке.

			Заметим, что все множество путей из точки $(0,0)$ в точку $(n-k,k)$
			складывается из множества путей из $(0,0)$ в $(n-k,k-1)$ с последним шагом из $(n-k,k-1)$ в $(n-k,k)$ и
			множества путей из $(0,0)$ в $(n-k-1,k)$ с последним шагом из $(n-k-1,k)$ в $(n-k,k)$.

			Тогда количество путей из $(0,0)$ в $(n-k,k)$, равное $\binom{n}{k}$, совпадает с суммой количеств путей из $(0,0)$ в $(n-k,k-1)$ и из $(0,0)$ в $(n-k-1,k)$, что
			равно $\binom{n-1}{k-1}+\binom{n-1}{k}$. Таким образом, мы привели еще одно доказательство рекурентной формулы для вычисления $C_n^k$.



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

	[[Категория:Комбинаторика]]		[[Категория:Комбинаторика]]

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

2026-10-09T19:15:00Z

← Предыдущая		Версия 19:15, 9 октября 2026
Строка 77:		Строка 77:
	}}		}}

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


	[[Категория:Комбинаторика]]		[[Категория:Комбинаторика]]

СВ в 13:26, 4 ноября 2021

2021-11-04T13:26:06Z

← Предыдущая		Версия 13:26, 4 ноября 2021
Строка 10:		Строка 10:
	{{Пример		{{Пример
	\|num=1		\|num=1
	\|~~definition~~=Предположим, из <math>n</math> участников спортивного клуба на соревнования должны поехать какие-то <math>k</math>.		\|content=Предположим, из <math>n</math> участников спортивного клуба на соревнования должны поехать какие-то <math>k</math>.
	Тогда имеется <math>C_n^k</math> различных возможности собрать команду.		Тогда имеется <math>C_n^k</math> различных возможности собрать команду.
	}}		}}
	{{Пример		{{Пример
	\|num=2		\|num=2
	\|~~definition~~= Пусть <math>S = \{1,2,3\}</math>. Тогда <math>\{1,2\}</math>, <math>\{1,3\}</math>, <math>\{2,3\}</math> {{---}} все возможные cочетания из трех элементов по два.		\|content= Пусть <math>S = \{1,2,3\}</math>. Тогда <math>\{1,2\}</math>, <math>\{1,3\}</math>, <math>\{2,3\}</math> {{---}} все возможные cочетания из трех элементов по два.
	}}		}}
	{{Утверждение		{{Утверждение
Строка 62:		Строка 62:
	{{Пример		{{Пример
	\|num=1		\|num=1
	\|~~definition~~=Рассмотрим, как работает алгоритм для <math>n=5</math> и <math>k=3</math>.		\|content=Рассмотрим, как работает алгоритм для <math>n=5</math> и <math>k=3</math>.
	# Сначала <math>x = (x_1, x_2, x_3) = (1,2,3)</math>.		# Сначала <math>x = (x_1, x_2, x_3) = (1,2,3)</math>.
	# Увеличиваем <math>x_3</math>: <math>x = (1,2,4)</math>.		# Увеличиваем <math>x_3</math>: <math>x = (1,2,4)</math>.

СВ в 15:03, 31 октября 2021

2021-10-31T15:03:18Z

← Предыдущая		Версия 15:03, 31 октября 2021
Строка 44:		Строка 44:
	Правая часть равенства соответствует выбору сначала <math>l</math> элементов из <math>n</math>,		Правая часть равенства соответствует выбору сначала <math>l</math> элементов из <math>n</math>,
	а затем <math>k-l</math> элементов из оставшихся <math>n-l</math>. Получим те же варианты подмножеств.		а затем <math>k-l</math> элементов из оставшихся <math>n-l</math>. Получим те же варианты подмножеств.

			== Алгоритм перебора сочетаний ==

			Пусть <math>x_1, x_2, ..., x_k</math> {{---}} числа из множества <math>\{1,2,...,n\}</math>, вошедшие в сочетание, причем <math>x_1 \lt x_2 \lt ... \lt x_k</math>.

			Пусть в начальный момент времени сочетание состоит из первых <math>k</math> чисел: <math>x_i = i, i=\overline{1,k}</math>.

			На каждом шаге будем просматривать вектор <math>(x_1, x_2, ..., x_k)</math>, начиная с <math>x_k</math>, и искать первую такую компоненту <math>x_i</math>,
			которую можно увеличить (нельзя увеличить <math>x_k</math>, если он равен <math>n</math>; <math>x_{k-1}</math>, если он равен <math>n-1</math> и так далее).

			Если такой компоненты не найдется, алгоритм завершает свою работу.
			В противном случае, пусть <math>i</math> {{---}} такое наибольшее число, что <math>x_i \lt n-k+i</math>.
			Увеличим <math>x_i</math> на единицу, а для всех <math>x_t, t=\overline{i+1,k}</math>, присваиваем значения <math>x_t = x_i+(t-i)</math>.
			Повторяем процесс нужное число раз.

			=== Пример ===
			{{Пример
			\|num=1
			\|definition=Рассмотрим, как работает алгоритм для <math>n=5</math> и <math>k=3</math>.
			# Сначала <math>x = (x_1, x_2, x_3) = (1,2,3)</math>.
			# Увеличиваем <math>x_3</math>: <math>x = (1,2,4)</math>.
			# Увеличиваем <math>x_3</math>: <math>x = (1,2,5)</math>.
			# <math>x_3</math> больше увеличить нельзя. Увеличиваем <math>x_2</math> и переназначаем значение <math>x_3</math>: <math>x = (1,3,4)</math>.
			# <math>x = (1,3,5)</math>
			# <math>x = (1,4,5)</math>
			# <math>x = (2,3,4)</math>
			# <math>x = (2,3,5)</math>
			# <math>x = (2,4,5)</math>
			# <math>x = (3,4,5)</math>

			Таким образом, мы перебрали все сочетания из 5 по 3.
			}}




	[[Категория:Комбинаторика]]		[[Категория:Комбинаторика]]

СВ в 14:47, 31 октября 2021

2021-10-31T14:47:46Z

← Предыдущая		Версия 14:47, 31 октября 2021
Строка 24:		Строка 24:
	Тогда <math>\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>.		Тогда <math>\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>.
	}}		}}

			== Свойства числа сочетаний ==

			<math>
			\binom{n}{k}\cdot\binom{k}{l} = \binom{n}{l}\cdot \binom{n-l}{k-l}.
			</math>

			Действительно,
			<math>
			\binom{n}{k}\cdot\binom{k}{l}= \frac{n!}{k!(n-k)!}\cdot\frac{k!}{l!(k-l)!} \cdot \frac{(n-l)!}{(n-l)!}=
			\frac{n!}{l!(n-l)!}\cdot\frac{(n-l)!}{(k-l)!(n-k)!} = \binom{n}{l}\cdot \binom{n-l}{k-l}.
			</math>

			Интуитивно формулу можно описать как разбиение множества
			из <math>n</math> элементов на три подмножества мощностей <math>l</math>, <math>k-l</math>, <math>n-k</math> соответственно.
			Левая часть равенства описывает выбор сначала <math>k</math> элементов из <math>n</math>, а затем <math>l</math> элементов из выбранных <math>k</math>.
			Получим все варианты разбиения исходного множества на три подмножества указанных мощностей.

			Правая часть равенства соответствует выбору сначала <math>l</math> элементов из <math>n</math>,
			а затем <math>k-l</math> элементов из оставшихся <math>n-l</math>. Получим те же варианты подмножеств.



	[[Категория:Комбинаторика]]		[[Категория:Комбинаторика]]