Статистическая обработка результатов учебно-исследовательской деятельности учащихся - Учебное пособие (Мельникова Ю.Б.)

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!