Элементы комбинаторики. Перестановки.

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

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

Алгоритм нахождения перестановок:

  1. Выберем элемент, который будет находиться на первом месте. Количество способов его выбрать равняется количеству элементов. Всего n элементов, значит количество способов тоже n.
  2. Так как первый элемент уже на месте, то количество элементов которые ещё не на месте уменьшается на единицу. На второе место мы можем поставить n-1 элемента.
  3. На третье место n-2 элемента.
  4. На четвертое n-3 элемента.
  5.  ...

n. На n-ое место оставшийся элемент.

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

Pn=n•(n-1)•(n-2)•(n-3)•...•1=n!

n! - произведение n первых натуральных чисел (читается как "эн факториал")

Замечание: 

Пустое множество можно упорядочить только одним способом. Полагают, что 0!=1.

Примеры:

  1. Сколько различных способов выстроиться в ряд компании из 6 человек?

    Решение:

    P6=6•(6-1)•(6-2)•(6-3)•...•1=6!=720.

    Ответ: 720.

  2. Сколько различных чисел можно составить из цифр 1, 2 и 3?

    Решение:

    P3=3•(3-1)•(3-2)=3!=6.

    Ответ: 6.

Выше предполагалось, что все элементы различны. Если же некоторые элементы повторяются, то число перестановок с повторениями определяется следующей формулой.

Pn(n1,n2,n3,...,nk)=n!/(n1!•n2!•n3!•...•nk!)

Примеры:

  1. Сколько различных перестановок букв можно сделать в слове: М,А,Т,Е,М,А,Т,И,К,А?

     Решение:

     Количество букв равно 10.

     Буква М повторяется 2 раза, буква А - 3 раза, буква Т - 2 раза, буквы И и К по одному разу.

     P10(2,3,2,1,1)=10!/(2!•3!•2!•1!•1!)=3628800/(2•6•2•1•1)=151200

    Ответ: 151200.

  2. Сколько различных шестизначных чисел можно составить из цифр 1, 1, 2, 2, 2, 3?

     Решение:

     P6(1,2,3)=6!/(1!•2!•3!)=720/12=60.

    Ответ: 60.

 

 

Вам будет интересно

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

Ваш e-mail не будет опубликован.

:-[ (B) (^) (P) (@) (O) (D) :-S ;-( (C) (&) :-$ (E) (~) (K) (I) (L) (8) :-O (T) (G) (F) :-( (H) :-) (*) :-D (N) (Y) :-P (U) (W) ;-)