Обсуждение участника:Galibov Mikhail

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

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

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

Теорема:

Число битовых векторов равно [math]2^{n}[/math].

Доказательство:

[math]\triangleright[/math]

Число битовых векторов — это частный случай размещения с повторениями [math]2[/math] элементов по [math]n[/math]. Таким образом ответ [math]2^n[/math]. Смотрите доказательство размещения с повторениями.

[math]\triangleleft[/math]

Теорема:

Число перестановок равно [math]P_n = n![/math]

Доказательство:

[math]\triangleright[/math]

Перестановка — это частный случай размещения [math]n[/math] элементов по [math]k[/math] при [math]k = n[/math]. Таким образом смотрите доказательство размещений.

[math]\triangleleft[/math]

Теорема:

Число перестановок с повторениями равно [math]\widetilde{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]\triangleright[/math]

Пусть нам нужно найти количество перестановок с повторениями на множестве [math]A[/math] в котором [math]k[/math] элементов. Будем учитывать, что в этом множестве [math]n[/math] групп одинаковых элементов. Таким образом количество перестановок не учитывая того факта, что элементы могут быть одинаковые будет равна [math]k![/math] однако мы также должны учитывать то, что у нас [math]n[/math] групп с одинаковыми элементами. В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из [math]k_i[/math]. Таким образом количество перестановок с одинаковым первым элементом будет [math]k_1![/math], для второго элемента — [math]k_2![/math]. Общее количество будет равно произведению данных факториалов. Итого одинаковых перестановок — [math]k_1! \cdot k_2! \cdot \ldots \cdot m_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]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](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]\widetilde{A}_n^k = n^k[/math]

Доказательство:

[math]\triangleright[/math]

Доказательство по индукции. Пусть [math]k = 1[/math]. Тогда [math] \widetilde{A}_n^1 = n[/math]. При [math]k \geq 2[/math] воспользуемся правилом произведения. Выбрать первый элемент [math]n[/math] различных значений. При любом первом элементе, все что осталось образует размещение с повторениями по [math](k - 1)[/math] из того же множества. Таким образом получаем рекуррентную формулу [math]\widetilde{A}_n^k = n \cdot \widetilde{A}_{n}^{k-1}[/math]. Таким образом получаем [math]\widetilde{A}_n^k=n \cdot n \ldots = n^k [/math]

[math]\triangleleft[/math]

Теорема:

Число сочетаний равно [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим все размещения из [math]n[/math] элементов по [math]k[/math]. Их [math]A_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] C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}[/math]

[math]\triangleleft[/math]

Теорема:

Число сочетаний с повторениями равно [math]\widetilde{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]a_i[/math] в сочетании с повторением, которое соответствует этому вектору. Получаем, что каждому сочетанию с повторениями из [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] \widetilde{C}_n^k = C_{n+k-1}^{k}[/math]

[math]\triangleleft[/math]