Комбинаторика

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

Комбинаториката е сред най-старите и силно развити дялове на математиката и по-специално на дискретната математика. Основен обект, с който се занимава комбинаториката е комбинаторната конфигурация. В областта на комбинаториакта са се оформили две проблеми области: изброителна комбинаторика и структурна комбинаторика.

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

Пермутация без повторение наричаме конфигурация, от n-елементно множество трябва да изберем всичките n елемента, като реда е от значение. Броят на конфигурациите е n! (ен факториел). n! има стойност n*(n-1)*(n-2)*...*3*2*1. Прост пример за една комбинаторна задача е "По колко начина може да се нареди едно тест от 52 карти?". Отговорът е 52!

[редактиране] Изборителна комбинаторика

Основен проблем на изброителната комбинаторика е по зададено множество и рпавила за комбиниране, да се намери броя на получаващите се комбинаторни конфигурации. Разглеждат правила, при които комбинаторните кнофигурации да бъдат краен брой.


[редактиране] Принципи на изброителната комбинаторика

Принцип на чекмеджетата (принцип на Дирихле) Нека Х е множество с к елемента (които ше наричаме предмети), а У е множество от р елемента (които ще наричаме чекмеджета и к > р. Както и да поставим всички предмети в чекмеджетата, поне в едно чекмедже ще има поне два предмета.

Принцип на биекцията Нека Х и У са крайни множества, |X| = k и |Y| = р. Съществува биекция f: X->Y, тогава и само тогава, когато к = р.