1.3 перестановки. число перестановокНа практике часто возникают задачи, связанные с установлением порядка во множестве. Например, число мест равно количеству людей, на которых мы должны разместить их. Такая ситуация встречается часто — рассадить n человек на n мест, или приписать каждому человеку номер. Первый человек может выбрать любое из n мест, второй человек выбирает из (n -1)оставшихся ест, третий человек может выбрать из уже (n -2) мест, предпоследний человек выбирает из 2 мест, а последний получает последнее место. Мы получаем произведение всех целых чисел от n до 1. . В общем виде произведение всех целых чисел от 1до n включительно обозначают n!=1*2*3...(n -2)*(п-1)*n; Определение. Установленный в конечном множестве порядок называют перестановкой его элементов. Перестановки можно образовывать из элементов любого конечного множества. Число перестановок из n элементов обозначают Pn. Возьмем одноэлементное множество {а}. Ясно, что один элемент можно упорядочить единственным образом, следовательно, P1=1. Перестановки — это такие соединения по n элементов из данных элементов, которые отличаются одно от другого порядком элементов. Возьмем двухэлементное множество {а, b}. В нем можно установить два порядка: {а, b} или {b,a}. Следовательно, число перестановок из двух элементов P2=2. Три буквы во множестве {a,b, с} можно расположить по порядку шестью способами: {а,b,с}; {а,с,b}; {b.а.с}; {b,с,а}; {с,b,а} ;{с,а,b}. Следовательно, общее число способов упорядочения трех элементов множества P3 =3*P2 =3*2*1=6. Докажем, что справедлива рекурентная формула: Pn =n*Pn-1 (*) Пусть требуется упорядочить n - элементное множество. Полагая в формуле (*) последовательность n=2, 3, 4. ..., имеем: P2 =2*Р1=2*1, P3=3*Р2 =3*2*1; P4 = 4 • Р3 = 4 • 3 • 2 • 1 Методом полной математической индукции докажем, что при любом натуральном n справедлива формула. Рn=n*(n-1)*(n-2)*...*2*1=n! (**) где n!=1*2*3*... *n — произведение всех натуральных чисел от I до n. При n=1 формула (**) справедлива, так как Р1 =1 . Предположим, что формула (**) справедлива при n=k и докажем ее справедливость при n=k+1. Действительно, по рекуррентной формуле (*) при n=k+1 имеем Pk+1 =(k+1)*Pk (***) При n=k формула (**) справедлива, следовательно, Pk =k * (k-1)*…*2*1 (****) Подставив (****) в (***), имеем Pk+1 =(k+1)*k*(k-1)*…*2*1=(k+1)! Итак, число способов упорядочения n элементов множества равно n!
|
| Оглавление| |