Комбинаторные объекты - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:27:04Z

rollbackEdits.php mass rollback

91.212.153.123 в 04:53, 1 сентября 2022

2022-09-01T04:53:35Z

192.145.16.192: Согласно правилам русского языка, правильно будет "векторы", а не "вектора"

2021-11-11T19:34:07Z

Согласно правилам русского языка, правильно будет "векторы", а не "вектора"

176.59.214.67: added proofs

2021-01-08T10:44:27Z

added proofs

Dantesto в 12:36, 5 января 2017

2017-01-05T12:36:35Z

Dantesto: Примеры

2017-01-05T12:18:51Z

Примеры

Dantesto: Английские термины, ссылки

2017-01-04T15:48:54Z

Английские термины, ссылки

Dantesto: Удаление вывода формул, добавление таблицы

2016-12-31T13:09:05Z

Удаление вывода формул, добавление таблицы

Внесённые изменения

Dantesto в 21:11, 12 декабря 2016

2016-12-12T21:11:45Z

Dantesto в 20:06, 12 декабря 2016

2016-12-12T20:06:27Z

@@ Строка 1: / Строка 1: @@
 {{Определение
@@ Строка 79: / Строка 57: @@
 === Разбиение на подмножества ===
 {{Определение
-|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
+|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
 # <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
 # <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.

@@ Строка 1: / Строка 1: @@
 {{Определение
@@ Строка 57: / Строка 79: @@
 === Разбиение на подмножества ===
 {{Определение
-|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
+|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
 # <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
 # <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.

@@ Строка 8: / Строка 8: @@
 == Примеры комбинаторных объектов ==
-=== Битовые вектора ===
+=== Битовые векторы ===
 {{Определение
-|definition='''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины.
+|definition='''[[Получение объекта по номеру#Битовые векторы | Битовые векторы]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины.
 }}
@@ Строка 67: / Строка 67: @@
 |'''Тип объекта'''||'''Число объектов'''
 |-
-|Битовые вектора||<tex>2^{n}</tex>
+|Битовые векторы||<tex>2^{n}</tex>
 |-
 |Перестановки||<tex>P_n = n!</tex>

@@ Строка 85: / Строка 85: @@
 |Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
 |}
 == См. также ==

← Предыдущая		Версия 12:36, 5 января 2017
Строка 100:		Строка 100:
	[[Категория: Дискретная математика и алгоритмы]]		[[Категория: Дискретная математика и алгоритмы]]
	[[Категория: Комбинаторика ]]		[[Категория: Комбинаторика ]]
		+	[[Категория: Комбинаторные объекты ]]

@@ Строка 9: / Строка 9: @@
 == Примеры комбинаторных объектов ==
 === Битовые вектора ===
-'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины.
+{{Определение
 === Перестановки ===
-'''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' (англ. ''permutations'') &mdash; упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.
+{{Определение
 === Перестановки с повторениями ===
-'''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — те же перестановки, однако некоторые элементы могут встречаться несколько раз.
+{{Определение
 === Размещения ===
-'''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> (англ. ''arrangement'') из <tex>n</tex> по <tex>k</tex> &mdash; упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
+{{Определение
 === Размещения с повторениями ===
-'''Размещение с повторениями''' (англ. ''arrangement with repetitions''), составленное из данных <tex>n</tex> элементов по <tex>k</tex> — отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, \ldots, k</tex> в данное множество <tex>\{a_1, a_2, \ldots, a_n\}</tex>.
+{{Определение
 === Сочетания ===
-'''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' (англ. ''combinations'') из <tex>n</tex> по <tex>k</tex> &mdash; набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.
+{{Определение
 === Сочетания с повторениями ===
-'''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
+{{Определение
 === Разбиение на неупорядоченные слагаемые ===
-[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') &mdash; представление числа <tex>n</tex> в виде суммы слагаемых.
+{{Определение
 {{main|Нахождение количества разбиений числа на слагаемые}}
 === Разбиение на подмножества ===
-[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
+{{Определение
 # <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
 # <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
 {{main|Числа Стирлинга второго рода}}

@@ Строка 27: / Строка 27: @@
 === Сочетания с повторениями ===
-'''Сочетания с повторениями''' — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество. Способов таких выборов всего <tex dpi = "150">\tilde{\sf_C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>.
+'''Сочетания с повторениями''' — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом. Способов таких выборов всего <tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>. Чтобы вывести формулу, давайте различные элементы в перестановке разделим перегородками, а каждый элемент назовем <tex>1</tex>, тогда, чтобы получить новую перестановку просто будем менять местами перегородки и <tex>1</tex>, причем таких перегородок будет <tex>n - 1</tex>, даже если мы не брали некоторые типы элементов. Таких перестановок <tex>(n - 1 + k)!</tex>, а за вычетом перестановок одинаковых элементов (перегородок и <tex>1</tex>), коих в <tex>k!(n - 1)!</tex> раз больше необходимых, получаем необходимую формулу.
 === Разбиение на неупорядоченные слагаемые ===
@@ Строка 65: / Строка 65: @@
 Подробнее можно прочитать на странице о [[Числа Стирлинга второго рода | числах Стирлинга второго порядка]].
 == Примечания ==

@@ Строка 13: / Строка 13: @@
 === Перестановки ===
 '''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' &mdash; это упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора. Количество перестановок равно <tex>P_n = n!</tex>. Получить эту формулу можно следующим образом: поставим один из <tex>n</tex> элементов на первое место, далее поставим на второе один из <tex>n - 1</tex> оставшихся элементов,... один из <tex>1</tex> элемента на последнее. Всего таких выборов можно совершить <tex>n \times (n - 1) \times ... \times 1 = n!</tex>.
 === Размещения ===
-'''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> из <tex>n</tex> по <tex>k</tex> &mdash; это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества. Таких наборов <tex>A^{k}_n = \frac{n!}{(n - k)!}</tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>n</tex> элементов, на следующее один из <tex>n - 1</tex>,... и на последнее один из <tex>n - k + 1</tex>. Всего получится <tex>n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(n - k)!}</tex>.
+'''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> из <tex>n</tex> по <tex>k</tex> &mdash; это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества. Таких наборов <tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>n</tex> элементов, на следующее один из <tex>n - 1</tex>,... и на последнее один из <tex>n - k + 1</tex>. Всего получится <tex dpi = "150">n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(n - k)!}</tex>.
 === Сочетания ===
-'''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' из <tex>n</tex> по <tex>k</tex> &mdash; это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы <tex>\{1, 2\}</tex> и <tex>\{2, 1\}</tex> эквивалентны. То есть в размещениях любой вариант сочетания повторяется столько же раз, сколько можно сделать перестановок для <tex>k</tex> мест. Тогда <tex dpi = "150">C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}</tex>.
+'''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' из <tex>n</tex> по <tex>k</tex> &mdash; это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы <tex>\{1, 2\}</tex> и <tex>\{2, 1\}</tex> эквивалентны. То есть в размещениях любой вариант сочетания повторяется столько же раз, сколько можно сделать перестановок для <tex>k</tex> мест. Тогда <tex dpi = "150">C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}</tex>.
 === Разбиение на неупорядоченные слагаемые ===
@@ Строка 32: / Строка 41: @@
 === Разбиение на подмножества ===
-[[Числа Стирлинга первого рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
+[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
 # <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>;
 # <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.