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

Из формулы (1) для числа сочетаний вытекает 2 свойства числа сочетаний:

1. =

2. +

Из формулы (1) с учетом того, что 0! = 1 вытекает, что = .

С учетом сделанного замечания, второе свойство позволяет вычислять число сочетаний с помощью треугольника Паскаля.

Число сочетаний также называется биноминальным коэффициентом.

Рассмотрим формулы, позволяющие возводить в степень (a+b):

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

С помощью метода математической индукции можно доказать формулу:

(2)

Соотношение (2) называется биномом Ньютона; откуда вытекает второе название числа сочетаний – биноминальный коэффициент.

Определение: Преобразование перестановки, которое меняет местами какие-либо два символа, а все остальные символы оставляет на своих местах называется транспозицией.

Определение: Два числа i , j образуют в перестановке инверсию, если i > j , и i стоит в перестановке раньше j.

Пример:

Подсчитать число инверсий в перестановке 32145.

1-ца образует две инверсии, 2-ка образует одну инверсию.

2 + 1 + 0 + 0 + 0 = 3 инверсии.

Сделаем в нашей перестановке транспозицию (поменяем местами 1 и 5). Посчитаем число инверсий.

3 2 5 4 1

4 + 1 + 0 + 1 + 0 = 6 инверсий

Определение: Перестановка называется четной, если число инверсий в ней определено четным числом, нечетная в обратном случае.

Теорема: Каждая транспозиция меняет четность в перестановке.

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

Каждую подстановку n – го порядка можно записать с помощью 2 -х перестановок.

В такой записи подчеркивается что три переходит в четыре 3-4, 2-3, 1-2, 4-5, 5-1.Одну и ту же подстановку можно записать различными способами :

1)поменяв в подстановке какие-либо столбцы

При такой записи видим, что число различных подстановок определяется нижней строкой, т.е. числом различных перестановок, следовательно число различных подстановок n-го порядка равного n!.

Подстановка называется четной, если сумма числа инверсий обоих ее перестановок является четным числом и нечетной в противном случае. Отметим , что выполнив в подстановке транспозицию столбцов не изменяим ее четности.