Алексеев-Дискретна математика-2 - Страница 2
Едно от следствията на бинома на Нютон (свойство 7 от предишната лекция) казва, че
Пример е проблемът с бунтовете. Нека = (1, 2, …,) е пермутация на елементи. Ако = за някои , тогава елементът се нарича пермутационна фиксирана точка. Пермутация, която няма фиксирани точки, се нарича разстройство. С други думи, в безпорядъка нито един елемент не стои на мястото си. Броят на смущенията между елементите ще бъде означен с . Лесно е да се провери например, че има точно две смущения на три елемента: (2,3,1) и (3,1,2), така че 3 = 2 . Нека приложим метода на включване-изключване, за да преброим броя на смущенията за произволно .
Означаваме с набор от всички такива пермутации на елементи, за които е фиксирана точка. Тогава 1 2 … е множеството от всички пермутации, които имат фиксирани точки. Защото има всичко! пермутации на елементи, тогава
За да изчислим мощността на обединението на множествата, използваме формулата за включване-изключване:
, , … , . Всяка такава пресечка
се състои от всички
неподвижен. Броят на
пермутации е равен на броя на пермутациите на останалите − елементи,
членове в тази сума е равен на броя на -елементните подмножества на набора от
елементи, т.е
и получете формулата за броя на смущенията:
= ! − 1! ! +2! ! − + (−1) ! ! = ! ( 1 − 1! 1 + 2! 1 − + (−1) 1 ! ) .
3.13. Неподредени дялове
Като друго приложение на метода за включване-изключване, ние извеждаме формула за броя на неподредените дялове.
На пръв поглед неподредените и подредените дялове са свързани помежду си по същия начин като комбинациите с разположения. От всяка комбинация от po, подреждайки нейните елементи по различни начини, можете да получите !разположения от до . Това е основата за извеждането на формулата за броя на комбинациите:
знаем броя на разположенията и знаем, че има! пъти повече от комбинациите. Може ли тази техника да се използва за преброяване на броя на неподредените дялове? Знаем, че броят на подредените разделяния на набор от елементи на части е . Всеки подреден дял се получава от неподреден чрез подреждане на частите му в определен ред. На разположение! начини за подреждане на части. Не е ли?
Не, не е и това се вижда от следния пример. Помислете за разделянето на набор от 5 елемента на 4 части:
Първата и четвъртата част са еднакви и когато се разменят, се получава еднакво подреден дял. Следователно, като пренаредите частите на този дял, можете да получите повече от 4! = 24, но само 12 различни подредени дяла.
Ясно е, че в този пример целият смисъл е, че има две еднакви части. Също така е ясно, че само празните части могат да бъдат еднакви. Ако намерим броя на подредените дялове на набор от елементи на непразни части, тогава за да изчислим броя на неподредените дялове, ще бъде достатъчно да разделим този резултат на ! .
Задача. Колко подредени разделяния на множество от елементи на непразни части има?