Конспект: элементы комбинаторики [часть 2] (алгебра)

Размещения, перестановки, сочетания

Определение 1. Размещениями из n элементов по k называются упорядоченные выборки по k элементов из n элементов.Пример. Пусть даны четыре элемента – ( a ), ( b ), ( c ) и ( d ). Выпишем все размещения из четырех элементов по три: begin{gather} abc abd acb acd adb adc tag{1} \ bac bad bca bcd bda bdc \ cab cad cba cbd cda cdb \ dab dac dba dbc dca dcb end{gather} (различным цветом выделены группы, состоящие из одних и тех же элементов). Подсчитаем число различных размещений из n элементов по ( k ) элементов. Так как первый элемент можно выбрать n различными способами, второй, после того как первый выбран, можно выбрать ( n-1 ) числом способов и т.д., ( k )-ый элемент, после того как выбраны предыдущие, можно выбрать ( n-(k-1) ) числом способов, то искомое число, если его обозначить через ( A_n^k ), будет равно произведению следующих сомножителей: ( A_n^k = n cdot (n – 1) cdot … cdot (n – k + 1) tag{2} ) Определение 2. Размещения из ( n ) элементов по ( n ) элементов называются перестановками из ( n ) элементов. В таблице (1) одинаковым цветом выделены перестановки из трех элементов. Число различных перестановок из ( n ) элементов очевидно равно ( A_n^n = n cdot (n – 1) cdot … cdot 2 cdot 1 = n! ) (читается: n факториал). Определение 3. Сочетаниями из ( n ) элементов по ( k ) называются неупорядоченные выборки по ( k ) элементов из ( n ) элементов. Два сочетания различны, если они отличаются, по крайней мере, одним элементом. В таблице (1) размещения, выделенные разным цветом, соответствуют разным сочетаниям, выделенные одним цветом, соответствуют одному и тому же сочетанию. Все множество ( A_n^k ) размещений из ( n ) элементов по ( k ) элементов можно разбить на группы, так что все члены группы будут состоять из одних и тех же элементов. Каждая такая группа будет состоять из ( k! ) размещений, различающихся лишь порядком элементов, но не самими элементами. Каждой такой группе будет соответствовать одна и та же неупорядоченная выборка или сочетание. Если обозначить число сочетаний из ( n ) элементов по ( k ) через ( C_n^k ) , то ( C_n^k = frac{n cdot (n – 1) cdot … cdot (n – k + 1)}{k!} tag{3} ) Формула (3) верна для ( 1 leq k leq n ). Если положить по определению, что ( 0!=1 ), то эту формулу можно переписать в виде ( C_n^k = frac{n!}{k!(n! – k!)} tag{4} ) верную уже для ( 1 leq k leq n ) Рассмотрим некоторые свойства числа сочетаний. 1) ( C_n^k = C_n^{n-k} = frac{n!}{(n! – k!)k!} ) 2) ( C_n^k + C_n^{k-1} = frac{n!}{k!(n! – k!)} + frac{n!}{(k-1)!(n – k + 1)!} = frac{n![(n – k + 1) + k]}{(n+1-k)!k!} = frac{(n + 1)!}{(n+1-k)!k!} = C_{n+1}^k ) Свойство 2) дает возможность практического вычисления числа сочетаний для различных ( n ) и ( k ) методом, носящим название треугольника Паскаля begin{gather} C_0^0 \ C_1^0 C_1^1 \ C_2^0 C_2^1 C_2^2 \ C_3^0 C_3^1 C_3^2 C_3^3 \ C_4^0 C_4^1 C_4^2 C_4^3 C_4^4 \ C_5^0 C_5^1 C_5^2 C_5^3 C_5^4 C_5^5 \ … … … … … … … \ end{gather} Заменив соответствующие ( C_k^n ) их числовыми значениями, получим «треугольник Паскаля»: begin{gather} 1 \ 1 1 \ 1 2 1 \ 1 3 3 1 \ 1 4 6 4 1 \ 1 5 10 10 5 1 \ … … … … … … … \ end{gather} Способ построения треугольника Паскаля очевиден – в последующей строке на место, расположенное между двумя соседними элементами предыдущей строки, ставится число, равное их сумме (свойство 2)). Каждая строка начинается и заканчивается единицей. Элементы, расположенные на одинаковом расстоянии от начала и конца строки, равны между собой (свойство 1)).
Автор данной лекции – Хитров Г. М. (кандидат физико-математических наук, доцент кафедры высшей математики). Перейти на страницу.
Опубликовано: 22 сентября

Добавить свой комментарий

(обязательно):