Вопрос 2. Методы пересчета. 
Перестановки, сочетания, транспозиции

Комбинаторика — один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в ВТ, кибернетике, робототехнике. Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств, поэтому эти две темы — элементы теории множеств и комбинаторика — рассматриваются взаимосвязано. Упорядоченные множества. Перестановки.

Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое число (номер элемента) от до где — число элементов множества.

Всякое конечное множество можно сделать упорядоченным, если, например, переписать все элементы множества в некоторый список (.), а затем каждому элементу присвоить номер.

Упорядоченные множества считаются различными, если они отличаются либо своими элементами, либо их порядком.

Различные упорядоченные множества, которые отличаются лишь порядком элементов, называются перестановками этого множества.

Пример. Перестановки множества из 3-х элементов имеют вид .

Число перестановок из элементов !

Задача 1. Сколькими способами можно разместить на плате 4 элемента?. дискретная математика комбинаторика бинарный Задача 2. Сколькими способами можно выстроить в линейку 10 человек (5 девушек и 5 юношей) с условием, чтобы девушки и юноши чередовались? 5 девушек можно разместить ! способами, а 5 юношей аналогично !. Следовательно, всего способов .

Перестановка называется транспозицией, если переставляются местами только два элемента множества, тогда как остальные элементы остаются на своих местах.

Пример перестановки:

Пример транспозиции:

Любую перестановку множества S можно осуществить посредством нескольких транспозиций. Например, перестановка {2,4,1,3} является результатом трех транспозиций множества S :