Обсуждение участника:Galibov Mikhail - История изменений

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-07T21:26:48Z

‎Доказательства числа комбинаторных объектов

176.59.214.217 в 21:20, 7 января 2021

2021-01-07T21:20:08Z

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-07T14:52:24Z

‎Доказательства числа комбинаторных объектов

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-07T12:53:06Z

‎Доказательства числа комбинаторных объектов

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-05T17:43:55Z

‎Доказательства числа комбинаторных объектов

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-05T17:25:35Z

‎Доказательства числа комбинаторных объектов

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-05T17:16:12Z

‎Доказательства числа комбинаторных объектов

Galibov Mikhail: /* Доказательства числа комбинаторных объектов */

2021-01-05T13:54:40Z

‎Доказательства числа комбинаторных объектов

Galibov Mikhail: /* Число комбинаторных объектов */

2021-01-05T13:41:08Z

‎Число комбинаторных объектов

Galibov Mikhail: /* Доказательства числа комбинаторных объектов. */

2021-01-05T13:39:26Z

‎Доказательства числа комбинаторных объектов.

@@ Строка 44: / Строка 44: @@
 Теорема | id=3
 |statement=
-Число различных перестановок с повторениями из <tex>k</tex> элементов с <tex>n</tex> группами одинаковых элементов равно <tex>\overline{P_k} (k_1, k_2, \ldots, k_n) = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>, где <tex>k_i</tex> - это количество одинаковых элементов в <tex>i</tex>-ой группе.
+Число различных перестановок с повторениями из <tex>k</tex> элементов с <tex>n</tex> группами одинаковых элементов равно <tex>\overline{P_k} (k_1, k_2, \ldots, k_n) = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>, где <tex>k_i</tex> {{---}} это количество одинаковых элементов в <tex>i</tex>{{---}}ой группе.
 |proof=
@@ Строка 62: / Строка 62: @@
 Доказательство по индукции. База <tex>k = 1</tex>, тогда количество размещений из <tex>n</tex> по <tex>1</tex> равно <tex>n</tex>.
-При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть <tex>(n-1)</tex> элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>A_{n}^{k}=n \cdot A_{n-1}^{k-1}</tex>. Отсюда получаем <tex>A_{n}^{k} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n - k)!}</tex>
+При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть <tex>(n-1)</tex> элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>A_{n}^{k}=n \cdot A_{n-1}^{k-1}</tex>. Отсюда получаем <tex>A_{n}^{k} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}</tex>
 }}
@@ Строка 100: / Строка 100: @@
 Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.
-Тогда предположим, что число единиц в <tex>i</tex>-м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> - это элемент из изначального множества с номером i.
+Тогда предположим, что число единиц в <tex>i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> {{---}} это элемент из изначального множества с номером i.
 Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.

@@ Строка 104: / Строка 104: @@
 Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.
-Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.
+Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.
 Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>(n+k-1)</tex>. Таким образом, ответом будет являться число сочетаний из <tex>(n+k-1)</tex> по <tex>k</tex>. Тогда количество равно <tex> \overline{C_n^k} = C_{n+k-1}^{k}</tex>
 }}

@@ Строка 100: / Строка 100: @@
 Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.
-Тогда предположим, что число единиц в <tex>i</tex>-м блоке {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
+Тогда предположим, что число единиц в <tex>i</tex>-м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> - это элемент из изначального множества с номером i.
 Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.

@@ Строка 44: / Строка 44: @@
 Теорема | id=3
 |statement=
-Число различных перестановок с повторениями из <tex>k</tex> элементов с различными <tex>n</tex> группами одинаковых элементов равно <tex>\overline{P_k} (k_1, k_2, \ldots, k_n) = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>
+Число различных перестановок с повторениями из <tex>k</tex> элементов с <tex>n</tex> группами одинаковых элементов равно <tex>\overline{P_k} (k_1, k_2, \ldots, k_n) = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>, где <tex>k_i</tex> - это количество одинаковых элементов в <tex>i</tex>-ой группе.
 |proof=
-Пусть нужно найти количество перестановок с повторениями на множестве <tex>A</tex> из <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Количество перестановок из <tex>k</tex> элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равна <tex>k!</tex>.
+Пусть нужно найти количество перестановок с повторениями на множестве <tex>A</tex> из <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Количество перестановок из <tex>k</tex> элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равно <tex>k!</tex>.
 В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из <tex>k_i</tex>. Таким образом количество перестановок с одинаковым первым элементом будет равно <tex>k_1!</tex>, для второго элемента {{---}} <tex>k_2!</tex>. Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок <tex>k_1! \cdot k_2! \cdot \ldots \cdot k_n!</tex>. Ответом будем являться частное количества всех перестановок и количества одинаковых.

@@ Строка 100: / Строка 100: @@
 Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.
-Тогда предположим, что число единиц в <tex>i</tex>-м куске {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
+Тогда предположим, что число единиц в <tex>i</tex>-м блоке {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
 Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.

@@ Строка 47: / Строка 47: @@
 |proof=
-Пусть нужно найти количество перестановок с повторениями на множестве <tex>A</tex> из <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Количество перестановок из <tex>k</tex> элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равна <tex>k!</tex>, однако мы также должны учитывать то, что у нас <tex>n</tex> групп с одинаковыми элементами.
+Пусть нужно найти количество перестановок с повторениями на множестве <tex>A</tex> из <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Количество перестановок из <tex>k</tex> элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равна <tex>k!</tex>.
-В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из <tex>k_i</tex>. Таким образом количество перестановок с одинаковым первым элементом будет равно <tex>k_1!</tex>, для второго элемента {{---}} <tex>k_2!</tex>. Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок <tex>k_1! \cdot k_2! \cdot \ldots \cdot m_n!</tex>. Ответом будем являться частное количества всех перестановок и количества одинаковых.
+В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из <tex>k_i</tex>. Таким образом количество перестановок с одинаковым первым элементом будет равно <tex>k_1!</tex>, для второго элемента {{---}} <tex>k_2!</tex>. Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок <tex>k_1! \cdot k_2! \cdot \ldots \cdot k_n!</tex>. Ответом будем являться частное количества всех перестановок и количества одинаковых.
 Получаем, что итоговое количество равно <tex>\frac{k!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!} = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!} </tex>
 }}

@@ Строка 26: / Строка 26: @@
 Теорема | id=1
 |statement=
-Число различных битовых векторов равно <tex>2^{n}</tex>.
+Число различных битовых векторов длины <tex>n</tex> равно <tex>2^{n}</tex>.
 |proof=

@@ Строка 60: / Строка 60: @@
 |proof=
-Доказательство по индукции. Пусть <tex>k = 1</tex>. Тогда количество размещений из <tex>n</tex> по <tex>1</tex> равно <tex>n</tex>.
+Доказательство по индукции. База <tex>k = 1</tex>, тогда количество размещений из <tex>n</tex> по <tex>1</tex> равно <tex>n</tex>.
 При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть <tex>(n-1)</tex> элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>A_{n}^{k}=n \cdot A_{n-1}^{k-1}</tex>. Отсюда получаем <tex>A_{n}^{k} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n - k)!}</tex>
@@ Строка 84: / Строка 84: @@
 |proof=
-Всего размещений из <tex>n</tex> элементов по <tex>k</tex> равно <tex>A_n^k  = \frac{n!}{(n - k)!}</tex>. В каждом размещении выбраны какие-то <tex>k</tex> элементов из данного множества. Если игнорировать порядок этих выбранных <tex>k</tex> элементов, мы получим некоторые сочетания из данного множества по <tex>k</tex>. Другими словами, размещение с одним и тем же набором выбранных <tex>k</tex> элементов задают одно и то же сочетание по <tex>k</tex> элементов.
+Всего размещений из <tex>n</tex> элементов по <tex>k</tex> равно <tex>A_n^k  = \frac{n!}{(n - k)!}</tex>. В каждом размещении выбраны <tex>k</tex> элементов из данного множества. Если игнорировать порядок этих выбранных <tex>k</tex> элементов, мы получим некоторые сочетания из данного множества по <tex>k</tex>. Другими словами, размещение с одним и тем же набором выбранных <tex>k</tex> элементов задают одно и то же сочетание по <tex>k</tex> элементов.
 Так как размещения с одним и тем же набором выбранных <tex>k</tex> элементов различаются только порядком элементов и число различных перестановок из <tex>k</tex> элементов равно <tex>k!</tex>, то итоговая формула будет равна <tex>C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>
@@ Строка 100: / Строка 100: @@
 Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.
-Будем полагать, что число единиц в <tex>i</tex>-м куске {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
+Тогда предположим, что число единиц в <tex>i</tex>-м куске {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
 Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.
-Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>(n+k-1)</tex>. Таким образом, ответ будет число сочетаний из <tex>(n+k-1)</tex> по <tex>k</tex>. Тогда количество равно <tex> \overline{C_n^k} = C_{n+k-1}^{k}</tex>
+Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>(n+k-1)</tex>. Таким образом, ответом будет являться число сочетаний из <tex>(n+k-1)</tex> по <tex>k</tex>. Тогда количество равно <tex> \overline{C_n^k} = C_{n+k-1}^{k}</tex>
 }}

@@ Строка 1: / Строка 1: @@
-== Число комбинаторных объектов ==
+== Количество комбинаторных объектов ==
 {| class="wikitable" border = 1
-|'''Тип объекта'''||'''Число различных объектов'''
+|'''Тип объекта'''||'''Количество различных объектов'''
 |-
 |Битовые вектора||<tex>2^{n}</tex>

@@ Строка 22: / Строка 22: @@
 |}
-==Доказательства числа комбинаторных объектов.==
+==Доказательства числа комбинаторных объектов==
 {{
 Теорема | id=1