Комбинация за разлагане. Комбинации с повторения

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

Правило за умножение (основна комбинаторна формула)

Общ бройначини, по които можете да изберете един елемент от всяка група и да ги подредите в определен ред (т.е. да получите подредена колекция), е равно на:

Пример 1

Монетата беше обърната 3 пъти. Колко различни резултати можете да очаквате?

Решение

Първата монета има алтернативи - или глави, или опашки. Има и алтернативи за втората монета и т.н., т.е. .

Желаният брой начини:

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

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

Пример 2

На рафта има 30 книги, от които 20 са математически, 6 са технически и 4 са икономически. Колко начина има да избереш една математическа или една икономическа книга.

Решение

Математическа книга може да бъде избрана по начини, икономическа книга по начини.

Според правилото за сумата има начин да изберете книга по математика или икономика.

Разположения и пермутации

Настаняване- Това са подредени колекции от елементи, които се различават един от друг или по състав, или по реда на елементите.

Разположения без повторениекогато избраният елемент не се върне в популацията преди избора на следващия. Такъв избор се нарича последователен избор без заместване и неговият резултат е поставяне без повторения от елементи по .

Броят различни начини, по които може да се направи последователен избор, без да се връщат елементи от населениеобемът е равен на:

Пример 3

Дневният график се състои от 5 различни уроци. Определете броя на опциите за график, когато избирате от 11 дисциплини.

Решение

Всеки вариант на графика представлява набор от 5 дисциплини от 11, различаващи се от другите варианти както по състав, така и по ред. Ето защо:

Пермутацииса подредени колекции, които се различават една от друга само по реда на елементите. Броят на всички пермутации на набор от елементи е

Пример 4

По колко начина могат да седнат 4 души на една маса?

Решение

Всяка опция за сядане се различава само по реда на участниците, тоест това е пермутация от 4 елемента:

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

Общият брой различни начини, по които може да се направи избор, връщайки елементи от популация от обем, е

Пример 5

Асансьорът спира на 7 етаж. По колко начина могат да излязат 6 пътника в асансьора на тези етажи?

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

Решение

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

Комбинации

Комбинацииот n елемента по k се наричат ​​неподредени колекции, които се различават една от друга с поне един елемент.

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

Броят на комбинациите от елементи е равен на:

Пример 6

В кутия има 9 ябълки. По колко начина могат да се изберат 3 ябълки от кутията?

Решение

Всеки избор се състои от 3 ябълки и се различава от останалите само по състав, тоест това е комбинация без повторения на 9 елемента:

Брой начини да изберете 3 ябълки от 9:

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

Броят на комбинациите с повторения на елементи от:

Пример 7

Пощата продава пощенски картички от 3 вида. По колко начина могат да се купят 6 пощенски картички?

Това е задача за намиране на броя на комбинациите с повторения от 3 до 6:

Разделяне на набор на групи

Нека наборът от различни елементисе разделя на групи, така че първата група включва елементи, втората - елементи, -тата група - елементи и . Тази ситуация се нарича разделяне на набора на групи.

Броят на дяловете в групи, когато елементите попадат в първата, елементите във втората, в k-та група- елементи, е равно на:

Пример 8

Група от 16 души трябва да бъде разделена на три подгрупи, първата от които трябва да има 5 души, втората - 7 души, а третата - 4 души. По колко начина може да стане това?

Решение

Тук

Брой дялове на 3 подгрупи:

Концепцията геометричен законразпределение на дискретни случайна величинаи се разглежда пример за решаване на задачата. Дадени са формули математическо очакванеи дисперсията на случайна променлива, разпределена по геометричен закон.

В комбинаториката се изучават въпроси за това колко комбинации от определен тип могат да бъдат направени от дадени обекти (елементи).

Раждането на комбинаториката като клон се свързва с трудовете на Б. Паскал и П. Ферма върху теорията хазарт. Голям принос за развитието на комбинаторните методи направи G.V. Лайбниц, Й. Бернули и Л. Ойлер.

Френският философ, писател, математик и физик Блез Паскал (1623–1662) показа рано своята изключителна математически способности. Кръгът на математическите интереси на Паскал беше много разнообразен. Паскал доказа едно
от основните теореми на проективната геометрия (теорема на Паскал), конструира сумираща машина (събираща машина на Паскал), даде метод за изчисляване на биномни коефициенти (триъгълник на Паскал), за първи път точно дефинира и приложи метода за доказателство математическа индукция, направи значителна крачка в развитието на инфинитезималния анализ, игра важна роляв развитието на теорията на вероятностите. В хидростатиката Паскал установи нейния основен закон (закон на Паскал). „Писма до един провинциалец“ на Паскал е шедьовър на френската класическа проза.

Готфрид Вилхелм Лайбниц (1646–1716) е немски философ, математик, физик и изобретател, юрист, историк и лингвист. В математиката, заедно с И. Нютон, той разработва диференциални и интегрално смятане. Той направи важен принос в комбинаториката. По-специално, проблемите на теорията на числата са свързани с неговото име.

Готфрид Вилхелм Лайбниц имаше малко впечатляващ външен вид и затова създаваше впечатление на доста невзрачен човек. Веднъж в Париж той влезе в книжарница с надеждата да си купи книга от свой познат философ. Когато посетител попита за тази книга, продавачът на книги, след като го прегледа от главата до петите, отговори подигравателно: „Защо ви трябва? Способни ли сте да четете такива книги? Преди ученият да успее да отговори, самият автор на книгата влезе в магазина с думите: „Поздрави и уважение към великия Лайбниц!“ Продавачът не можеше да разбере, че наистина притежава известния Лайбниц, чиито книги бяха в голямо търсене сред учените.

В бъдеще важна роля ще играе следното.

Лема.Нека в множеството елементи, а в множеството - елементи. Тогава броят на всички различни двойки, където ще бъде равен на.

Доказателство.Наистина с един елемент от множеството можем да направим толкова различни двойки, но само в множеството от елементи.

Разположения, пермутации, комбинации

Да кажем, че имаме набор от три елемента. По какви начини можем да изберем два от тези елементи? .

Определение.Подредбите на набор от различни елементи по елементи са комбинации, които са съставени от дадени елементи по > елементи и се различават или по самите елементи, или по реда на елементите.

Броят на всички разположения на набор от елементи по елементи се обозначава с (от начална буква френска дума„подреждане“, което означава разположение), където и .

Теорема.Броят на разположенията на набор от елементи по елементи е равен на

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

Пример.По колко начина едно знаме може да бъде съставено от три хоризонтални ивици с различни цветове, ако има материал от пет цвята?

Решение.Желаният брой знамена с три ленти:

Определение.Пермутацията на набор от елементи е подреждането на елементите в определен ред.

По този начин всички различни пермутации на набор от три елемента са

Посочен е броят на всички пермутации на елементите (от началната буква на френската дума "permutation", което означава "пермутация", "движение"). Следователно броят на всички различни пермутации се изчислява по формулата

Пример.По колко начина могат да се поставят топовете на шахматна дъска, така че да не се нападат един друг?

Решение.Необходим брой поставяне на топове

По дефиниция!

Определение.Комбинации от различни елементи по елементи са комбинации, които са съставени от дадени елементи по елементи и се различават поне с един елемент (с други думи, -елементни подмножества даден наборот елементи).

Както можете да видите, при комбинации, за разлика от разположенията, редът на елементите не се взема предвид. Броят на всички комбинации от елементи по елементи във всяка е посочен (от началната буква на френската дума „combinasion“, което означава „комбинация“).

Числа

Всички комбинации от комплекта от две - .

Свойства на числата (\sf C)_n^k

Наистина, всяко подмножество от -елементи на дадено множество от -елементи съответства на едно и само едно подмножество от -елементи на същото множество.

Наистина можем да избираме подмножества от елементи по следния начин: фиксираме един елемент; броят на -елементните подмножества, съдържащи този елемент, е ; броят на -елементните подмножества, които не съдържат този елемент, е .

Триъгълник на Паскал

В този триъгълник крайните числа във всеки ред са равни на 1, а всяко неекстремно число е равно на сумата от двете числа от предходния ред над него. По този начин този триъгълник ви позволява да изчислявате числа.

Теорема.

Доказателство.Разгледайте набор от елементи и решете следния проблем по два начина: колко последователности могат да бъдат съставени от елементи на даден
набори, в които нито един елемент не се среща два пъти?

1 начин. Избираме първия член на редицата, след това втория, третия и т.н. член

2 начина. Първо избираме елементи от даден набор и след това ги подреждаме в някакъв ред

Умножете числителя и знаменателя на тази дроб по:

Пример.По колко начина можете да изберете 5 числа от 36 в играта Спортлото?

Желаният брой начини

Задачи.

1. Автомобилните номера се състоят от 3 букви от руската азбука (33 букви) и 4 цифри. Колко различни номера на коли има?
2. Пианото има 88 клавиша. По колко начина могат да бъдат произведени последователно 6 звука?
3. Колко шестцифрени числа се делят на 5?
4. По колко начина могат да се сложат 7 различни монети в три джоба?
5. Колко петцифрени числа можете да направите десетичен запиское число 5 се среща поне веднъж?
6. По колко начина могат да седнат 20 души кръгла маса, считайки методите за еднакви, ако те могат да бъдат получени един от друг чрез движение в кръг?
7. Колко петцифрени числа, които се делят на 5, нямат еднакви цифри?
8. Върху карирана хартия със страна на клетката 1 cm се начертава кръг с радиус 100 cm, който не минава през върховете на клетките и не докосва страните на клетките. Колко квадрата може да пресече тази окръжност?
9. По колко начина могат да се подредят числата в редица, така че числата да стоят едно до друго и освен това да вървят във възходящ ред?
10. Колко петцифрени числа могат да бъдат направени от цифри, ако всяка цифра може да се използва само веднъж?
11. От думата ROT чрез пренареждане на буквите можете да получите и следните думи: TOR, ORT, OTR, TRO, RTO. Те се наричат ​​анаграми. Колко анаграми можете да направите с ЛОГАРИТ?
12. Да се ​​обадим разделянеестествено число неговото представяне като сума естествени числа. Ето, например, всички дялове на число:

Дяловете се считат за различни, ако се различават по номера или по реда на събираемите.

Колко различни части на едно число има?
13. Колко ненарастващи трицифрени числа има?
14. Колко ненарастващи 4-цифрени числа има?
15. По колко начина могат да се настанят 17 души в редица, така че да са един до друг?
16. момичетата и момчетата се настаняват на случаен принцип в редица места. По колко начина могат да бъдат настанени така, че две момичета да не седят едно до друго?
17. момичетата и момчетата се настаняват на случаен принцип в редица места. По колко начина могат да бъдат настанени така, че всички момичета да седят едно до друго?

Трябва да се отбележи, че комбинаториката е самостоятелна секция висша математика(а не част от terver) и са написани тежки учебници по тази дисциплина, чието съдържание понякога не е по-лесно от абстрактната алгебра. Малка част обаче ще ни е достатъчна. теоретични знания, а в тази статия ще се опитам да анализирам основите на темата с типични комбинаторни задачи в достъпна форма. И много от вас ще ми помогнат ;-)

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

След като много подредени, сега за комбинациите. Най-често срещаните видове комбинации са пермутации на обекти, изборът им от набор (комбинация) и разпределение (поставяне). Нека да видим как се случва това в момента:

Пермутации, комбинации и поставяния без повторение

Не се страхувайте от неясни термини, особено след като някои от тях наистина не са много успешни. Да започнем с опашката на заглавието - което означава " без повторение"? Това означава, че в този раздел ще разгледаме множества, които се състоят от различниобекти. Например ... не, няма да предлагам каша с поялник и жаба, нещо по-вкусно е по-добре =) Представете си, че на масата пред вас се материализират ябълка, круша и банан (ако има всеки, ситуацията може да бъде симулирана в реално време). Подреждаме плодовете отляво надясно в следния ред:

ябълка / круша / банан

Първи въпрос: по колко начина могат да бъдат пренаредени?

Една комбинация вече е написана по-горе и няма проблеми с останалите:

ябълка / банан / круша
круша / ябълка / банан
круша / банан / ябълка
банан / ябълка / круша
банан / круша / ябълка

Обща сума: 6 комбинации или 6 пермутации.

Е, не беше трудно да изброя всички възможни случаи тук, но какво ще стане, ако има повече елементи? Вече с четири различни плода, броят на комбинациите ще се увеличи значително!

Без мъки - 3 обекта могат да бъдат пренаредени по начини.

Втори въпрос: по колко начина можете да изберете а) един плод, б) два плода, в) три плода, г) поне един плод?

Защо да изберете? И така, в предишния абзац са събудили апетит - за да ядат! а) Един плод може да бъде избран, очевидно, по три начина - вземете или ябълка, или круша, или банан.

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

Запис в този случайтрябва да се разбира по следния начин: „по колко начина можете да изберете 1 плод от три?“

б) Изброяваме всички възможни комбинации от два плода:

ябълка и круша;
ябълка и банан;
круша и банан.

Броят на комбинациите е лесен за проверка по същата формула:

Записът се разбира по подобен начин: „по колко начина можете да изберете 2 плода от три?“.

в) И накрая, могат да бъдат избрани три плода единствения начин:

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

г) По колко начина можете да вземете поне единплодове? Условието „поне един“ предполага, че сме доволни от 1 плод (който и да е) или произволни 2 плода или всичките 3 плода:
начини, по които можете да изберете поне един плод.

За отговор на следващ въпросИмам нужда от двама доброволци ... ... Е, тъй като никой не иска, тогава ще се обадя на дъската =)

Трети въпрос: по колко начина може да се раздаде един плод на Даша и Наташа?

За да раздадете два плода, първо трябва да ги изберете. Съгласно параграф "be" от предишния въпрос, това може да стане по начини, ще ги пренапиша отново:

ябълка и круша;
ябълка и банан;
круша и банан.

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

И такава пермутация е възможна за всяка двойка плодове.

В този случай работи формула за поставяне:

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

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

Също така напомням, че сега говорим за набор от различниобекти и ако една ябълка/круша/банан се замени с 3 ябълки или дори 3 много подобни ябълки, то в контекста на разглеждания проблем те пак ще бъдат разглеждани различни.

Нека се спрем на всеки тип комбинация по-подробно:

Пермутации

Пермутации се наричат ​​комбинации от същото различниобекти и се различават само по реда, в който са поставени. Броят на всички възможни пермутации се изразява с формулата

Отличителна черта на пермутациите е, че всяка от тях включва ВСИЧКОкомплект, т.е. всичкообекти. Например приятелско семейство:

Задача 1

По колко начина могат да седнат 5 души на една маса?

Решение: използвайте формулата за броя на пермутациите:

Отговор: 120 начина

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

Задача 2

Колко четирицифрени числа могат да се съставят от четири карти с числа 0, 5, 7, 9?

За да направите четирицифрено число, трябва да използвате всичкочетири карти (числата, на коиторазлично! ) , а това е много важна предпоставка за прилагане на формулата.Явно, като пренаредим картите, ще получим различни четирицифрени числа, ... чакай, тук всичко наред ли е? ;-)

Помислете внимателно върху проблема! Като цяло това особеносткомбинаторни и вероятностни проблеми - те ТРЯБВА ДА МИСЛЯТ. И често мислят по светски начин, както например в анализа уводен примерс плодове. Не, разбира се, не призовавам към глупаво разработване на други раздели на математиката, но трябва да отбележа, че същото интегралимога научи се да решавашчисто механично.

Решение и отговор в края на урока.

Увеличаване на оборота:

Комбинации

Учебниците обикновено дават стегнато и не много ясна дефинициякомбинации, следователно в моята уста формулировката няма да бъде особено рационална, но, надявам се, разбираема:

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

Задача 3

В кутия има 15 части. По колко начина могат да се вземат 4 части?

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

В задачата говорим за селекция от 4 части, в които техните „ по-нататъшна съдба"- грубо казано," просто са избрали 4 парчета и това е. Така имаме комбинация от части. Преброяваме броя им:

Тук, разбира се, не е нужно да местите огромни числа.
В подобна ситуация ви съветвам да използвате следния трик: в знаменателя изберете най-големия факториел (в случая ) и намалете дробта с него. За да направите това, числителят трябва да бъде представен като. Ще пиша много подробно:

Можете да вземете 4 части от кутията по различни начини.

Още веднъж, какво означава това? Това означава, че от комплект от 15 различни части можете да направите хиляда триста шестдесет и пет единствен по рода сикомбинации от 4 части. Тоест всяка такава комбинация от 4 части ще се различава от другите комбинации поне по един детайл.

Отговор: 1365 начина

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

Единственият начин е да не вземете нито един детайл;
начини, по които можете да вземете 1 част (всяка от 15);
начини, по които можете да вземете 14 части (в този случай една от 15-те ще остане в кутията);
- единственият начин да вземете всичките петнадесет части.

Препоръчвам ви внимателно да се запознаете с бинома на Нютон и триъгълника на Паскал, според които, между другото, е много удобно да проверявате изчисленията за малки стойности на "en".

Задача 4

По колко начина могат да бъдат избрани 3 карти от тесте от 36 карти?

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

Задача 4

Човек участва в турнир по шах и всеки играе по 1 партия с всеки. Колко игри бяха изиграни в турнира?

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

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

Еквивалентен проблем е относно ръкостисканията: в отдела работят мъже и всички се ръкуват един с друг, колко ръкостискания правят? Между другото, шахматистите също се ръкуват помежду си преди всяка игра.

Е, изводите са два:

Първо, не всичко, което е очевидно, е очевидно;

И второ, не се страхувайте да решавате проблеми „извън кутията“!

Благодаря ви много за вашите писма, те помагат за подобряване на качеството на учебните материали!

Настаняване

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

Какъв е нашият живот? Играта:

Задача 5

Боря, Дима и Володя седнаха да играят точка. По колко начина могат да раздадат по една карта? (колодето съдържа 36 карти)

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

Начини за раздаване на 3 карти на играчите.

Има друга схема на решение, която от моя гледна точка е още по-ясна:

начини, по които можете да изтеглите 3 карти от тестето.

Сега нека да разгледаме един от седем хиляди сто и четиридесеткомбинации, например: цар пика, 9 купа, 7 купа. В комбинаторна терминология, тези 3 карти могат да бъдат "пренаредени" между Борей, Дима и Володя по следните начини:

KP, 9H, 7H;
KP, 7H, 9H;
9H, KP, 7H;
9H, 7H, KP;
7H, KP, 9H;
7H, 9H, KP.

И същият факт е верен за всекиуникален комплект от 3 карти. И не забравяйте, ние броихме такива набори. Не е нужно да сте професор, за да разберете, че броят на намерените комбинации трябва да се умножи по шест:

Има начини да раздадете една карта на трима играчи.

По същество това се оказа визуална проверка формули, чието окончателно значение ще изясним в следващия раздел.

Отговор: 42840

Може би все още имате въпрос, но кой раздаде картите? …Вероятно учител =)
И за да няма обидени, цялата студентска група ще участва в следната задача:

Задача 6

AT студентска група 23 души. По колко начина могат да бъдат избрани началник и неговия заместник?

Задачата за "поставяне" на позиции в отбора е много често срещана и е истински акордеон. Бързо решениеи отговорът в края на урока.

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

25) Какво се нарича пермутации?

Пермутации- различни подредени множества, които се различават само по реда на елементите (т.е. могат да бъдат получени от едно и също множество).

26) По каква формула се изчислява броят на пермутациите на n различни елемента?

Пермутации.Да вземем нразлични елементи: а 1 , а 2 , а 3 , …, ан . Ще ги пренаредим всички възможни начини, като запазваме номера им и променяме само реда на разположението им. Всяка от получените по този начин комбинации се нарича пермутация.Обща сума пермутации на n елементаозначено P n. Това число е равно на произведението на всички цели числа от 1 до н:

Символ н! (Наречен факториел) - съкратено обозначение на произведението: 1 2 3 ... ... ( н-един) · н.

ПРИМЕР Намерете броя на пермутациите от три елемента: а, b, ° С.

РЕШЕНИЕ Съгласно горната формула: П 3 = 1 2 3 = 6.
Наистина имаме 6 пермутации: abc, acb, bac, bca, cab, cba.

27) Какво се нарича разположения? Запишете формулата, по която се изчислява броя на поставянията на n елемента по m.

Настаняванеса подредени подмножества на дадено крайно множество.

Настаняване.Ще направим групи от м нелементи, подреждайки тези мвзети елементи в различен ред. Получените комбинации се наричат подреждане на n елемента по m .

Общият им брой се означава с: и е равен на произведението:

ПРИМЕР Намерете броя на разположенията на четири елемента a, b, c, dс две.

Решение В съответствие с формулата получаваме:

Това са разположенията: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

28) Какво се наричат ​​комбинации? Запишете формулата, по която се изчислява броят на комбинациите от n елемента по m.

Комбинация без повторения на n елемента по mима м-елемент подмножество на някои н- набор от елементи.

Накратко такива комбинации се наричат ​​„комбинации от мНа н" и техният номер означават или . Освен това н- набор от елементи ще бъде означен като н-Много.

Комбинации.Ще направим групи от мразлични елементи, взети от набор, състоящ се от нелементи, независимо от реда на тези m елемента.Тогава ще получим комбинации от n елемента по m .

Общият им брой е посочен и може да се изчисли по формулата:

От тази формула става ясно, че

Обърнете внимание, че можем само да композираме една комбинация от n елемента по n, която съдържа всички n елемента.Формулата за броя на комбинациите дава тази стойност, само ако приемем това 0! = 1 , Какво е определението 0! .

Според тази дефиниция получаваме:

Общият брой комбинации може да се изчисли с друг израз:

ПРИМЕР Намерете броя на комбинациите от пет елемента: а б В Г Дтри.

Решение:

Тези комбинации: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

29) По каква формула се изчислява броят на пермутациите на n елемента, ако елементите се повтарят?

Пермутацииот н елементи се наричат ​​разположения на тези нелементи от н (Пермутации - специален случайразположения).

Брой пермутации без повторение (н

Пример . Да вземем писмата Б, А, Р . Какви пермутации на тези букви могат да се получат? Колко такива набора ще се получат, ако: 1) буквите в набора не се повтарят; 2) буквата А се повтаря два пъти?

Решение.

1. Вземете комплекти: BAR, BRA, ARB, ADB, RAB, RBA.

По формула (3.3) получаваме: комплекти.

2. Вземете комплекти: BARA, BRAA, BAAR, AARB, AABR, ABAR, ARAB, ARBA, ABRA, RABA, RAAB, RBAA.

По формула (3.4) получаваме: комплекти.

Пример . Колко шестцифрени числа могат да се съставят от цифрите 0, 1, 2, 3, 4, 5, така че числата да не се повтарят в числото?

Решение.От тези шест цифри можете да направите P 6 \u003d 6! = 720 пермутации. Но числата, които започват с нула, не са шестцифрени. Такива числа се различават един от друг чрез пермутация на останалите пет цифри, което означава, че те ще бъдат P 5 \u003d 120. Следователно ще има 720 - 120 \u003d 600 шестцифрени числа.

Пример . По колко начина могат да се поставят белите фигури (2 топа, 2 коня, 2 офицера, дама и цар) на първия ред на шахматната дъска?

Решение.Първата линия на шахматната дъска се състои от 8 клетки, върху които трябва да бъдат поставени тези 8 фигури. Различни опцииподредбите ще се различават само по реда на фигурите, което означава, че това ще бъдат пермутации с повторения P 8 (2,2,2).

По формулата (3.4) получаваме: начини.

30) Каква формула определя броя на поставянията с повторения на n елемента по m елемента?

Настаняване

Разположенияот н елементи от м елементи ( м < н) се наричат ​​комбинации, съставени от данни н елементи от м елементи, които се различават или по самите елементи, или по реда на елементите.

Брой поставяния без повторенияот н На м (нразлични елементи) се изчислява по формулата:

Пример . Да вземем писмата Б, А, Р . Какви разположения на тези букви, взети две по две, могат да се получат? Колко такива набора ще се получат, ако: 1) буквите в набора не се повтарят; 2) буквите могат да се повтарят?

Решение.

1. Ще получите следните комплекти: BA, BR, AR, AB, RB, RA .

По формула (3.1) получаваме: комплекти.

2. Вземете комплекти: BB, BA, BR, AA, AB, AR, RR, RB, RA.

По формула (3.2) получаваме: множества.

Пример. По пътя има 6 светофара. Колко различни комбинации от техните сигнали може да има, ако всеки светофар има 3 състояния: "червено", "жълто", "зелено"?

Решение.Нека напишем няколко комбинации: KKKZHZZ, ZZZZZZZ, KZhZKZHZ... Виждаме, че съставът на извадката се променя и редът на елементите е значителен (в крайна сметка, ако например в извадката KZHZKZHZ, K и F са разменени, ситуацията на пътя ще бъде различна). Следователно прилагаме формула (3.2) и изчисляваме броя на поставянията с повторения от 3 до 6, получаваме комбинации.

31) Каква формула определя броя на комбинациите с повторения на n елемента по m елемента?

Комбинации

Комбинации от n елемента по m елементасе наричат ​​комбинации, съставени от данни н елементи от м елементи, които се различават поне с един елемент (разликата между комбинациите и разположенията е, че редът на елементите не се взема предвид при комбинациите).

Брой комбинации без повторения(н различни елементи, взети от м ) се изчислява по формулата:

Пример . Да вземем писмата Б, А, Р . Какви комбинации от тези букви, взети две по две, могат да се получат? Колко такива набора ще се получат, ако: 1) буквите в набора не се повтарят; 2) можете да вземете две еднакви букви.

Решение.

1. Вземете комплекти: BA (BA и AB - същия комплект) AR и РБ

По формула (3.5) получаваме: комплекти.

2. Вземете комплекти: BB, BA, BR, AA, AR, RR.

По формула (3.6) получаваме: множества.

Пример . От 20 ученици трябва да бъдат избрани двама придружители. По колко начина може да стане това?

Решение.Необходимо е да се изберат двама души от 20. Ясно е, че нищо не зависи от реда на избор, тоест Иванов-Петров или Петров-Иванов са една и съща двойка придружители. Следователно това ще бъдат комбинации от 20 към 2.

По формула (3.5) получаваме: начини.

Пример . В хлебния отдел има бял и черен хляб. По колко начина можете да си купите 6 хляба?

Решение.Обозначавайки кифличките бял и черен хляб с буквите B и H, ще направим няколко проби: BBBBBBB, BBCHCHBB, HCHCHCHCHB, ... Съставът се променя от проба на проба, редът на елементите не е значим, което означава, че това са комбинации с повторения от 2 до 6. По формулата (3.6 ) получаваме начини.

Ще проверим и изпишем всички опции за покупка: BBBBBBB, BBBBBCH, BBBBBCHCH, BBBCHCHCH, BBCHCHCHCH, BCHCHCHCHCH, HCHCHCHCHCH. Всъщност има 7 от тях.

32) Какво се нарича сбор от две събития?

Сумата от две събития инаименувайте събитие, състоящо се в настъпването на събитие, или събитие, или и двете от тези събития.
Сумата от няколко събитияназовете събитие, състоящо се в настъпването на поне едно от тези събития.

33) Какво се нарича продукт на две събития?

Продукт на две събитиянаричаме събитието, състоящо се в съвместното възникване на тези събития.

34) Каква е вероятността за сумата от две несъвместими събития?

СъбитиеНаречен независимо от събитието, ако настъпването на събитието не променя вероятността за настъпване на събитието , т.е. ако условната вероятност на събитието е равна на неговата безусловна вероятност:
.
Свойството за независимост на събитията е взаимно: ако едно събитие не зависи от събитието, тогава събитието не зависи от събитието.
Теорема.Вероятността за съвместна поява на двама независими събитияе равно на произведението на вероятността от тези събития:
.
Извикват се няколко събития независими по двойкиако всеки две от тях са независими.
Извикват се няколко събития колективно независими, ако всеки две от тях са независими и всяко събитие и всички възможни работиостатъка.

35) Формулирайте теоремата за добавяне?

Вероятност Р(A+B) суми от събития НОи ATе равно на

Р (A+B) = Р (НО) + Р (AT) – Р (AB). (2.2)

Доказателство.

Нека докажем теоремата за добавяне за схемата от случаи. Позволявам П- броя на възможните резултати от експеримента, т А- броят на резултатите, благоприятно събитие НО, t V -брой изходи, благоприятни за събитието AT, а раздел -броят на резултатите от опита, при които се случват и двете събития (т.е. резултатите, благоприятни за продукта AB). След това броят резултати, за които се случва събитието A+B, се равнява t A + t B - t AB(защото общо ( t A + t B)разделброени два пъти: като резултати, благоприятни НОи резултатите благоприятни AT). Следователно вероятността на сумата може да се определи по формулата 2.2, която трябваше да бъде доказана.

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

Комбинаториката възниква през 16 век. Първите комбинаторни проблеми се отнасят до хазарта. Днес комбинаторни методиизползвани за решаване транспортни задачи, съставяне на планове за производство и реализация на продукцията. Установяват се връзки между комбинаторика и проблеми линейно програмиране, статистика. Комбинаториката се използва за съставяне и декодиране на шифри, за решаване на други проблеми на теорията на информацията.

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

Пример за комбинаторна задача. как трицифрени числаможе да се състои от цифрите 0, 2, 4, 6, 8, като всяка от тях се използва не повече от веднъж в нотацията?

азначин. Нека се опитаме да запишем всички такива числа. Първото място може да бъде всяка цифра с изключение на 0. Например 2. Второто място е всяка цифра от 0, 4, 6 и 8. Нека 0. Тогава всяка от 4, 6, 8 може да бъде избрана като трета цифра. Ние вземете три числа

Вместо 0, 4 може да се постави на второ място, тогава третата цифра може да се напише или 0, или 6, или 8:

Разсъждавайки по подобен начин, получаваме още две тройки трицифрени числа с числото 2 на първо място:

Няма други, освен изписаните 12, трицифрени числа с цифрата 2 на първо място и отговарящи на условието.

Ако на първо място напишем числото 4, а останалите изберем от числата 0, 2, 6, 8, тогава ще получим още 12 числа:

Еднакъв брой трицифрени числа могат да бъдат направени с числото 6 на първо място и числото 8 на първо място. Така че необходимото количество е:

Ето и числата:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Отговор: 48. ◄

Методът на разсъждение, който използвахме при решаването на предишната задача, се нарича изброяване настроики .

Правила за събиране и умножение

Комбинаторно правило за добавяне(правило "или". - едно от основните правила на комбинаториката, което гласи, че ако има н елементи и елемент A 1може да избира м 1 начини, елемент A2може да избира м 2 А н може да избира м н начини, след това изберете или A 1, или A2, или и така нататък, А н мога

м 1 + м 2 + ... + м н

начини.

Например, изберете подарък за дете от 9 коли, 7 плюшени мечета и 3 железницимога

начини.

Отговор: 19. ◄

Правило за умножение (правило „и“) - още един от важни правилакомбинаторика. Според него, ако елементът A 1може да избира м 1 начини, елемент A2може да избира м 2 начини и така нататък, елемент А н може да избира м н начини, тогава наборът от елементи ( A 1, A2, ... , А н ) може да избира

м 1 · м 2 · ... · м н

начини.

Например.

1) Можете да изберете кола, плюшено мече и железопътна линия за подарък за дете, като избирате от 9 коли, 7 плюшени мечета и 3 железопътни линии, можете

9 7 3 = 189

начини.

Отговор: 189.

2) Нека използваме правилото за умножение, за да решим вече разгледаната по-горе задача: Колко трицифрени числа могат да се съставят от числата 0, 2, 4, 6, 8, като всяко от тях се използва не повече от веднъж при запис на число?

IIначин.

0 не може да бъде първата, така че първата цифра трябва да бъде избрана от 2, 4, 6, 8 - 4 начина;

втората цифра може да бъде всяка от четирите останали - 4 начина;

третата цифра може да бъде избрана между останалите три - 3 начина.

И така, желаният брой трицифрени числа:

4 4 3 = 48.

Отговор: 48. ◄

Пермутации

Комплект от н елементи се нарича подреден , ако на всеки негов елемент се присвои естествено число от 1 до н .

пермутация от н елементи е всеки подреден набор от н елементи.

Например от 4 елемента ♦ ♣ ♠ могат да бъдат направени следните 24 пермутации:

♦ ♣ ♠	♦ ♣ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♠ ♣	♦ ♠ ♣	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♦ ♠	♣ ♦ ♠	♠ ♦ ♣
♦ ♣ ♠	♣ ♠ ♦	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♦ ♣	♣ ♠ ♦	♠ ♣ ♦
♦ ♠ ♣	♠ ♣ ♦	♣ ♠ ♦	♠ ♣ ♦

◄

Брой пермутации от н елементи обикновено се обозначават П н . Чрез изброяване на възможните опции е лесно да се провери това

P1 = 1; P2 = 2; P3 = 6; P4 = 24.

Като цяло, броят на възможните пермутации от н елементи е равно на произведението на всички естествени числа от 1 до н , това е н! (прочетете "en factorial"):

П н= 1 2 3 ... ( н- 1 ) · н = н!.

За П нрекурсивната формула е валидна:

П н = нП н- 1 .

Факториалната стойност се определя не само за естествени числа, но и за 0:

0! = 1 .

Таблица с факториели на цели числа от 0 преди 10
н		1	2	3	4	5	6	7	8	9	10
н!	1	1	2	6	24	120	720	5 040	40 320	362 880	3 628 800

Например, по колко начина могат 5 момчета и 5 момичета да заемат места на един и същ ред от 1-ви до 10-ти в театъра, ако няма две момчета и две момичета, седнали един до друг?

Има два случая с еднакъв брой начини: 1) момчетата са на нечетни места, момичетата са на четни места и 2) обратното.

Да разгледаме първия случай. Момчетата на странни места могат да седят

P5 = 120

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

120 120 = 14400

начини. Така че всички начини

14 400 + 14 400 = 28 800.

Отговор: 28 800. ◄

Пермутации с повторения

пермутация с повторения от н елементи, сред които к различни, докато ги има н 1 неразличими елементи от първия тип, н 2 неразличими елементи от втория тип и т.н. н к неразличими елементи к -ти тип (където н 1 + н 2 + … + нк = н ), е всяко подреждане на тези елементи н различни места.

Брой пермутации с повторения на дължината н от к различни елементи, взети съгл н 1 , н 2 , …, нк след като всеки е обозначен и изчислен по следния начин: $$P_(n_1,n_2, ... , n_k)=\frac(n{n_1!n_2! ... n_k!}~.$$!}

Например колко различни десетцифрени числа могат да се съставят от числата: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В такъв случай: n= 10, н 1 = 1, н 2 = 2, н 3 = 3, н 4 = 4,$$P_(1, 2, 3, 4)=\frac(10{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$!}

Отговор: 12 600. ◄

Настаняване

Поставяне на n елемента по m(m ≤ n) м елементи, взети в определен ред от данните н елементи.

Две разположения от нелементи от мсе считат за различни, ако се различават по самите елементи или по реда на тяхното подреждане.

Например, ще съставим всички разположения от четири елемента A, B, C, Dпо два елемента:

A B; A C; A D;

B A; B C; B D;

C A; C B; C D;

D A; D B; D.C.

◄

Брой всички разположения от нелементи от мозначава \(A_n^m\) (прочетете: " НОот нНа м") и се изчислява по някоя от формулите: $$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^ m= \frac(n{(n-m)!}$$!}

Примерни задачи.

1) Нека използваме понятието разположения от н елементи от м за решаване на задачата, разгледана вече два пъти по-рано: Колко трицифрени числа могат да се съставят от числата 0, 2, 4, 6, 8, като всяко от тях се използва не повече от веднъж в записа?

аз азазначин.

Първата цифра може да бъде избрана по четири начина от набора 2, 4, 6, 8. Във всеки от тези случаи броят на двойките на втората и третата цифра е равен на броя на поставянията на останалите 4 цифри с 2 Така желаният брой трицифрени числа е: $$4\cdot A_4^ 2=4\cdot \frac(4{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48.!}

2) За полет в космоса е необходимо да се попълни екипаж от шест души. В него трябва да се включат: командирът на кораба, негови първи и втори помощник, двама бордни инженери, единият от които е старши, и един лекар. Командният състав е подбран от 20 пилоти, бордните инженери от 15 специалисти и лекар от 5 лекари. По колко начина може да бъде комплектован екипажът?

Защото в избора командириредът е важен, тогава командирът и двамата му помощници могат да бъдат избрани по \(A_(20)^3\) начина. Редът на бордните инженери също е важен, което означава, че има \(A_(15)^2\) начини да ги изберете. Има само един лекар, за неговия избор има 5 начини. Нека използваме правилото за комбинаторно умножение и намерим броя на възможните корабни екипажи: $$A_(20)^3\cdot A_(15)^2\cdot 5=\frac(20){17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. !} ◄

Ясно е, че ако m = n , тогава $$A_n^m=A_n^n=P_n=n!.$$

Също така е вярно, че ако m = n- 1 , тогава $$A_n^(n-1)=A_n^n=P_n=n!.$$

Поставяния с повторения

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

Нека има н различни предмети. Да изберем от тях м парчета, действащи на следния принцип. Да вземем който и да е, но няма да го инсталираме в нито един ред, а просто да напишем името му под номер 1 и след това да върнем самия обект към останалите. После пак от всички н Избираме един обект (включително, вероятно, този, който току-що беше взет), записваме името му, отбелязвайки го с цифрата 2, и връщаме обекта обратно. И така докато стигнем м заглавия.

Разположенията с повторения се означават с \(\overline(A)_n^m\) и според правилото за умножение се изчисляват по формулата $$\overline(A)_n^m=n^m.$$ m > n , тоест има повече избрани обекти от общия брой. Това не е изненадващо: всеки обект след "използване" се връща обратно и може да бъде използван повторно.

Например броят на опциите за шестцифрена парола, в която всеки знак е число от 0 до 9 или буква латиница(една и съща малка и главна буква - един знак) и може да се повтаря, е равно на: $$\overline(A)_(10+26)^6=\overline(A)_(36)^6=36^ 6 =2~176~782~336.$$Ако малки букви и главни буквисе считат за различни знаци (както обикновено се случва), броят на възможните пароли става още по-колосален: $$\overline(A)_(10+26+26)^6=\overline(A)_(62)^ 6= 62^6=56~800~235~584.$$

◄

Комбинации

Комбинация от n елемента по m(m ≤ n) произволен набор се извиква м елементи, избрани от данните н елементи.

За разлика от разположенията в комбинации, няма значение в какъв ред са посочени елементите. Две комбинации от нелементи от мсе считат за различни, ако се различават поне по един елемент.

Например, нека направим всички комбинации от четири елемента A, B, C, Dпо два елемента:

A B; A C; A D;

B C; B D;

C D.

◄

Броят на всички комбинации от нелементи от мозначава \(C_n^m\) (прочетете: " ° Сот нНа м") и се изчислява по някоя от формулите: $$C_n^m=\frac(A_n^m)(P_m)$$$$C_n^m=\frac(n\cdot (n-1)\cdot (n -2 )~\cdot~ ...~\cdot~ (n-m+1))(1\cdot2\cdot3~\cdot~...~\cdot ~m)$$$$C_n^m=\ frac( n{m!\cdot (n-m)!}.$$!}

Примерни задачи.

1) Екипът за ремонт на училището се състои от 12 бояджии и 5 дърводелци. От тях 4 бояджии и 2 дърводелци да се отделят за ремонт на физкултурния салон. По колко начина може да стане това?

Тъй като редът на бояджиите във всяка избрана четворка и редът на дърводелците във всяка избрана двойка няма значение, тогава, съгласно правилото за комбинаторно умножение, необходимият брой начини е: $$C_(12)^4 \cdot C_5^2 =\frac(12{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. !} ◄

2) В класа има 30 ученици, включително 13 момчета и 17 момичета. По колко начина може да се сформира екип от 7 ученици от този клас, ако в него трябва да има поне едно момиче?

Броят на всички възможни отбори от 7 души от класа е \(C_(30)^7\). Броят на отборите само с момчета е \(C_(13)^7\). Така че броят на отборите с поне едно момиче е: $$C_(30)^7 - C_(13)^7 =\frac(30{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. !} ◄

Комбинации с повторения

В допълнение към обичайните комбинации, помислете комбинации с повторения .

Нека комплектът има н обекти. Да изберем от тях м парчета, действайки по следния принцип. Нека вземем всеки, но няма да го инсталираме в нито един ред, а просто да го запишем и след това да върнем самия обект към останалите. После пак от всички н ще изберем един обект (включително евентуално този, който е бил взет и записан по-рано), ще запишем името му и ще върнем обекта обратно. И така докато стигнем м заглавия.

Основната разлика от разположенията с повторения е, че в този случай елементите на списъка не са номерирани. Например списък "A, C, A, B"и списък "A, A, B, C"се считат за еднакви.

Комбинациите с повторения се означават с \(\overline(C)_n^m\) и се изчисляват по формулата $$\overline(C)_n^m=P_(m,~n-1)=\frac((m+ n-1 ){m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда !} m > n , тоест има повече избрани обекти от общия брой. Наистина, всеки предмет след "използване" се връща и може да се използва отново и отново.

Например, нека да разберем по колко начина можете да купите 7 торти в сладкарския отдел, ако има 4 разновидности от тях в продажба?

Естествено е да приемем, че броят на тортите от всеки вид е поне 7, като при желание можете да закупите само торти от един от тях. Тъй като редът, в който са поставени закупените торти в кутията, не е важен, имаме работа с комбинации с повторения. Тъй като трябва да изберете 7 торти от 4 от нейните видове, необходимият брой начини е: $$\overline(C)_4^7=\frac((7+4-1){7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$!}

Отговор: 120. ◄

Бином на Нютон и биномни коефициенти

Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^(n-1)a^1+...+C_n^mx^(n-m)a^m+...+ Извиква се C_n^nx^0a^n$$ Бином на Нютон или Формула на Нютон . Дясна частравенство се нарича биномно разширение в сума , а коефициентите \(C_n^0,~C_n^1,~...~,~C_n^n\) са биномни коефициенти .

Свойства на биномните коефициенти:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^(n-m)\\ ~~ ~~~~~~3.~~C_n^m=C_(n-1)^(m-1)+C_(n-1)^(m)\\ ~~~~~~~~4.~ ~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^ 4+~... =C_n^1+C_n^3+C_n^5+~...=2^(n-1)\\ ~~~~~~~~6.~~C_n^n+C_ (n+1)^n+C_(n+2)^n+~...~+C_(n+m-1)^n=C_(n+m)^(n+1)\\ \)

Свойства на биномно разширение:

1. Броят на всички членове на разширението е с едно по-голям от показателя на бинома,

което е равно на n+ 1 .

2. Сума от показателите х и а на всеки член на разширение е равен на биномния показател,

това е (n - m) + m = n .

3. Общ термин на разширението (обозначено T н+1 ) има формата $$T_(n+1)=C_n^m x^(n-m)a^m,~~~~m=0,~1,~2,~...~,~n.$$

Триъгълник на Паскал

Всички възможни стойности на биномни коефициенти (брой комбинации) за всеки биномен показател н може да се напише като безкрайна триъгълна таблица. Такава таблица се нарича Триъгълник на Паскал:

					\(C_0^0\)
				\(C_1^0\)		\(C_1^1\)
			\(C_2^0\)		\(C_2^1\)		\(C_2^2\)
		\(C_3^0\)		\(C_3^1\)		\(C_3^2\)		\(C_3^3\)
	\(C_4^0\)		\(C_4^1\)		\(C_4^2\)		\(C_4^3\)		\(C_4^4\)
\(C_5^0\)		\(C_5^1\)		\(C_5^2\)		\(C_5^3\)		\(C_5^4\)		\(C_5^5\)
	. . .				. . .				. . .

В този триъгълник най-крайните числа във всеки ред са равни на 1. Наистина, \(C_n^0=C_n^n=1\). И всяко неекстремно число е равно на сумата от двете числа от предишния ред над него: \(C_n^m=C_(n-1)^(m-1)+C_(n-1)^(m )\).

По този начин този триъгълник предлага друг (повтарящ се) начин за изчисляване на числата \(C_n^m\):

н = 0									1
н = 1								1		1
н = 2							1		2		1
н = 3						1		3		3		1
н = 4					1		4		6		4		1
н = 5				1		5		10		10		5		1
н = 6			1		6		15		20		15		6		1
н = 7		1		7		21		35		35		21		7		1
н = 8	1		8		28		56		70		56		28		8		1
...				...				...		...				...