Обсуждение участника:Galibov Mikhail — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Число комбинаторных объектов)
(Доказательства числа комбинаторных объектов)
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Число комбинаторных объектов ==
+
== Количество комбинаторных объектов ==
 
{| class="wikitable" border = 1
 
{| class="wikitable" border = 1
|'''Тип объекта'''||'''Число различных объектов'''
+
|'''Тип объекта'''||'''Количество различных объектов'''
 
|-
 
|-
 
|Битовые вектора||<tex>2^{n}</tex>
 
|Битовые вектора||<tex>2^{n}</tex>
Строка 22: Строка 22:
 
|}
 
|}
  
==Доказательства числа комбинаторных объектов.==
+
==Доказательства числа комбинаторных объектов==
 
{{
 
{{
 
Теорема | id=1
 
Теорема | id=1
 
|statement=
 
|statement=
Число различных битовых векторов равно <tex>2^{n}</tex>.
+
Число различных битовых векторов длины <tex>n</tex> равно <tex>2^{n}</tex>.
  
 
|proof=
 
|proof=
Строка 44: Строка 44:
 
Теорема | id=3
 
Теорема | id=3
 
|statement=
 
|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=
 
|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>
 
Получаем, что итоговое количество равно <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>
 
}}
 
}}
Строка 60: Строка 60:
 
|proof=
 
|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>
+
При <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=
 
|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>
 
Так как размещения с одним и тем же набором выбранных <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>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> совпадает с числом таких векторов.  
+
Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.
  
Таких векторов столько, сколько вариантов выбрать <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>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>
 
}}
 
}}

Текущая версия на 00:26, 8 января 2021

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

Тип объекта Количество различных объектов
Битовые вектора [math]2^{n}[/math]
Перестановки [math]P_n = n![/math]
Перестановки с повторениями [math]\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!}[/math]
Размещения [math]A^{k}_n = \frac{n!}{(n - k)!}[/math]
Размещения с повторениями [math]\overline{A_n^k} = n^k[/math]
Сочетания [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]
Сочетания с повторениями [math]\overline{C^k_n} = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}[/math]
Разбиение на неупорядоченные слагаемые Нахождение количества разбиений числа на слагаемые
Разбиение на подмножества Числа Стирлинга второго порядка

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

Теорема:
Число различных битовых векторов длины [math]n[/math] равно [math]2^{n}[/math].
Доказательство:
[math]\triangleright[/math]
Число битовых векторов — это частный случай размещения с повторениями [math]2[/math] элементов по [math]n[/math]. Таким образом, количество различных битовых векторов будет равно [math]2^n[/math].
[math]\triangleleft[/math]
Теорема:
Число различных перестановок из [math]n[/math] элементов равно [math]P_n = n![/math]
Доказательство:
[math]\triangleright[/math]
Перестановка — это частный случай размещения [math]n[/math] элементов по [math]k[/math] при [math]k = n[/math]. Таким образом, количество различных перестановок будет равно [math]n![/math]
[math]\triangleleft[/math]
Теорема:
Число различных перестановок с повторениями из [math]k[/math] элементов с [math]n[/math] группами одинаковых элементов равно [math]\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!}[/math], где [math]k_i[/math] — это количество одинаковых элементов в [math]i[/math]—ой группе.
Доказательство:
[math]\triangleright[/math]

Пусть нужно найти количество перестановок с повторениями на множестве [math]A[/math] из [math]k[/math] элементов. Будем учитывать, что в этом множестве [math]n[/math] групп одинаковых элементов. Количество перестановок из [math]k[/math] элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равно [math]k![/math].

В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из [math]k_i[/math]. Таким образом количество перестановок с одинаковым первым элементом будет равно [math]k_1![/math], для второго элемента — [math]k_2![/math]. Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок [math]k_1! \cdot k_2! \cdot \ldots \cdot k_n![/math]. Ответом будем являться частное количества всех перестановок и количества одинаковых.

Получаем, что итоговое количество равно [math]\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!} [/math]
[math]\triangleleft[/math]
Теорема:
Число различных размещений из [math]n[/math] элементов по [math]k[/math] равно [math]A^{k}_n = \frac{n!}{(n - k)!}[/math]
Доказательство:
[math]\triangleright[/math]

Доказательство по индукции. База [math]k = 1[/math], тогда количество размещений из [math]n[/math] по [math]1[/math] равно [math]n[/math].

При [math]k \geq 2[/math] воспользуемся правилом произведения. Выбрать первый элемент можно [math]n[/math] различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть [math](n-1)[/math] элементов, по [math](k - 1)[/math]. Следовательно получаем рекуррентную формулу [math]A_{n}^{k}=n \cdot A_{n-1}^{k-1}[/math]. Отсюда получаем [math]A_{n}^{k} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}[/math]
[math]\triangleleft[/math]
Теорема:
Число различных размещений с повторениями из [math]n[/math] элементов по [math]k[/math] равно [math]\overline{A_n^k} = n^k[/math]
Доказательство:
[math]\triangleright[/math]

Докажем по индукции. База: [math]k = 1[/math]. Тогда [math] \overline{A_n^1} = n[/math].

При [math]k \geq 2[/math] воспользуемся правилом произведения. Выбрать первый элемент можно [math]n[/math] различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по [math](k - 1)[/math]. Следовательно получаем рекуррентную формулу [math]\overline{A_n^k} = n \cdot \overline{A_{n}^{k-1}}[/math]. Отсюда получаем [math]\overline{A_n^k}=n \cdot n \ldots = n^k [/math]
[math]\triangleleft[/math]
Теорема:
Число различных сочетаний из [math]n[/math] элементов по [math]k[/math] равно [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]
Доказательство:
[math]\triangleright[/math]

Всего размещений из [math]n[/math] элементов по [math]k[/math] равно [math]A_n^k = \frac{n!}{(n - k)!}[/math]. В каждом размещении выбраны [math]k[/math] элементов из данного множества. Если игнорировать порядок этих выбранных [math]k[/math] элементов, мы получим некоторые сочетания из данного множества по [math]k[/math]. Другими словами, размещение с одним и тем же набором выбранных [math]k[/math] элементов задают одно и то же сочетание по [math]k[/math] элементов.

Так как размещения с одним и тем же набором выбранных [math]k[/math] элементов различаются только порядком элементов и число различных перестановок из [math]k[/math] элементов равно [math]k![/math], то итоговая формула будет равна [math]C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}[/math]
[math]\triangleleft[/math]
Теорема:
Число различных сочетаний с повторениями из [math]n[/math] элементов по [math]k[/math] равно [math]\overline{C^k_n} = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим двоичный вектор из [math](n+k-1)[/math] координат, в котором [math](n-1)[/math] нулей и [math]k[/math] единиц.

Будем считать нули разделителями, которые делят этот вектор на [math]n[/math] частей.

Тогда предположим, что число единиц в [math]i[/math]—м блоке — это число элементов [math]k_i[/math] в сочетании с повторением, которое соответствует этому вектору, где [math]k_i[/math] — это элемент из изначального множества с номером i.

Пример: Если у нас есть набор элементов 1 1 2 2 3, то [math]k_2[/math] = 2.

Получаем, что каждому сочетанию с повторениями из [math]n[/math] по [math]k[/math] соответствует некоторый вектор из нулей и единиц с [math](n+k-1)[/math] координатами, в котором [math](n-1)[/math] нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из [math]n[/math] по [math]k[/math] совпадает с числом таких векторов.

Таких векторов столько, сколько вариантов выбрать [math]k[/math] координат, на которых должны стоять единицы из [math](n+k-1)[/math]. Таким образом, ответом будет являться число сочетаний из [math](n+k-1)[/math] по [math]k[/math]. Тогда количество равно [math] \overline{C_n^k} = C_{n+k-1}^{k}[/math]
[math]\triangleleft[/math]