Предмет. Основни понятия на комбинаториката

Комбинаториката е дял от математиката, посветен на решаването на проблеми с избора и подреждането на елементи от някои, обикновено крайни, набори в съответствие с дадени правила.

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

Най-простите примери за комбинаторни конфигурации сапермутации, разположения, комбинации и разделяния.

При броене на комбинаторни конфигурации се използват правилата за сума и произведение.

Правило за сумиране. Ако обект A може да бъде избран по m начина, а обект B по други n начина, тогава изборът „или A, или B“ може да бъде направен по m + n начина.

Правило за продукта. Ако обект A може да бъде избран по m начина и след всеки от тези избори, обект B на свой ред може да бъде избран по n начина, тогава изборът на „A и B“ в този ред може да бъде направен по mn начина.

По своята същност тези правила садефиниции и трябва да бъдатразбрани, а недоказани. Трябва да се отбележи, че в първото правило изборите A и B са взаимно изключващи се, т.е. няма начин да изберете двата обекта едновременно (по един и същи начин).

Правилото за продукта най-често се използва в случаите, когато редът на избор не е значим, т.е. когато изборите А и Б са независими. Не бива обаче да се пренебрегва възможността за такава зависимост.

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

Броят на всички пермутации отn елемента е равно на произведението на последователни естествени числа от 1 до n включително, т.е.

=1 (1)

където n! - се чете “n факториал” (от латински фактор - множител).

Пример:

Помислете за пермутация на три числа: 1, 2, 3. От тези три числа могат да бъдат направени само 3! = 6 пермутации: 123, 132, 321, 312, 231, 213.

При първата пермутация всички числа са в естествен ред, а при останалите пермутации този ред е нарушен. Например при пермутация 312 числото 3 е както пред 1, така и пред 2. Това явление, когато по-голямо число е пред по-малко, се наричаразстройство илиинверсия. По-специално, пермутация 132 има една инверсия, пермутация 312 има две инверсии, а пермутация 321 има три инверсии и т.н.

Пример: Пребройте броя на инверсиите в пермутация 531642.

Решение: Започваме с броенето на числата пред 1 - има две от тях (5 и 3). Задраскваме 1. Пред 2 има четири числа (5, 3, 6 и 4). Задраскваме 2. Пред 3 е едно число (5). Задраскваме 3. Пред 4 има две числа (5, 6). Задраскваме 4. Пред 5 няма нищо. Задраскваме 5. И накрая, пред 6 също е безполезно (зачертайте всичко).

Следователно желаното число чрез инверсия е 2+4+1+2=9.

Операцията за преместване на два елемента в дадена пермутация се наричатранспониране.

Всички пермутации на n числа 1, 2, 3, ..., n могат да бъдат разделени на два класа. Една пермутация се наричачетна (или от четен клас), ако броят на нейните инверсии е четен, и нечетна (от нечетен клас) в противен случай.

Например, пермутация 231 е четна, защото има две инверсии. Но ако приложим към него транспозицията (2, 3), тогава получаваме пермутацията 321 с три инверсии, т.е. нечетна пермутация.

Теорема: Четността на една пермутация се променя от едно транспониране.

От теоремата следва.

1. За да преминете от една пермутация към друга от същия клас, трябва да се извършат четен брой транспозиции. Напротив, за да преминете от една пермутация към друга от противоположния клас, трябва да извършите нечетен брой транспозиции.

2. От n числа 1, 2, …, n могат да се направят четни пермутации и същия брой нечетни пермутации.

Заместване на n елемента

(*)

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

Заместването обикновено се обозначава със символа

( 2 )

Ако вземем предвид само номерата на елементите, тогава нотацията на заместването ( 2 ) е опростена

( 3 )

Очевидно различните пермутации на n числа трябва да имат различни пермутации в долния ред ( 3 ). От това следва, че броят на пермутациите от n-та степен (т.е. пермутациите на n числа) е равен на броя на пермутациите на n числа, т.е. е равно на n!.

Пермутация на n-та степен се наричачетна, ако долният ред на нейния запис ( 3 ) образува четна пермутация, инечетна, ако този ред образува нечетна пермутация.

Как да определим паритета на пермутация от n-та степен, ако е написана като

( 4 )

Нека , където S е броят на инверсиите в горния ред, а t е броят на инверсиите в долния ред на записа (4) на заместването S.

Може да се покаже, че пермутацията S е четна, когато е четно число, и нечетна, когато е нечетно число.

Нека две пермутации на числата 1, 2, 3, 4

Нека да видим какво се случва, ако първо извършим заместването

Заместването замества 1 с 4 и- 4 с 3. Така числото 1 се влияе от две замествания и се заменя с числото 3. Следващото число 2 се заменя със заместване с 1, а 1 се заменя със заместване с 2. Така че 2 е под съвместно влияние и влиза в 2. Накрая 4 е под съвместно влияние и влиза в 4. Резултатът е заместване

Кой от тях произвежда същото действие, това са и двете замествания и , извършени последователно едно след друго.

Продуктът от замествания S и T от n числа 1, 2, ..., n е такова трето заместване от същите числа, което само по себе си изпълнява същия ефект като двете замествания S и T, извършени последователно едно след друго. Продуктът на заместванията се означава като = ST.

Може да се покаже, че не винаги ST = TS.

,

Сред всички възможни пермутации на числата 1, 2, …, n има едно така нареченоидентично илиединично заместване

,

което при умножаване на пермутации се държи подобно на числото 1 при аритметично умножение, а именно: за всяка пермутация

важи равенството SJ = JS = S.

За всяко заместване S винаги съществува обратно заместване, характеризиращо равенството

S=S=J.

Където .

Умножението на пермутации от 1, 2, ..., n се подчинява на закона за комбиниране

Заместване S на числата 1, 2, …, n се наричаk - наречено циклично илиk - наречено цикъл, ако се превежда до число, различно от , - до число, различно от , ..., - до число, различно от , и - до оригиналното число ( k u ), и други числа ( k

---