20. Комбинаторика. Сочетания без повторений и с повторениями. Свойства сочетаний. Доказать одно из них. Привести примеры.

Комбинато́рика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).

Сочетания без повторений из n элементов по k называется неупорядоченное количество выборки из n элементов без повторений.

C^k_n=n!/k!(n-k)! k=n.

Сочетание из n по k без повторений образует k-элементов подмножества мощности n.

Сколькими способами можно разместить в пятибуквенном слове 2 буквы a?

Сочетание - это класс эквивалентности размещений из m элементов по n, при этом два размещения объема n из данного m-элементного множества считаются эквивалентными, если они состоят из одних и тех же элементов, взятых одно и то же число раз. Класс эквивалентности размещений с повторениями называется сочетанием с повторениями. Число сочетаний с повторениями из m по n равно . =(n+k+1)!/k!(n-1)

В палитре художника 8 различных красок. Художник берет кистью наугад любую из красок и ставит цветное пятно на ватмане. Затем берет следующую кисть, окунает её в любую из красок и делает второе пятно по соседству. Сколько различных комбинаций существует для шести пятен? Порядок пятен на ватмане не важен.

Решение

Решим задачу следующим образом. Пусть количество пятен первого цвета равно k1, второго цвета – k2, третьего – k3 и так далее. Запишем каждое из этих чисел последовательностью из соответствующего количества единиц, а на границах между числами поставим нули. Так, если у нас первого цвета 1 пятно, второго – 3 пятна, третьего и четвёртого – ни одного, пятого и шестого – по одному пятну, а седьмого и восьмого – снова не одного, то запись будет выглядеть следующим образом: 1011100010100. В этой цепочке содержится m1 = 6 единиц, m0 – 1 = 8 – 1 = 7 нулей – всего n = m0 + m1 – 1 = 13 цифр. Количество перестановок с повторениями этих цифр равно

Свойства сочетаний:

1.

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

2. k<n

3.

4.

5.

21. Комбинаторика. Перестановки с повторениями. Циклические перестановки. Подсчет числа беспорядков. Привести примеры.

Комбинато́рика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики — алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике).

Последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй — n2 раз, третий — n3 раз,…, k-й — nk раз (где n1+ n2+ … + nk = n) называется перестановкой с повторениями из n элементов.

Например, пусть дан набор из четырех букв aabc. Тогда все перестановки с повторениями из этих букв суть abac, baac, aabc, aacb, abca, baca, acba, acab, bcaa, cbaa, caba, caab.

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n1, n2, …, nk раз каждый обозначается P(n1, n2, …, nk) и равно n! / (n1! n2! … nk!).

В рассмотренном выше примере, букв a в исходном наборе две, а букв b и с — по одной. Следовательно, количество всех перестановок с повторениями из 4 элементов и составом букв 2, 1, 1 равно P(2, 1, 1) = 4! / (2! 1! 1!) = 12, в чем мы и убедились.

Циклические перестановки.

7 девушек водят хороод сколькими различными способами они могут встать в круг?

Если бы они стояли на месте то 7! Способов, но так как они кружатся их положение относительно окружающего не существенно, а важно их взаимное расположение. Поэтому количество перестановок=7!/7=6!

Число N перестановок из цифр множества {1, 2, 3,…, n} таких, что никакая цифра не остается на своем месте, можно найти по формуле: N=n! (-1)^k1/k!