Тема 2. Елементи на комбинаторика
Цели и задачи на темата на изследването
Тази тема обхваща основите на комбинаторика и алгоритми за генериране на комбинаторни обекти.
Комбинаторика - един от разделите на дискретна математика, който е придобил голямо значение поради използването му в теорията на вероятностите, математическата логика, теория на числата, компютърни науки, кибернетиката.
Тук е най-простият пример за комбинаторна проблем. Нека град А до град Б, можете да стигнете с лодка, влак, автобус, самолет; от B до град C - с лодка и автобус. Колко начини може да се направи по пътя от A - B - C?
Решение. Очевидно е, че броят на различните пътеки от А до С е 4 х 2 = 8, така че, за избиране на една от четирите възможни начини за пътуване от А до В, имаме две възможни начини за пътуване от В до С
Въз основа на тези съображения, основното правило формулира комбинаторна - обикновено работи.
Правило работи. Ако някои диапазон А може да се извършва чрез методи, m, и за всеки един от тези методи, друг избор може да се осъществи В п начини, изборът на "А и Б" в този ред може да се проведе m х п начини.
Това правило може да се обобщи по следния начин.
Да предположим, че искате да извършите една след друга действията к. Ако първото действие да се извърши n1 начини, вторият акт - n2 начини, третият начин - N3 начини, и така нататък, докато к-то действие, което може да се извърши NK начини, всички к действия могат да бъдат изпълнени n1 × n2 × n3 × ... × NK начини.
Когато броенето се използва също и броят на различните комбинации обикновено възлиза.
Член сума. Ако някои диапазон А може да се проведе съм методите и избор B п други начини, изборът на "или или А. В" може да се осъществи m + п начини.
правило сума може да се обобщи и да е брой действия.
В razd.1.1.1 тя бе дадена на концепцията за комплект. Ограничен набор S ще бъде дадено от списък на нейните елементи: S = s1, s2, ..., SN>, където s1, s2, ..., SN - елементи S (непременно важно).
Представяме на концепцията за MultiSet. MultiSet обединение на не непременно различни обекти. Това може да се счита комплект, в който всеки елемент се определя положително цяло число, наречено множество.
Крайните MultiSet S ще бъдат записани в следния вид:
Тук всичко е различно и си ки - кратност си елемент. Тогава мощност S е.
А сега да разгледаме някои от комбинаторни обекти.
Подмножества. Зададената М е подмножество на набор S (наименование М ÌS или S ÉМ; М се чете влиза в S, S съдържа М), ако и само ако всеки елемент от множеството М принадлежи на набора S.
Теорема. Броят на подгрупи н елемент в комплект S равни на 2 п.
Доказателство. Задаваме на всяка съвкупност от набор S M двоичен набор от дължината н със следното правило: SI ÎМ. единствено и само ако -тата бит е равен на единица. Броят на бинарни вектори с дължина п. според правило работи, е 2 × 2 × ... × 2 = 2 п. Следователно, броят на всички подгрупи елемент в определен п равно на 2 п.
Комбинации. Пермутации се нарича разположението на елементите на снимачната площадка в определен ред.
Теорема. N броя пермутации т.е. елемент в определен S. броят на начини за организиране на дадена от Рп = п !.
Символ п. (Вижте -faktorial п) означава продукта от естествени числа от 1 до п :! N = 1 х 2 х. Х п. Смята се, че 0! = 1.
Доказателство. Ние последователно изберете елементи от набор S и да ги подредите в определен ред н за областта. На първо място, можете да сложите някоя от п елементи. След напълване на първо място на второ място може да постави всеки от останалите N -1 елементи, и т.н. След това правило работи на всички п места могат да попълнят н × (п-1) × (Н -2) х. Х 2 х 1 = N. начини. Track-ствие, н-елемент комплект могат да бъдат рационализирани н! Начини.
Поставянето. Подреден к елемент в подмножество на множеството от п елементи наречен поставянето на п елементи на к.
Теорема. Брой на режима на п к се определя от формулата:
.
Доказателство. Ние последователно ще избере к- елементи на п елемент в комплект, и да ги подредите в определен ред, за да к места. На първо място могат да бъдат поставени или на п елементи, тогава вторият - или п -1ostavshihsya т.н. Чрез върховенството на про-поведение оказват
.
Комбинации. Комбинация от елементи к п к елемент в наречен подгрупа от п елементи.
Теорема. Броят на комбинации от п елементи се експресира от к-писта железопътна формула:
.
Доказателство. От елемент в масива от п могат да образуват различни нареди к елемент в подгрупи. Всеки елемент к подгрупа може да се поръча Пк начини. След това броят на комбинациите от п от к - броят на неподреден к-елемент подгрупи на п елемент в предвидено да бъде равно на
.
За броя на комбинациите от равенства
,
,
.
Последният имота следва от теоремата за броя на подгрупи на ограничен набор (обясни защо).
Пермутации с повторения. Пермутации с повторения се нарича оформление multisets в определен ред.
Теорема. Броят на пермутации с повторения за multisets изразени с формула
,
Доказателство 1. Помислете пермутация на MultiSet и да го замените всички едни и същи елементи са различни. След това, броят на различните пермутации, който може да бъде съставен от разглеждания пермутация добре k1! × k2! × ... × км !. Направете това за всяка пермутация, ние получаваме п. пермутации. Ето защо,
Броят Cn (k1, k2, ..., км), се нарича полином коефициент. Ето още едно доказателство за това теорема.
Доказателство 2. За организиране на необходимата MultiSet от п места, за да изберете К1 места на S1 елемент, който може да бъде направено по начин, а след това на п -k1 останалите места да избират K2 места за s2 елемент. начини, по които може да се направи, и т.н. Тогава броят на начини за организиране на MultiSet S от правилото работи по същия начин (Припомняме, че 0! = 1)
.
Комбинации с повторение. Комбинации от м елементи от п елементи, наречени повторения групи с п елементи, като всеки елемент принадлежи към един от видовете м.
Пример. От трите елемента (т = 3). б. С можете да направите такава комбинация от двете с повторения: AA. аб. Ал. бб. преди новата ера. сс.
Теорема. Броят на различни комбинации от елементи м равно на п повторения с
.
Доказателство. Всяка комбинация е напълно определено, ако зададени колко елементи на всеки от типовете м включени в него. С всеки комбиниране последователност от нули и единици, съставени от правилото, като ред блокове, като елементи от първия вид е включен в комбинацията, след определен нула, и след много запис единици, колко елементи от втория тип се състои от комбинация и т.н. , Например, горните писмени комбинации от три букви ще съответстват на две такива последователности:
1100, 1010, 1001, 0110, 0101, 0011.
По този начин, всяка комбинация от х п съответства на последователност на N единици, и m -1 нули. Броят на последователности, равен на броя на начина за избор m -1 поставя нули на п + m -1 общо места (), или същия брой п поставя методи за подбор на единици п + m -1mest (). Равенство следва от уравнението.
Съставите и дяла. Нека задачата за генериране на дялове на положително число п на последователност от числа Р1, Р2, ..., РК>, така че Р1 + Р2 + ... + пк = п и пи могат да бъдат наложени на различни ограничения.
Ако реда на номерата Pi е важно, тогава (Р1, Р2, ..., п.к.) се нарича състав п. Търсене на песни се ограничават пи> 0.
Ако к се фиксира, след това такъв състав се нарича състав п к части. Когато търсенето ограничение пи> 0 може да бъде отстранена, т.е. оставя пи = 0.
Нека обясним разликата между състава, съставът на единици К и дяловете в следния пример:
състав (3), (1,2), (2,1), (1,1,1)
състава на двете части (пи> 0): (1,2), (2,1),
състава на двете части (пи ³0): (0,3), (1,2), (2,1), (3,0),
Теорема. Брой на песните п е 2 п -1.
Доказателство. Разделете сегмент с дължина п на п части на единица дължина се използва (N -1) точка. Тогава п взаимно състав съответства еднозначно маркиране някои от точките за разделяне. Елементи-трет състав в този случай ще е разстоянието между съседни точки. Например, съставът (2,2,1), п = 5 е показан на Фигура 2.1.
Следователно, всеки състав п съответства на метод за избиране на подгрупа (п-1) пиксела. Това означава, че броят на песни п е 2 п-1.
Теорема. Брой на песните п к парчета ограничен пи> 0 равни.
Доказателство. Ние представляваме състава, както и доказателство за предишната теорема. Всеки състав на парчета п к (пи> 0) съответства на метода на селекция (к-1) - елемент подгрупи на точки п -1 точки. Това означава, че броят на тези състави, са еднакви.
Теорема. N брой песни от к парчета ако пи ³0 грижи.
Доказателство. Всеки състав на п компоненти а к пи ³0 едно съответствие между двоичен набор, така че първият термин е равен на броя на единиците пред първата нула в комплекта, а вторият - на броя единици пред първата и втората нули и т.н. Един пример за това представителни състави, п = 4, к = 3 е даден в Таблица 2.1.
набор дължина е п + к -1, броят на нули е равна к -1 следователно броят на комплекта (на желаните състави) е броят на начини к -1 поставя нули избор за п + K -1 места () или същия брой начини за избора п места за единици п + к -1mest ().
Илюстрация на теоремата на броя на състави от п к части
Свързани статии