Тази статия ще се фокусира върху специален раздел от математиката, наречен комбинаторика. Формули, правила, примери за решаване на проблеми - всичко това можете да намерите тук, като прочетете статията до самия край.
И така, какъв е този раздел? Комбинаториката се занимава с въпроса за преброяването на всякакви обекти. Но в този случай обектите не са сливи, круши или ябълки, а нещо друго. Комбинаториката ни помага да намерим вероятността за събитие. Например, когато играете на карти, каква е вероятността противникът да има коз? Или такъв пример - каква е вероятността да получите точно бяло от торба с двадесет топки? Именно за този вид задачи трябва да знаем поне основите на този раздел от математиката.
Комбинаторни конфигурации
Разглеждайки въпроса за основните понятия и формули на комбинаториката, не можем да не обърнем внимание на комбинаторните конфигурации. Използват се не само за формулиране, но и за решаване на различни комбинаторни задачи. Примери за такива модели са:
- разположение;
- пермутация;
- комбинация;
- числова композиция;
- разделено число.
Ще говорим за първите три по-подробно по-късно, но ще обърнем внимание на композицията и разделянето в този раздел. Когато говорят за състава на определено число (да речем, а), те имат предвид представянето на числото а като подредена сума от някои положителни числа. А разделянето е неподредена сума.
Раздели
Преди да преминем директно към формулите на комбинаториката и разглеждането на проблемите, си струва да обърнем внимание на факта, че комбинаториката, подобно на други раздели на математиката, има свои собствени подраздели. Те включват:
- изброяване;
- структурно;
- екстремно;
- теория на Рамзи;
- вероятност;
- топологичен;
- безкрайно.
В първия случай говорим за изброяваща комбинаторика, проблемите разглеждат изброяването или броенето на различни конфигурации, които се формират от елементи на множества. По правило върху тези набори се налагат някои ограничения (различимост, неразличимост, възможност за повторение и т.н.). И броят на тези конфигурации се изчислява с помощта на правилото за събиране или умножение, за което ще говорим малко по-късно. Структурната комбинаторика включва теориите на графиките и матроидите. Пример за проблем с екстремална комбинаторика е кое е най-голямото измерение на графика, което удовлетворява следните свойства… В четвъртия параграф споменахме теорията на Рамзи, която изучава наличието на регулярни структури в произволни конфигурации. Вероятностникомбинаториката е в състояние да отговори на въпроса - каква е вероятността дадено множество да има определено свойство. Както може би се досещате, топологичната комбинаторика прилага методи в топологията. И накрая, седмата точка - безкрайната комбинаторика изучава прилагането на методите на комбинаториката към безкрайни множества.
Правило за добавяне
Сред формулите на комбинаториката могат да се намерят доста прости, с които сме познати отдавна. Пример е правилото за сумата. Да предположим, че са ни дадени две действия (C и E), ако те се изключват взаимно, действие C може да се извърши по няколко начина (например a), а действие E може да се извърши по b-начини, тогава всяко от тях (C или E) може да се направи по a + b начини.
На теория това е доста трудно за разбиране, ще се опитаме да предадем цялата идея с прост пример. Да вземем средния брой ученици в един клас – да кажем, че е двадесет и пет. Сред тях има петнадесет момичета и десет момчета. Всеки ден в класа се назначава един придружител. Колко начина има за назначаване на придружител днес? Решението на проблема е доста просто, ще прибегнем до правилото за добавяне. В текста на задачата не пише, че само момчета или само момичета могат да дежурят. Следователно може да бъде някое от петнадесетте момичета или някое от десетте момчета. Прилагайки правилото за сумата, получаваме доста прост пример, с който ученик от началното училище лесно може да се справи: 15 + 10. След като изчислихме, получаваме отговора: двадесет и пет. Тоест има само двадесет и пет начиназадайте дежурен клас за днес.
Правило за умножение
Правилото за умножение също принадлежи към основните формули на комбинаториката. Да започнем с теорията. Да предположим, че трябва да извършим няколко действия (а): първото действие се извършва по 1 начина, второто - по 2 начина, третото - по 3 начина и така нататък, докато последното a-действие се изпълнява по sa начини. Тогава всички тези действия (от които имаме общо) могат да бъдат извършени по N начина. Как да изчислим неизвестното N? Формулата ще ни помогне с това: N \u003d c1c2c3…ca.
Отново нищо не е ясно на теория, нека да преминем към прост пример за прилагане на правилото за умножение. Да вземем същия клас от двадесет и пет човека, в който учат петнадесет момичета и десет момчета. Само този път трябва да изберем двама придружители. Те могат да бъдат или само момчета или момичета, или момче с момиче. Обръщаме се към елементарното решение на проблема. Избираме първия придружител, както решихме в последния параграф, получаваме двадесет и пет възможни варианта. Вторият дежурен може да бъде всеки от останалите хора. Имахме двадесет и пет ученика, избрахме един, което означава, че всеки от останалите двадесет и четири човека може да бъде вторият дежурен. Накрая прилагаме правилото за умножение и установяваме, че двамата придружители могат да бъдат избрани по шестстотин начина. Получаваме това число, като умножим двадесет и пет и двадесет и четири.
Размяна
Сега ще разгледаме още една формула за комбинаторика. В този раздел на статията ниеДа поговорим за пермутациите. Разгледайте проблема веднага с пример. Да вземем билярдни топки, имаме n-ти брой от тях. Трябва да изчислим: колко опции има да ги подредим в един ред, тоест да направим подреден набор.
Нека започнем, ако нямаме топки, тогава също имаме нулеви опции за поставяне. И ако имаме една топка, тогава подредбата също е същата (математически това може да се запише по следния начин: Р1=1). Две топки могат да бъдат подредени по два различни начина: 1, 2 и 2, 1. Следователно Р2=2. Три топки могат да бъдат подредени по шест начина (Р3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. А ако няма три такива топки, а десет или петнадесет? Изброяването на всички възможни опции е много дълго, тогава на помощ ни идва комбинаториката. Формулата за пермутация ще ни помогне да намерим отговора на нашия въпрос. Pn=nP(n-1). Ако се опитаме да опростим формулата, получаваме: Pn=n (n - 1) … 21. И това е произведението на първите естествени числа. Такова число се нарича факториал и се обозначава като n!
Нека разгледаме проблема. Водачът всяка сутрин изгражда своя отряд в редица (двадесет души). В отряда има трима най-добри приятели - Костя, Саша и Леша. Каква е вероятността те да бъдат един до друг? За да намерите отговора на въпроса, трябва да разделите вероятността за „добър“резултат на общия брой резултати. Общият брой на пермутациите е 20!=2,5 квинтилона. Как да преброим броя на "добрите" резултати? Да предположим, че Костя, Саша и Леша са един супермен. Тогава ниеИмаме само осемнадесет предмета. Броят на пермутациите в този случай е 18=6,5 квадрилиона. С всичко това Костя, Саша и Леша могат произволно да се движат помежду си в своята неделима тройка, а това са още 3!=6 опции. Така че имаме общо 18 „добри“съзвездия!3! Просто трябва да намерим желаната вероятност: (18!3!) / 20! Което е приблизително 0,016. Ако се преобразува в процент, се оказва само 1,6%.
Настаняване
Сега ще разгледаме друга много важна и необходима комбинаторика. Настаняването е следващият ни въпрос, който ви предлагаме да разгледате в този раздел на статията. Ще станем по-сложни. Да приемем, че искаме да разгледаме възможни пермутации, само че не от цялото множество (n), а от по-малко (m). Тоест, ние разглеждаме пермутации на n елемента с m.
Основните формули на комбинаториката трябва не просто да се запомнят, но и да се разбират. Дори въпреки факта, че те стават по-сложни, тъй като имаме не един параметър, а два. Да предположим, че m=1, след това A=1, m=2, след това A=n(n - 1). Ако допълнително опростим формулата и преминем към нотация, използвайки факториали, получаваме доста кратка формула: A \u003d n! / (n - m)!
Комбинация
Разгледахме почти всички основни формули на комбинаториката с примери. Сега нека преминем към последния етап от разглеждането на основния курс на комбинаториката – запознаване с комбинацията. Сега ще изберем m елемента от n, които имаме, докато ще изберем всички от тях по всички възможни начини. Как тогава това е различно от настаняването? Ние нямапомислете за реда. Този неподреден набор ще бъде комбинация.
Незабавно въведете обозначението: C. Ние вземаме разположения на m топки от n. Спираме да обръщаме внимание на реда и получаваме повтарящи се комбинации. За да получим броя на комбинациите, трябва да разделим броя на разположенията на m! (m факториал). Тоест C \u003d A / m! По този начин има няколко начина да избирате от n топки, приблизително равни на колко да изберете почти всичко. Има логичен израз за това: да избереш малко е същото като да изхвърлиш почти всичко. Също така е важно да се спомене в този момент, че максималният брой комбинации може да се постигне, когато се опитвате да изберете половината от елементите.
Как да изберем формула за решаване на проблем?
Разгледахме подробно основните формули на комбинаториката: поставяне, пермутация и комбинация. Сега нашата задача е да улесним избора на необходимата формула за решаване на задачата в комбинаториката. Можете да използвате следната доста проста схема:
- Запитайте се: взет ли е предвид редът на елементите в текста на проблема?
- Ако отговорът е не, тогава използвайте формулата за комбинация (C=n! / (m!(n - m)!)).
- Ако отговорът е не, тогава трябва да отговорите на още един въпрос: всички елементи ли са включени в комбинацията?
- Ако отговорът е да, тогава използвайте формулата за пермутация (P=n!).
- Ако отговорът е не, тогава използвайте формулата за разпределение (A=n! / (n - m)!).
Пример
Разгледахме елементите на комбинаториката, формулите и някои други въпроси. Сега да преминем къмкато се има предвид реален проблем. Представете си, че имате киви, портокал и банан пред себе си.
Въпрос първи: по колко начина могат да бъдат пренаредени? За да направим това, използваме формулата за пермутация: P=3!=6 начина.
Въпрос втори: по колко начина може да бъде избран един плод? Това е очевидно, имаме само три опции - изберете киви, портокал или банан, но прилагаме формулата на комбинацията: C \u003d 3! / (2!1!)=3.
Въпрос трети: по колко начина могат да бъдат избрани два плода? Какви опции имаме? Киви и портокал; киви и банан; портокал и банан. Тоест три опции, но това е лесно да се провери с помощта на комбинираната формула: C \u003d 3! / (1!2!)=3
Въпрос четири: по колко начина могат да бъдат избрани три плода? Както можете да видите, има само един начин да изберете три плода: вземете киви, портокал и банан. C=3! / (0!3!)=1.
Въпрос пет: по колко начина можете да изберете поне един плод? Това условие предполага, че можем да вземем един, два или трите плода. Следователно добавяме C1 + C2 + C3=3 + 3 + 1=7. Тоест имаме седем начина да вземем поне едно парче плод от масата.
