Пермутация

от Уикипедия, свободната енциклопедия

Направо към: навигация, търсене

Пермутация се нарича всяка подредена съвкупност от n естествени числа, в която дадено число да се среща само веднъж.

Съдържание

[редактиране] Дефиниция

Пермутация на n елемента наричаме произволна тяхна наредба, в която всеки един от тези елементи се среща само веднъж. Броят на възможните различни наредби (пермутации) е n!=1.2.3...n.


Всяко подреждане на дадени различни елементи се нарича пермутация (пермутация без повторение) на тези елементи. В дадена пермутация на елементи всеки елемент участва точно веднъж и мястото му в пермутацията е съществено.

[редактиране] Представяне

Нека са дадени n различни елемента a1,a2,...,an. Те могат да бъдат подредени по различни начини. Всяко подреждане на елементите a1,a2,...,an се нарича пермутация на n елемента. Броят на всички възможни пермутации от n елемента се бележи с Pn. Pn = n! (n факториел)

[редактиране] Примери

Типичен пример за пермутация е размесването на карти за игра. Всяка една нова подредба е пермутация на началната.

Друг пример е разместването на буквите в дадена дума, напр. воал -> овал.

Пермутациите се делят на два вида: четни и нечетни. Пермутацията е четна, когато има четен брой инверсии, а нечетна-има нечетен брой инверсии.

Пример:

P1 = 1!P2 = 1.2 = 2!P3 = 1.2.3 = 3!Pn = n!Pn + 1 = n!(n + 1) = (n + 1)!

[редактиране] Свойства

Лични инструменти