Знайте, Intuit, лекция, комбинаторика на дялове

Анотация: Въведение. Задачи. Различни статистики. Дървета и пермутации на п елементи. CMN Броят на комбинациите. Предизвикателства за номерата на дяловете. Комбинаторните проблеми на теорията на информацията.

Предизвикателствата, пред които ние сега смятат, че елементите са разделени на групи, както и необходимостта да се намери всички начини, по този раздел. В същото време тя може да се срещнат различни поводи. Понякога играе значителна роля в реда на елементите в групи: например, когато сигнални флагове стрелочник пост на няколко мачти, а след това е важно не само за мачта ще е това или онова знаме, но и реда, по който са окачени знамената. В други случаи, редът на елементи в групи от никакво значение. Когато играчът избира зарове домино от купчината, че няма значение в какъв ред те ще дойдат, но само крайният резултат е важен.

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

Играе роля и че се прави разлика между самите елементи, или не, както и да прави разлика дали една група, които са разпределени в елементи. Накрая, в някои проблеми, някои групи могат да бъдат празни, т.е. не съдържа никакъв елемент, и други подобни групи, които не са разрешени. В съответствие с всички по-горе, има няколко различни комбинаторни проблеми на дял.

Общият състав на тези задачи:

Задача 1. Разпределение на чекмеджета

Като се има предвид различни елементи и кутии. Необходимо е да се постави в първото поле на елементите, във втория - елементи. в та - неща, където колко начина да се направи такова разпределение?

Броят на различни оформления на същите кутии

Тази формула може да бъде получена чрез решаване на следните, на пръв поглед, доста за разлика от проблема:

Проблем 2. Пермутации с повторение.

Има различни видове обекти. Колко различни пермутации може да се направи на обекти от първия тип, на втория вид обекти. -ти тип обекти? Броят на обекти във всяка пермутация грижи. Ето защо, ако всички елементи са различни, броят на пермутации би бил равен. Но поради факта, че някои от елементите са същите, можете да получите по-малък брой пермутации. Всъщност, нека вземем, например, пермутацията

където първият писмени всички елементи от първия тип, след това всички елементи от втория вид. И накрая, всички елементи на тия тип. Елементите от първия вид, могат да бъдат разменени помежду си! начини. Но тъй като всички тези елементи са същите, такива преустройства не променят нищо. По същия начин, не променя нищо! пермутации на елементите от втория вид. ! -ти елементи пермутация тип.

Пермутации на елементите от първия тип, втория тип и така нататък може да се направи самостоятелно. Ето защо, елементи за нейното транспониране 5.1. могат да бъдат разменени помежду си! начини, така че да не се променят. Същото се отнася за всяко друго подреждане на елементите. Поради това, множеството от всички! пермутации се разпадат, състоящ се от! идентичен всяка пермутация. Следователно, броят на различни пермутации с повторения, който може да бъде съставен от елементи на данни, както и

5.2 Като се използва формулата, ние можем да отговорим на въпроса: колко пермутации може да се направи от буквите на думата "Мисисипи"? Тук имаме една буква "м", четирите букви "и" три букви "в" и буква "м", и общо 9 букви. Така, съгласно формула 5.2 броя пермутации на същото

За да се установи връзката между тези проблеми, ние се изброят всички места, които могат да ни неща. Всяка пермутация съответства на разпределението на местата в класа на стаята. Първият клас включва броя на местата, които са обекти от първия тип, а вторият - броят на местата за обекти от втори тип, и така нататък. Това се установява съответствие между пермутации с повторения и оформлението на стаи места "кутия". Ясно е, че за решаване на проблеми формулата са едни и същи.

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

Проблем 3. Знамена мачти.

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

Всеки метод за висящи флагове може да се извърши на два етапа. В първия етап ние разменят данните във всяко едно възможно знамена. Тя може да се направи! начини. След това вземете един от начините за разпространяване на мачтите на идентични знамена (брой начини). Нека този метод се състои в това, че първата мачта е необходимо да се мотае знамената на втория - знамена. на тия знамена, които след това да вземат първото знаме на последователността и виси на получените ред на първата мачта; Следните флагове са окачени върху втората мачта, и т.н. Ясно е, че с помощта на всички пермутации на знамената и всички видове дистрибуция на същите знамена на мачтите, ние откриваме всички начини за решаване на този проблем. Според правилото работи ние откриваме, че броят на начини за висящи знамена така или иначе

По принцип, ако има най-различни неща, броят на начини за разпространение на тези неща в различни кутии или иначе

Други статистика

Проблемът с оформлението на предмети върху кутиите са много важни в статистическия физика. Тази наука проучвания как разпределени на физическите свойства на частицата; например, коя част на молекулите на даден газ при дадена температура е определена скорост. В този случай, множеството от всички възможни състояния се разпределя на голям брой малки клетки (фаза щати), така че всяка от частиците попадат в една от клетките.

Въпросът за това, което статистиката са предмет на някои частици, зависи от вида на частиците. В класическата статистическа физика, създаден от Максуел и Boltzmann частици се счита различава една от друга. Тези статистически данни са предмет на, например, газови молекули. Известно е, че различни частици могат да бъдат разделени между клетките на начини. Ако всички тези методи за дадено енергия имат еднаква вероятност. тогава говорим за статистика на Максуел-Boltzmann.

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

Въпреки това, за много от частиците, като електрони, протони и неутрони не са подходящи, и статистика Bose-Einstein. За тях във всяка клетка може да се намира на не повече от една частица, различното разпределение отговаря на посоченото условие, имат еднаква вероятност. В този случай, тя може да бъде от различни дистрибуции. Тази статистика се нарича Дирак статистиката Fermi.

Дървета и пермутации на п елементи

С помощта на гората може да бъде представляван от пермутация на елементите на комплекта (набор от дефинираме: снимачната площадка - е неподреден събиране на различни предмети или структура на данните, използвани за представяне на снимачната площадка.). Да се ​​изчисли колко можете да получите пермутации. За такъв дървен материал е показана на Фиг. 5.1.

Фиг. 5.1. Различни пермутации на този модел се четат от основния връх, съответстваща на дървесината висящия. Tier показва броя на мястото, където се намира обекта. Броят на висящите върховете на гората, равен на броя на пермутации