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

Перестановками с повторениями из n элементов по k называется упорядоченное подмножество из k элементов n -элементного множества, в которой каждый элемент множества встречается k_i раз (причем, k₁+k₂+... +k_n=k). Число перестановок с повторениями обозначается

Сочетаниями с повторениями из n элементов по k называются неупорядоченные подмножества k элементов, выбранных из данных n элементов, среди которых могут быть одинаковые элементы, и которые отличаются они хотя бы одним элементом (неупорядоченная (n, k)-выборка с возвращением). Число элементов каждого вида неограниченно.

Пример

А={a,b,с},

{а,b,а,а,а,а},

{b,b,a,c,a,a},

{с,с,с,с,b,b}

Эти множества можно записать следующим образом:

где количество единиц обозначает количество элементов a,b,с, ноль – разделитель между группами различных элементов. Т.е задача определения количества таких сочетаний сводится к задаче нахождения числа перестановок с повторениями.

Число различных сочетаний с повторениями из n элементов по k обозначается и вычисляется по формуле

Пример

У преподавателя есть карточки на четыре различных варианта. Сколькими способами можно выбрать шесть карточек?

Соединение Тип	Перестановки	Размещения	Сочетания
Без повторений
С повторениями

Для n элементов существует (n-1)! круговых перестановок.

Пример

Сколькими способами можно рассадить 5 детей за круглым и за квадратным столом?

За квадратным: P₅ = 5!

За круглым: P₄ = 4!

Для доказательства свойств сочетаний иногда удобно применять геометрический способ доказательства. Этот способ в комбинаторике основан на подсчете различных кратчайших путей (ломаных), ведущих из точки в точку . Такие пути можно зашифровать последовательностью из нулей и единиц: нуль означает место, где ломаная идет вправо, а единица - место, где она идет вверх. Число последовательностей из нулей и единиц равно числу перестановок с повторениями

Дата добавления: 2014-01-15