Изменения

|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}

|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными'''(англ. ''ordered'').

{{Определение|definition='''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.

{{Определение|definition='''Перестановки<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>-й элемент из набора. Количество перестановок равно <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>местам.

{{Определение|definition='''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — это те же перестановки, однако некоторые элементы могут встречаться несколько раз. Число различных перестановок с повторениями из элементов }}В пример можно привести следующую задачу: имеется набор книг <tex>\{a_1, a_2, ...\ldots, a_n\}</tex>, каждая из которых имеется в которых эти элементы повторяются соответственно <tex>k_1, k_2, ..., k_n</tex> раз, равно <tex dpi = "150">\frac{(k_1 + k_2 + ... + k_n)!}{k_1!k_2!...k_n!}</tex>. Выведем формулу. Всего перестановок <tex>(k_1 + k_2 + ... + k_n)!</tex>, однако среди них есть и повторяющиеся. Такие попадаютсяldots, когда мы переставляем местами одинаковые элементы. Тогда всего повторяющихся перестановок будет в <tex>k_1!k_2!...k_n!</tex> раз. В итоге получаем необходимую формулуэкземплярах соответственно.Сколько существует способов переставить книги на полке?

{{Определение|definition='''Размещение'''<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>-элементного множества. Таких наборов <tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}Примером размещения может служить задача о рассадке </tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>nk</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>.

{{Определение|definition='''Размещение с повторениями'''(англ. ''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>. Всего таких элементов }}В пример можно привести следующую задачу: имеется <tex>n^</tex> книг, каждая в <tex>k</tex>экземплярах. Формула выводится так же, как и для битовых векторов.Сколькими способами может быть сделан выбор книг из числа данных?

{{Определение|definition='''Сочетания<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> элементов. Количество таких наборов вычисляется по формуле <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>вариантов.

{{Определение|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом. Способов таких выборов всего }}В пример можно привести следующую задачу: имеется <tex dpi = "150">\tilde{\sf_C}^k_n = \frac{(n + </tex> пирожных. Сколько способов купить <tex>k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>.пирожных?

{{Определение|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') &mdash; это представление числа <tex>n</tex> в виде суммы слагаемых. Всего таких разбиений::<p><tex>P_{n,k} = \left \{ \begin{array}{ll} P_{n,k - 1} + P_{n - k, k}, & 0 < k \leqslant n \\ P_{n, n}, & k > n \\1, & n = 0, k = 0 \\0, & n \neq 0 , k = 0, \end{array} \right.</tex></p>где <tex>k</tex> — число, не превышаемое слагаемыми, причем начальное значение <tex>k = n</tex>. Вывод формулы можно найти [[main|Нахождение количества разбиений числа на слагаемые | здесь]].}}

{{Определение|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:

Если задано множество из <tex>n</tex> элементов, которое необходимо разбить на <tex>k</tex> непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть (<tex dpi = "180">\lbrace{n-1\atop k-1}\rbrace</tex> способами), либо поместить его в некоторое подмножество (<tex>k</tex><tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способами, поскольку каждый из <tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способов распределения первых <tex>n-1</tex> элементов по <tex>k</tex> непустым частям дает <tex>k</tex> подмножеств, с которыми можно объединить последний элемент). <tex>\begin{Bmatrix}n \\k\end{Bmatrixmain|Числа Стирлинга второго рода} = \begin{cases}k\begin{Bmatrix}n-1 \\k\end{Bmatrix} + \begin{Bmatrix}n-1 \\k-1\end{Bmatrix}, 0<k<n \\0, k = 0 \\0, n = 0 \\0, k > n \\1, k = n\end{cases}</tex>

Подробнее можно прочитать == Число комбинаторных объектов =={| class="wikitable" border = 1|'''Тип объекта'''||'''Число объектов'''|-|Битовые вектора||<tex>2^{n}</tex>|-|Перестановки||<tex>P_n = n!</tex>|-|Перестановки с повторениями||<tex dpi = "150">\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>|-|Размещения||<tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>|-|Размещения с повторениями||<tex>n^k</tex>|-|Сочетания||<tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>|-|Сочетания с повторениями||<tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>|-|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]|-|Разбиение на странице о подмножества||[[Числа Стирлинга второго рода | числах Числа Стирлинга второго порядка]]|} == См.также ==*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение следующего объекта | Получение следующего объекта]]*[[Получение номера по объекту | Получение номера по объекту]]*[[Получение объекта по номеру | Получение объекта по номеру]]