Казват, че ключовата предпоставка за създаване на елементи от комбинаториката и теорията на вероятностите е пристрастеността на хората към лотарии, зарове, карти и други хазартни игри. Хазартът е бил от голямо значение в древността. Някои спечелиха богатства, земи, съпруги. Други загубиха всичко, което имаха, до последната тениска. Действително се осъществи влиянието на рисковите игри или произволни игри. Имаше обаче по-фундаментални причини, включително бързото развитие на науката: експерименти, необходимостта да се предвиди хода на поредица от експерименти и да се оцени грешката в резултатите. Всичко това и много повече доведоха до появата на елементи от комбинаториката и теорията на вероятностите.
Теоремата на Бернули
Смята се, че комбинаториката се е появила през 17-ти век благодарение на работата на такива учени като Кардано, Паскал, Галилей, Ферма, Лайбниц, Бернули. Именно те въведоха конкретни терминиза тази наука и доказа редица фундаментални закони и първите формули за комбинаториката. Например теоремата на Бернули, която казва, че си струва да се вземат предвид само онези експерименти и експерименти с произволност, които са независими един от друг и могат да бъдат повторени произволен брой пъти при едни и същи условия. Общоприето е, че тази теорема определя по-нататъшното развитие на комбинаториката и теорията на вероятностите като наука.
Стабилност на честотата
Преди да се обърнем към изучаването на елементите на комбинаториката, нека дадем ясен пример, който подсказва определени мисли - хвърляне на зарове. Нека разгледаме една кост за простота. Това е шестостранен куб, всяка страна на който е номерирана. Ако проведем серия от експерименти от n хвърляния и приемем, че Г1 е броят на капките на ръба с номер 1, Г2 - с номер 2 и т.н. и т.н., се оказва, че с увеличаване на броя на хвърлянията n, честотата Г1/n, Г2 /n, …, Г 6/n, които в началото на експеримента изглеждат произволни, придобиват съвсем определени стойности. И за добре балансиран зар, честотата на всеки аспект ще бъде равна с голяма точност.
Друг пример е експериментът с монети. И така, ученият Пиърсън, след като извърши 24 000 хвърляния на монета, стигна до заключението, че честотата на падане от една от страните на монетата се доближава до 0,5, колкото по-точно, толкова повече хвърляния се правят. Така той получи вероятност от 0,5005 за загуба на герба. Този принципчестотната стабилност също е една от основите на теорията.
Историческа бележка
Теорията на вероятностите и комбинаториката се развиват най-активно през 20-ти век. И огромен принос към този въпрос имаха руски и съветски математици. Сред тях, например, Колмогоров, Чебишев, Ляпунов, Марков. Те значително разширяват областите на приложимост, изследват и описват закона за големите числа, централната гранична теорема и аксиоматиката на теорията на вероятностите. Всичко това стана основа за цяла наука. Днес е трудно да се надцени значението на елементите на комбинаториката и теорията на вероятностите във физиката, химията, биологията и много други области, особено в тяхната практическа област.
Примери за проблеми с комбинаториката
Комбинаториката е оценка на броя на възможните комбинации, съставени от произволен набор от елементи, при определени условия. За целта са изведени формули в комбинаториката, които позволяват удобно и бързо решаване на искания проблем. Но преди да покажем тези формули, нека разгледаме някои примери за въпросите, довели до тях.
Задача 1. 16 отбора участват в плейофната фаза на Световното първенство. По колко начина ще могат да разпределят места помежду си? Така например:
- (3, 1, 2, 4..16) - отбор номер 3 е на първо място, отбор номер 1 е на второ място и т.н.
- (16, 1, 2, 3, 4..15) - отбор номер 16 е на първо място, …
- (1..7, 9, 8, 10..16) - на първите места на отбора 1, 2, 3, …
Това са всички примери за опции. Очевидно решение на този проблем би било да се изпишат всичкивъзможни комбинации. Това обаче ще отнеме много време, защото броят им ще бъде същият, тъй като има начини за пренареждане на 16 цифри на места. Елементите на комбинаториката решават примери като този за миг.
Проблем 2. Сред тези 16 отбора само трима могат да получат награда. По колко начина ще бъдат определени победителите? В този случай задачата се различава от предишната по това, че изобщо няма значение как изглежда класирането и какъв е редът на финалистите. Наистина, сред всички отбори е важно да се намерят само три, които ще се борят за награди помежду си. Тоест наборите могат да изглеждат като {3, 2, 1}, {5, 12, 7}, {8, 1, 2} и т.н.
Проблем 3. Ами ако поставим въпроса малко по-различно: колко начина има за разпределяне на медали за 16 отбора, участващи в плейофите? Разликата с втората задача може да не е съвсем очевидна. Сега обаче трябва да изберем не само три отбора, които ще се борят за награди, а да определим кой от тях на какво място ще заеме. С други думи, ако за втората задача, например, наборите (5, 12, 1) и (1, 12, 5) са били еквивалентни, то сега редът на командите има тежест. Наистина, в първия случай, отбор номер 5 ще получи златото, а във втория случай отбор номер 1.
По-долу ще разгледаме към кои от разделите на комбинаториката принадлежи всяка от задачите и ще опишем подробно как да ги решим. Междувременно можете да опитате да помислите сами за поставените въпроси.
Комбинации или комбинация без оглед на поръчка
Комбинация само от n-части елементинабори от k-части елементи, където k може да приема стойности от 1 до n, е всяка комбинация от k елемента, избрани от n парчета елементи. В този случай две множества ще се считат за различни, ако едно от тях съдържа елемент от n, но не принадлежи на втория. С други думи, те се различават само по състав. В елементите на комбинаториката комбинациите са въвеждащата основа.
Броят на комбинациите от n до k се обозначава с C k, от английската дума Combination. Изявленията C 1=n и C =1 са доста очевидно е, че има само n опции за избор от n елемента един по един (същият брой като самите елементи) и съответно можете да направите набор от n елемента в количество от n парчета, само един.
Така че, например, разгледайте набор от три елемента {e, 2, a}. За него C31=3: {a}, {2}, {е}; C32=3: {e, 2}, {2, a}, {a, e}; и накрая C33=1: {e, 2, a}. Припомнете си, че в този случай редът на елементите в множествата няма значение.
Какво се случва, ако се опитате да разберете какво е C 0?
Поставяне или комбинация въз основа на поръчка
Комбинаториката на разположението е достатъчно лесна за разбиране. Това са същите комбинации, само че сега се взема предвид не само съставът, но и редът във всяка комбинация. И така, като поставите n парчета елементи в комбинации (набори) от k парчета, където k може да приеме стойности от 1 до n,нарича се всяка комбинация, състояща се от k-части елементи от n, подредени в определен ред. С други думи, две комбинации за разположение са различни в три случая:
- те се различават по състав;
- те се различават по реда на елементите в наборите;
- те се различават както по състав, така и по ред.
Броят на разположенията от n до k се обозначава с A k, от Договорености. Помислете за всички опции за поставяне на набора от три елемента {x, e, z}:
- A31=3: (x), (e), (z);
- A32=6: (x, e), (e, x), (x, z), (z, x), (e, z), (z, e);
- A33=6: (x, e, z), (e, x, z), (z, x, e), (x, z, e), (e, z, x), (z, e, x).
Последният ред A33 заслужава специално внимание. Това не са нищо друго освен пермутации.
Пермутации
Както споменахме по-горе, пермутациите са доста прости по смисъл. Това са просто подреждане на n елемента, n всеки. Тоест, ние се интересуваме от всички комбинации, които се различават по реда на елементите, и само от тях. Или, еквивалентно, A . Броят на пермутациите се обозначава с буквата P, от думата Permutation. В елементите на комбинаториката пермутациите са снабдени само с един индекс. Така, например, P3=6, както разбрахме в предишната глава.
Комбинации чрез теория на множеството
Както знаете, в математиката е трудно да се общува с неопределени обекти: набор, комбинация и т.н. Би било хубавоматематически точно да определим с какво си имаме работа. Тук езикът на теорията на множествата идва полезен. Нека дефинираме какви са елементите на комбинаториката на езика на теорията на множествата.
Нека се даде някакво n-множество A={a1, a2, …, a }, съдържа n парчета елементи. Лесно е да се определи от n-множество неговото k-подмножество, където k е по-малко или равно на n. Тогава комбинации от n до k ще се наричат всички подмножества k от множеството n. Благодарение на това определение е лесно да се отговори на въпроса как ще изглежда записът C 0. Тъй като в теорията на множеството празното множество се съдържа във всяко подмножество, тогава C 0=1. С други думи, това ще бъде комбинация, която съдържа едно елемент - празен набор.
По този начин, изучавайки множеството от три елемента {c, b, a}, получаваме, че C 0 =1: { }; C31=3: {a}, {b}, {c}; C32=3: {a, b}, {b, c}, {c, a}; и накрая C33=1: {a, b, c}.
Съответно, те ще бъдат дефинирани по същия начин в комбинаториката на разположението. Единствената разлика е, че трябва да изберете подредени k-подмножества от n-множеството. И всички подмножества също ще съдържат празния набор. Условно се счита за подредена комбинация от n елемента от 0 броя, т.е. A 0=1.
Поради прехода от неясни конструкции към обекти, ясно дефинирани в теорията на множествата, се оказа доста тривиално да се отговори на едно отвъзникнали въпроси. Това е цялата математика.
Принцип на добавяне
Това е едно от двете основни правила на комбинаториката. Нека в град Москва от точка А до точка Б може да се стигне с 5 автобуса, 3 трамвая и 1 метровлак. Оказва се, че има 5 + 3 + 1=9 начина да стигнете до правилното място. Това е комбинаторният принцип на събиране.
Ако при разглеждане на проблем той може да бъде решен по n начина, докато първият от тези методи може да се приложи m1 пъти, вторият - m 2пъти и т.н., тогава този проблем ще бъде решен m1 + m2 + … + mначини.
Принцип на умножение
Сега нека си представим, че трябва да стигнете от Москва до Казан през Нижни Новгород. В същото време Москва и Нижни Новгород са свързани с 2 влака, 3 полета и 10 автомобила, а Нижни Новгород и Казан - с 1 влак, 1 полет и 2 автобуса. По принципа на добавяне стигаме до заключението, че има 13 начина да стигнете от Москва до Нижни Новгород, а от там до Казан - 4. Общият брой начини, които свързват Москва и Казан, ще бъде: 134=52.
По този начин, комбинаторният принцип на умножение гласи както следва. Ако проблемът е решен на n парчета от последователни етапи, с m1 начини на първия етап, m2 - на втория и т.н., с В този случай тези последователни етапи са независими, тоест броят на начините не се променя в зависимост от това как е взето решението на предишните етапи, тогава проблемът е решен m1 m2 …m начини. Две решения се считат за различни, ако има поне една разлика в стъпките.
Основни формули
Нека покажем формулите веднага, след това накратко опишем откъде идват и решим примерите, описани по-рано, използвайки тези елементи на комбинаториката.
Настаняване. Започваме с тази формула, тъй като други са извлечени от нея
| A k= | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1)= | n! |
| (n-k)! |
Пермутации
| P= | A = | n(n-1)(n-2)(n-3)(n-4)(n-5)…4321= | n! |
Комбинации
| C k= | A k | n(n-1)(n-2)(n-3)(n-4)(n-5)…(n-k+1) | n! |
| k! | k! | k!(n-k)! |
Доказателството на тези формули се основава на принципите на елементите на комбинаториката - правилата за събиране и умножение. Помислете за първата формула за намиране на броя на разположенията. На първия етап вземаме един от n елемента и имаме n начина да направим това. На втория етап ни остават n-1 елемента и съответно n-1 възможности за избор. На третия - n-3 начина. Продължаваме да правим това, докато в нашия набор има k парчета елементи. Според правилото за умножение ще стигнем до факта, че общо има n (n-1) (n-2) (n-3) (n-4) (n-5) … (n-k + 1) начини за избор на k елементи. Втората формула за намиране на пермутации е просто следствие от първата.брой замествания m=k. Последната формула, която дава броя на комбинациите, се получава от съображенията, че при търсене на комбинации от n елемента, k парчета всеки път, когато стигнем до k! подреждания от n до k (те се получават като пермутации на k елементи). Следователно имаме A k=C kk!.
Сега можем да се върнем към задачите, които бяха обявени по-рано, и да оценим броя на опциите. За първия проблем трябва да използваме формулата за пермутация, т.е. P16=16!=20 922 789 888 000 ≈ 211012 възможни опции за това как 16 отбора могат да бъдат поставени в класирането. Вторият проблем се отнася до комбинации, което означава C163=16! / [3!(16-3)!]=560 победители. И накрая, последният проблем се отнася до разположенията, т.е. A163=16! / (16-3)!=3360 начина как 3 отбора от 16 могат да споделят наградите.
Предвид горното е излишно да говорим за това как работи комбинаториката на големи числа.
