Основни формули на комбинаторни. Комбинаторика: формулата за пермутация, разположение

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

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

Комбинаторни конфигурации

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

• настаняване;
• пермутация;
• комбинация;
• състав на числото;
• разделяне на номера.

За първите три ще говорим по-подробно по-късно, но ще обърнем внимание на композициите и разделянето в този раздел. Когато говорим за състав от определен брой (да речем а), тогава имаме предвид представянето на числото a под формата на наредена сума от определени положителни числа. Разделянето е неопределено количество.

Секции

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

• изброяване;
• структурен;
• крайност;
• Теорията на Рамзи;
• вероятност;
• топологични;
• infinitary.

В първия случай става дума за изброяване комбинаторика на проблема обмислят брой или изброяване на различни конфигурации, които се формират от елементи на декорите. В набора от данни, обикновено наложени никакви ограничения (разграничимостта, неразличимост, възможността за повторение и така нататък). Някои от тези конфигурации са изчислени въз основа на правилата за събиране и умножение, които ние ще обсъдим по-късно. За структурни комбинаторика включва графика теория и matroids. Един пример за проблема с екстремни комбинаторика - това, което е най-големият размер на графиката, която отговаря на следното svoystvamhellip- В четвъртия параграф споменахме теорията на Рамзи, който изучава в присъствието на случайни конфигурации на редовните структури. Вероятностни комбинаторика състояние нас, за да се отговори на въпроса - Каква е вероятността, че дадена група има специфично свойство. Както можете да предположите, топологичните комбинаторика прилага методи в топология. И накрая, на седмия точка - infinitary комбинаторика комбинаторика се учат на използването на методи към определя безкраен.

Правило за добавяне

Сред комбинаторика формули могат да се намерят доста прости, с които отдавна са запознати достатъчно. Пример за това е правилото за сума. Да предположим, че са ни дадени два етапа (С и Е), ако те са взаимно изключващи се, в сила от изпълним по няколко начина (например), както и ефекта на E изпълним б-начини, за да се съобразят с нито един от тях (С или E), могат да бъдат А + В начини ,

На теория това е трудно за разбиране, опитваме се да предадем цялата точка на един прост пример. Нека вземем средния брой ученици от един клас - да речем, двадесет и пет. Сред тях са петнадесет момичета и десет момчета. Всеки ден в класа се назначава едно дежурно лице. Колко начина да се назначи служител на длъжността днес? Решаването на проблема е съвсем проста, прибягваме до правилото за добавяне. Текстът на проблема не казва, че само момчета или момичета могат да бъдат на служба. Следователно те могат да бъдат всеки от петнадесет момичета или някое от десетте момчета. Прилагайки сумата на правилото, получаваме сравнително прост пример, с който студентът от началното училище може лесно да се справи: 15 + 10. След като броим, получаваме отговора: двадесет и пет. Това означава, че има само двайсет и пет начина за назначаване на длъжност за днес.

Правилото за умножение

Правилото за умножение важи за основните формули на комбинираното. Нека да започнем с теорията. Например, трябва да извършим няколко действия (а): първото действие се изпълнява по 1 начин, вторият по c2 начини, третият с c3 методи и т.н., докато последното действие е извършено по същия начин. Тогава всички тези действия (които всички ние имаме) могат да бъдат извършени по N пъти. Как да се изчисли неизвестния N? В това ние ще ни помогнат с формулата: N = c1 * c2 * c3 * hellip- * sa.

Отново, на теория нищо не е ясно, ние се обръщаме към един прост пример за прилагането на правилото за умножение. Да вземем същия клас от двадесет и пет души, в който се учат петнадесет момичета и десет момчета. Само този път трябва да изберем двама души на дежурство. Те могат да бъдат веднага след като момчета или момичета, и едно момче с момиче. Продължаваме към елементарното решение на проблема. Избираме първия дежурен човек, както решихме в последния параграф, получаваме двадесет и пет възможни варианта. Второто дежурно лице може да бъде всеки от останалите хора. Имахме двайсет и пет студенти, избрахме, така че второто дежурно лице би могло да бъде всеки от останалите двадесет и четирима души. Накрая прилагаме правилото за умножение и откриваме, че двама дежурни служители могат да бъдат избрани в шестстотин начина. Ние умножихме този брой на двадесет и пет и двадесет и четири.

пермутация

Сега ще разгледаме още една комбинация от комбинации. В тази секция на статията ще говорим за пермутации. Помислете веднага за проблема с пример. Вземете билярдни топки и ние имаме n-то число. Трябва да изчислим: колко опции има, за да ги подреждате в ред, т.е. да съставите подреден набор.

Нека започнем, ако нямаме топки, тогава имаме същите варианти на споразумението като нула. И ако имаме една топка, тогава подредбата е същата (математически това може да бъде написано както следва: P1 = 1). Две топки могат да бъдат поставени по два различни начина: 1,2 и 2,1. Следователно P2 = 2. Три сфери могат да бъдат подредени по шест начина (P3 = 6): 1,2,3-1,3,2-2,1,3-2,3,1-3,2,1-3 , 1.2. И ако няма три такива топки, а десет или петнадесет? Да изброим всички възможни варианти за много дълго време, след това да стигнем до спасителните комбинаторики. Формата за пермутация ще ни помогне да намерим отговора на въпроса, който ни интересува. Pn = n * P (n-1). Ако се опитаме да опростим формулата, получаваме: Pn = n * (n-1) * hellip- * 2 * 1. И това е продуктът на първите естествени числа. Такъв номер се нарича факториал и се обозначава като n!

Помислете за проблема. Водачът всяка сутрин изгражда своя отряд на линия (двадесет души). Отрядът има трима най-добри приятели - Костя, Саша и Леша. Каква е вероятността те да застанат една до друга? За да се намери отговор на въпроса, вероятността за "добър" резултат трябва да бъде разделена на общия брой резултати. Общият брой на пермутациите е 20! = 2.5 quintillion. Как да се изчисли броят на "добрите" резултати? Представете си, че Костя, Саша и Леша са един супермен. Тогава имаме само осемнадесет предмета. Броят на пермутациите в този случай е 18 = 6,5 квадрилиона. С всичко това Костя, Саша и Леша могат произволно да се движат помежду си в своите неделими три, а това е 3! = 6 опции. Така че имаме само 18 "добри" аранжимента! * 3! Можем да намерим само необходимата вероятност: (18! * 3!) / 20! Което е равно на 0.016. Ако преведете в проценти, то се оказва, че е само 1,6%.

поставяне

Сега ще разгледаме друга много важна и необходима формула на комбинираното. Разположението е следващият ни въпрос, който предлагаме да разгледате в този раздел на статията. Ние ще усложним нещата. Да предположим, че искаме да разгледаме възможни пермутации, не само от целия комплект (n), но от по-малкия (m). Тоест ние разглеждаме permutations на n обекти в m.

Основните формули на комбинираното са не само да се научи, но и да ги разбере. Дори въпреки факта, че те са сложни, тъй като нямаме един параметър, а два. Да предположим, че m = 1, тогава A = 1, m = 2, а след това A = n * (n - 1). Ако опростим по-нататък формулата и отидем до рекорда с помощта на factorials, тогава получаваме една изчерпателна формула: A = n! / (n - m)!

съчетание

Ние разгледахме почти всички основни формули на комбинаторни с примери. Сега ще преминем към заключителния етап на обсъждане на основния курс на комбинатиката - познаване на комбинацията. Сега ще изберем m елементи от нашата съществуваща n, докато ние ще избираме всичко с всички възможни средства. Какво тогава се различава от настаняването? Няма да обмислим реда. Този неорганизиран комплект ще бъде комбинация.

Незабавно въвеждаме означението: C. Вземаме разположението на m топки от n. Спираме да обръщаме внимание на реда и да получаваме повторни комбинации. За да получим броя комбинации, трябва да делим броя на разположенията по m! (m фактор). Това означава, че C = A / m! По този начин, начини да избирате от n топки малко, е колкото да изберете почти всичко. Това е логичен израз: да избереш малко, така че да изхвърлиш почти всичко. Дори в този параграф е важно да се спомене, че максималният брой комбинации може да бъде постигнат, когато се опитвате да изберете половината от елементите.

Как да изберем формула за решаване на проблем?

Разгледахме подробно основните формули на комбинираното: разположение, пермутация и комбинация. Сега нашата задача е да улесним избора на необходимата формула за решаване на проблема с комбинаторите. Можем да използваме следната по-скоро проста схема:

1. Задайте си въпроса: реда на разполагане на елементи се взема предвид в текста на задачата?
2. Ако отговорът е "не", използвайте комбинацията от формули (C = n! / (M! * (N - m)!)).
3. Ако няма отговор, тогава е необходимо да се отговори на още един въпрос: са всички елементи, включени в комбинацията?
4. Ако отговорът е да, използвайте формулата за пермутация (P = n!).
5. Ако отговорът е "не", използвайте формулата за разположение (A = n! / (N - m)!).

пример

Разгледахме елементите на комбинирането, формулите и някои други въпроси. Сега се насочваме към истинския проблем. Представете си, че преди да поставите киви, оранжево и банан.

Първият въпрос: колко начини могат да бъдат пренаредени? За тази цел използваме формула за пермутация: P = 3! = 6 начина.

Въпрос втора: колко начина да избера един плод? Това е очевидно, имаме само три възможности - да изберем киви, оранжево или банан, но да приложим формулата от комбинации: C = 3! / (2! * 1!) = 3.

Трети въпрос: колко начина можете да изберете две плодове? Какви опции имаме като цяло? Киви и портокалови киви, банан оранжево и банан. Това означава, че три варианта, но е лесно да се провери използва комбинация формула: C = 3! / (1! 2!) = 3

Въпрос 4: Колко начина можете да изберете три плода? Очевидно можете да изберете три плода по един начин: вземете киви, оранжево и банан. С = 3! / (0! * 3!) = 1.

Въпрос 5: Колко начина да избера поне един плод? Това условие означава, че можем да вземем един, два или и трите плода. Ето защо добавяме C1 + C2 + C3 = 3 + 3 + 1 = 7. Това означава, че имаме седем начина да вземем от масата поне един плод.