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

Размещение без повторений

Размещения без повторений — комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

формула для нахождения количества размещений без повторений:


Размещения с повторениями — комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

 

формула для нахождения количества размещений с повторениями:

Перестановки.

В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i -й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово расстановка.

Свойства:

Число всех перестановок порядка равно числу размещений из n по n, то есть факториалу:^[1][2][3][4]

Композиция определяет операцию произведения на перестановках одного порядка: Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают .

Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой тождеством где g — произвольный элемент группы G, а — групповая операция.

Сочетания.

В комбинаторике сочетанием из по называется набор элементов, выбранных из данного множества, содержащего различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-хэлементные сочетания, подмножества, ) {2, 1, 3} и {3, 2, 1} 6-тиэлементного множества {1, 2, 3, 4, 5, 6} () являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать элементов из множества, содержащего различных элементов, стоит на пересечении -й диагонали и -й строки треугольника Паскаля.^[1]

Сочетания с повторениями.

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

Число сочетаний с повторениями из по равно биномиальному коэффициенту

При фиксированном производящей функцией чисел сочетаний с повторениями из по является:

Двумерной производящей функцией чисел сочетаний с повторениями является:

Бином Ньютона.

Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

,

где — биномиальные коэффициенты, — неотрицательное целое число.

В таком виде эта формула была известна ещё индийским и исламским математикам; Ньютон вывел формулу бинома для более общего случая, когда показатель степени — произвольное рациональное число (возможно, отрицательное). В этом случае бином представляет собой бесконечный ряд

Свойства бинома Ньютона

Разложение бинома (a + b)ⁿ представляет собой многочлен, расположенный по убывающим степеням a (от n-й до нулевой) и по возрастающим степеням b (от нулевой до n-й); сумма показателей a и b в каждом члене разложения равна показателю степени бинома. Число членов разложения на единицу больше показателя степени бинома.

Коэффициенты членов разложения («биноминальные коэффициенты») возрастают до середины разложения и затем убывают; коэффициенты каждой пары членов, равноотстоящих от начала и конца разложения, равны между собой. Если n четное, то имеется один средний наибольший коэффициент; если n нечетное, то имеется два средних наибольших коэффициента.

При возведении в n-ю степень разности a - b все четные члены разложения имеют знак "минус":

Треугольник Паскаля.

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

Свойства

Числа треугольника симметричны(равны) относительно вертикальной оси.

В строке с номером n:

первое и последнее числа равны 1.

второе и предпоследнее числа равны n.

третье число равно треугольному числу , что также равно сумме номеров предшествующих строк^[3].

четвёртое число является тетраэдрическим^[3].

m -е число равно биномиальному коэффициенту .

Сумма чисел восходящей диагонали, начинающейся с первого элемента (n -1)-й строки, есть n -е число Фибоначчи:^[3]

Если вычесть из центрального числа в строке с чётным номером соседнее число из той же строки, то получится число Каталана.^[3]

Сумма чисел n -й строки треугольника Паскаля равна ^[3].

Все числа в n -й строке, кроме единиц, делятся на число n, если и только если n является простым числом^[4] (следствие теоремы Люка).

Простые делители чисел треугольника Паскаля образуют детерминистские фракталы с вращательной симметрией 3-го порядка, которые в полной мере выявляются учётом показателей степеней простых делителей [6].

Если в строке с нечётным номером сложить все числа с порядковыми номерами вида 3 n, 3 n +1, 3 n +2, то первые две суммы будут равны, а третья на 1 меньше.

Каждое число в треугольнике равно количеству способов добраться до него из вершины, перемещаясь либо вправо-вниз, либо влево-вниз.

Полиномиальная формула.

Формула

(х₁+х₂+…+х_k)ⁿ = (1)

 

называется полиномиальной, где суммирование выполняется по всем решениям уравнения n₁+n₂+ …+ n_k = n в целых неотрицательных числах, n_i 0, I =1,2,…,k.

 

Для доказательства выполним умножение

 

(х₁+х₂+…+х_k)·(х₁+х₂+…+х_k) … (х₁+х₂+…+х_k) = (х₁+х₂+…+х_k)ⁿ.

n

 

Чтобы привести подобные в полученном выражении, необходимо подсчитать количество одночленов вида каждого разбиения n₁+n₂+ …+ n_k = n. Для получения же одночлена необходимо выбрать х₁ в качестве множителя в n₁ скобках при раскрытии выражения (х₁+х₂+…+х_k)ⁿ. Это можно сделать способами. Из оставшихся n – n₁ не раскрытых скобок необходимо выбрать х₂ в качестве множителя в n₂ скобках. Это можно сделать способами и т.д. Тогда количество одночленов при раскрытии выражения

 

(х₁+х₂+…+х_k)·(х₁+х₂+…+х_k) … (х₁+х₂+…+х_k)

 

n

 

будет равно числу … = упорядоченных разбиений.

Рекуррентные соотношения.

!

Свойства

Производящая функция суммы (или разности) двух последовательностей равна сумме (или разности) соответствующих производящих функций.

Произведение производящих функций и последовательностей и является производящей функцией свёртки этих последовательностей:

Примеры использования

Пусть — это количество композиций неотрицательного целого числа n длины m, то есть, представлений n в виде , где — неотрицательныецелые числа. Число также является числом сочетаний с повторениями из m по n, то есть, количество выборок n возможно повторяющих элементов из множества (при этом каждый член в композиции можно трактовать как количество элементов i в выборке).

При фиксированном m производящей функцией последовательности является:

Поэтому число может быть найдено как коэффициент при в разложении по степеням x. Для этого можно воспользоваться определением биномиальных коэффициентов или же непосредственно взять n раз производную в нуле:

 

Задача Фибоначчи

Пусть в огороженном месте имеется пара кроликов (самка и самец) в первый день января. Эта пара кроликов производит новую пару кроликов в первый день февраля и затем в первый день каждого следующего месяца. Каждая новорожденная пара кроликов становится зрелой уже через месяц и затем через месяц дает жизнь новой паре кроликов. Возникает вопрос: сколько пар кроликов будет в огороженном месте через год, то есть через 12 месяцев с начала размножения?"

 

Производящая функция

Последовательность числа разбиений имеет следующую производящую функцию:

Размещение без повторений

Размещения без повторений — комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

формула для нахождения количества размещений без повторений:


Размещения с повторениями — комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

 

формула для нахождения количества размещений с повторениями:

Перестановки.

В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i -й элемент из набора. Число n при этом называется порядком перестановки. Как синоним слову "перестановка" в этом смысле некоторые авторы используют слово расстановка.

Свойства:

Число всех перестановок порядка равно числу размещений из n по n, то есть факториалу:^[1][2][3][4]

Композиция определяет операцию произведения на перестановках одного порядка: Относительно этой операции множество перестановок порядка n образует группу, которую называют симметрической и обычно обозначают .

Любая группа является подгруппой группы перестановок множества элементов этой группы (теорема Кэли). При этом каждый элемент сопоставляется с перестановкой , задаваемой тождеством где g — произвольный элемент группы G, а — групповая операция.

Сочетания.

В комбинаторике сочетанием из по называется набор элементов, выбранных из данного множества, содержащего различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Так, например, наборы (3-хэлементные сочетания, подмножества, ) {2, 1, 3} и {3, 2, 1} 6-тиэлементного множества {1, 2, 3, 4, 5, 6} () являются одинаковыми (однако, как размещения были бы разными) и состоят из одних и тех же элементов {1,2,3}.

В общем случае число, показывающее, сколькими способами можно выбрать элементов из множества, содержащего различных элементов, стоит на пересечении -й диагонали и -й строки треугольника Паскаля.^[1]

Сочетания с повторениями.

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

Число сочетаний с повторениями из по равно биномиальному коэффициенту

При фиксированном производящей функцией чисел сочетаний с повторениями из по является:

Двумерной производящей функцией чисел сочетаний с повторениями является:

Бином Ньютона.

Бино́м Нью́то́на — формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид

,

где — биномиальные коэффициенты, — неотрицательное целое число.

В таком виде эта формула была известна ещё индийским и исламским математикам; Ньютон вывел формулу бинома для более общего случая, когда показатель степени — произвольное рациональное число (возможно, отрицательное). В этом случае бином представляет собой бесконечный ряд

Свойства бинома Ньютона

Разложение бинома (a + b)ⁿ представляет собой многочлен, расположенный по убывающим степеням a (от n-й до нулевой) и по возрастающим степеням b (от нулевой до n-й); сумма показателей a и b в каждом члене разложения равна показателю степени бинома. Число членов разложения на единицу больше показателя степени бинома.

Коэффициенты членов разложения («биноминальные коэффициенты») возрастают до середины разложения и затем убывают; коэффициенты каждой пары членов, равноотстоящих от начала и конца разложения, равны между собой. Если n четное, то имеется один средний наибольший коэффициент; если n нечетное, то имеется два средних наибольших коэффициента.

При возведении в n-ю степень разности a - b все четные члены разложения имеют знак "минус":

Треугольник Паскаля.

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

Свойства

Числа треугольника симметричны(равны) относительно вертикальной оси.

В строке с номером n:

первое и последнее числа равны 1.

второе и предпоследнее числа равны n.

третье число равно треугольному числу , что также равно сумме номеров предшествующих строк^[3].

четвёртое число является тетраэдрическим^[3].

m -е число равно биномиальному коэффициенту .

Сумма чисел восходящей диагонали, начинающейся с первого элемента (n -1)-й строки, есть n -е число Фибоначчи:^[3]

Если вычесть из центрального числа в строке с чётным номером соседнее число из той же строки, то получится число Каталана.^[3]

Сумма чисел n -й строки треугольника Паскаля равна ^[3].

Все числа в n -й строке, кроме единиц, делятся на число n, если и только если n является простым числом^[4] (следствие теоремы Люка).

Простые делители чисел треугольника Паскаля образуют детерминистские фракталы с вращательной симметрией 3-го порядка, которые в полной мере выявляются учётом показателей степеней простых делителей [6].

Если в строке с нечётным номером сложить все числа с порядковыми номерами вида 3 n, 3 n +1, 3 n +2, то первые две суммы будут равны, а третья на 1 меньше.

Каждое число в треугольнике равно количеству способов добраться до него из вершины, перемещаясь либо вправо-вниз, либо влево-вниз.

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

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

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

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n ₁, n ₂, …, n_k раз каждый обозначается P (n ₁, n ₂, …, n_k) и равно

n! / (n ₁! n ₂! … n_k!).

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

Полиномиальная формула.

Формула

(х₁+х₂+…+х_k)ⁿ = (1)

 

называется полиномиальной, где суммирование выполняется по всем решениям уравнения n₁+n₂+ …+ n_k = n в целых неотрицательных числах, n_i 0, I =1,2,…,k.

 

Для доказательства выполним умножение

 

(х₁+х₂+…+х_k)·(х₁+х₂+…+х_k) … (х₁+х₂+…+х_k) = (х₁+х₂+…+х_k)ⁿ.

n

 

Чтобы привести подобные в полученном выражении, необходимо подсчитать количество одночленов вида каждого разбиения n₁+n₂+ …+ n_k = n. Для получения же одночлена необходимо выбрать х₁ в качестве множителя в n₁ скобках при раскрытии выражения (х₁+х₂+…+х_k)ⁿ. Это можно сделать способами. Из оставшихся n – n₁ не раскрытых скобок необходимо выбрать х₂ в качестве множителя в n₂ скобках. Это можно сделать способами и т.д. Тогда количество одночленов при раскрытии выражения

 

(х₁+х₂+…+х_k)·(х₁+х₂+…+х_k) … (х₁+х₂+…+х_k)

 

n

 

будет равно числу … = упорядоченных разбиений.

Рекуррентные соотношения.

!