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

СВ в 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>. Получим те же варианты подмножеств.



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

СВ: Новая страница: «{{Определение |id=def1 |definition= ''Сочетанием'' из $n$ элементов по $k$ называется неупо...»

2021-10-30T22:31:39Z

Новая страница: «{{Определение |id=def1 |definition= ''Сочетанием'' из <math>n</math> элементов по <math>k</math> называется неупо...»

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

{{Определение
|id=def1
|definition=
''Сочетанием'' из <math>n</math> элементов по <math>k</math> называется неупорядоченная выборка без повторений объема <math>k</math> из <math>n</math>-элементного множества.
}}
Не умаляя общности, можно называть сочетанием из <math>n</math> элементов по <math>k</math> неупорядоченный набор из <math>k</math> различных чисел,
принадлежащих множеству <math>\{1, ..., n\}</math>.

Количество различных сочетаний из <math>n</math> по <math>k</math> обозначают <math>C_n^k</math> или <math>\binom{n}{k}</math>.
{{Пример
|num=1
|definition=Предположим, из <math>n</math> участников спортивного клуба на соревнования должны поехать какие-то <math>k</math>.
Тогда имеется <math>C_n^k</math> различных возможности собрать команду.
}}
{{Пример
|num=2
|definition= Пусть <math>S = \{1,2,3\}</math>. Тогда <math>\{1,2\}</math>, <math>\{1,3\}</math>, <math>\{2,3\}</math> {{---}} все возможные cочетания из трех элементов по два.
}}
{{Утверждение
|statement=Пусть <math>k,n\in\mathbb{N}</math> и <math>1 \leq k \leq n</math>.
Тогда <math>\binom{n}{k} = \frac{n!}{k!(n-k)!}</math>.
|proof=
Действительно, каждому сочетанию из <math>n</math> по <math>k</math> соответствует <math>k!</math> различных размещений из <math>n</math> по <math>k</math> с различным порядком следования элементов.
Тогда <math>\binom{n}{k} = \frac{A_n^k}{k!} = \frac{n!}{k!(n-k)!}</math>.
}}

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

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

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

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

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

СВ: Новая страница: «{{Определение |id=def1 |definition= ''Сочетанием'' из n элементов по k называется неупо...»

СВ: Новая страница: «{{Определение |id=def1 |definition= ''Сочетанием'' из $n$ элементов по $k$ называется неупо...»