Комбинаторика Исторически бележки



Дата25.07.2016
Размер122.31 Kb.
#5530
Комбинаторика
Исторически бележки

Елементи на комбинаториката са известни от дълбока древност. Някои известни математици оставили трудове по комбинаторика са:


Николо Фонтана ( Тартария) род 1500 в Бершиа – поч. 14.12.1557г във Венеция. Поради крайната си бедност като момче е принуден да краде книги, за да се научи да чете. След това се издига постепенно до частен учител, изчислител и професор във Венеция. Освен някои елементи на комбинаториката той намира и метод за изчисляване на кубичното уравнениеот вида х3 + ахаb = 0.
Блез Паскал род.19.06.1623 в Клермон Феран – поч. 19.08.1663 в Париж. Обучаван от баща си в детска възраст. През 1641 построява първата известна сметачна машина. От същата година се присъединява към янсенистите и живота му е определен от фанатична религиозна вяра. Паскал и Ферма се считат за създателите на теорията на вероятностите. Паскал първи използва термина “Комбинация”. Блез Паскал има и философски съчинения.
Пиер дьо Ферма род. 17.08.1601 в Бомон дьо Ломаж – поч.12.01.1665г в Кастр. Син на търговец на кожи. Следва право, след което купува място на съветник в Тулузкия парламент през 1630г. Умира неочаквано при служебно пътуване. За неговите изследвания в областта на математиката се съди от писмата му до Паскал. Той се счита за един от създателите на аналитичната геометрия.
Готфрид Вилхелм Лайбниц, род.1.07.1646 в Лайпциг – в семейство на професор, поч.14.11.1716г. в Хановер. Следва философия в Лайпциг от 1661, от 1664 – право и защитава докторска дисертация през 1667 в Алтдорф близо до Нюрнберг. През 1672 г. е натоварен с политическа мисия и заминава за Париж където се занимава изключително с математика. Енциклопедист. Написаният от него “Трактат на комбинаторното смятане” - 1666 се счита за първия цялостен труд в тази област.
Якоб Бернули, род.27.12.1654г. в Базел – поч.16.08.1705г. в Базел. Следвайки теология той тайно изучава математика. В “Изкуство на предположенията” са поставени основите на теория на вероятностите. Бернули е първият математик, който разбира и доразвива смятането на Лайбниц. В свои труд от 1713, той затвърждава понятията “пермутация”, “вариация”, въведени за пръв път от белгийският математик Такс през 1656г.
Кристиян Крамп – въвежда означението факториел през 1808г. (1.2.3.4.....n = n!)
Множества
Най показателни примери са множествата от числата – естествените числа – N = ; целите числа – Z = ;

Като пример може да даден и учениците от един клас А =


Определение: Множества, които имат краен брой елементи, се наричат “крайни”. Например: множеството от учениците в един клас.

Множества, които имат неизброим брой елементи, се наричат “безкрайни”. Например множествата от числата.

Множество, което няма нито един елемент се нарича “празно” и се отбелязва с .

Две множества са равни, ако съдържат едни същи елементи.

Едно множество А е подмножество на множеството В, ако в множетвото В участват всички елементи на множеството А.

Множества, които имат общи елементи се наричат пресичащи се.

Множества, които нямат общи елементи се наричат непресичащи се. .

Ако , то може да образуваме разликата им С = В – А


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

  1. Ако , то е крайно множество и


Съединения

Пример: Ако е дадено едно множество

А = и множеството , то новото множетсво В се нарича съединение.

Множеството В е съединение на 7 елемента от втори клас.


Правила:

  1. За събиране на съединения. Ако елемент х може да се избере по n различни начина, а елемент y по m , то изборът на x или y може да се извърши по n + m начина.

  2. За умножение на съединения. Ако елемент х може да се избере по n различни начина и при всеки такъв избор елемент y може да се ибере по m различни начина, то изборът на (x, y) може да се извърши по n.m начина.

Задачи за подготовка:




  1. Oт град А до град В водят 6 пътя, а от В за С – 3 пътя. Определете по колко начина може да се отиде от А до С.

Решение: Прилагаме правилото за умножение на съединения и се получава 6.3 = 18

  1. Трябва да се определи отбор по тенис от един мъж и една жена, които да представят България. Избора може да се направи измежду 21 тенисистки и 15 тенисисти. Колко различни такива двоики е възможно да се образуват.

Решение: Прилагайки правилото за умножение на съединения, ще се получи 21.15 = 315.

  1. Хвърлят се два различни зара. По колко различни начина могат да се хвърлят и в колко случая сборът от точките ще е 9 ?

Решение: 6.6 = 36 различни начина може да се хвърлят заровете.

Сборът 9 може да се получи при 3 – 6; 6 – 3; 4 – 5; 5 – 4, т.е. в 4 случая.


Задачи за самостоятелна работа:
1 зад. Към един връх водят 4 пътеки. По колко начина може турист да се качи и слезе от този връх?

Отг. 16


2 зад. Хвърлят се три различни зара. Колко различни резултата могат да се получат ? В колко случаи сборът от цифрите ще е 9 ?

Отг. 216; 18

3 зад. В десети клас се учат 10 предмета. Одобрените от МОН (Министерството на образованието и науката) са по 3 за всеки предмет. По колко различни начина може да се избере един набор от учебници?

Отг. 30


4 зад. Трябва да изпратим три различни пратки от София за Варна. Фирмата ни работи с три куриерски бюра. Колко различни възможности имаме за това?

Отг. 12


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

Отг. 30.104.30.30 = 90 000 000


Комбинации
За да покажем разликата между пермутация, вариация и комбинация, ще направим интерпретация на една задача:

  1. Пет съученика Ани, Борис, Васил, Иван и Мария посетили един много интересен филм за които едва си купили билети. Иван купил билетите и те влезли заедно като местата били точно отпределени. По колко различни начина могат да седнат.

  2. Пет съученика Ани, Борис, Васил, Иван и Мария имали свободен час и решили да влезат да гледат филм, които очевидно не се радвал на голям интерес. Писнали ги в киното като им казали, че 3 ред целият е свободен. По колко различни начина могат да седнат съучениците, ако се знае, че реда се състой от 12 стола.

  3. От група от 12 ученика трябва да изберем 5. По колко различни начина могат да се изберат.

При записването на формулите, ще използваме понятието факториел – това е произведението от първите n естествени числа. Озн. n! = 1.2.3.4…..n. Дефинираме 0! = 1.

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

Pn=n!
Решението на зад. 1 е Р5= 5! = 1.2.3.4.5 = 120
Вариация на n елемента от k клас се нарича всяка подредба на k члена от различни елементи. Вариацията също може да е с или без повторение. Тук разглеждаме само без повторение.


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


Решение на 3 зад.
Задачи за подготовка:
Всички разглеждани примери са без повторение на числа.


  1. Колко различни четирицифрени числа могат да се образуват от цифрите 1, 2, 3 и 4.

  2. Колко различни четирицифрени числа могат да се образуват от цифрите 0, 2, 4, и 6.

  3. Колко различни четирицифрени числа могат да се образуват от цифрите 1, 2, 3, 4, 5, и 9.

  4. Колко различни четирицифрени числа могат да се образуват от цифрите 0, 1, 3, 5, 6 и 8.

  5. Ако имаме номерирани 5 топки с цифрите от 1 до 5 и изтегляме три от тях. Колко различни възможности имаме.

Решение:1) Р4 = 4! = 1.2.3.4 = 24

2)Р4Р3 = 4! – 3! = 24 – 6 = 18, защото, ако нулата е на първо място то числото не е четирицифрено.

3)

4)

5)


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

При тото 6/49 тя е

При тото 5/35

И при 6/42 е

6) Да се определи колко прави са определени от 4 точки.

Решение: Имаики впредвид, че всяка права се определя от две точки, то



  1. Да се определи в колко точки се пресичат 6 прави, които не минават през една точка и никои две не са успоредни.

Решение:

  1. Да се определи в колко прави се пресичат 10 равнини, 3 от които минават през една права, а останалите са в общо положение.

Решение:

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

1 зад. Пресметнете:

а) Р6

б) V106

в) С124


отг.а) 6! = 720; б) в)
2 зад. Решете уравненията:

а)

б)

в) , ако

г)

д)

е)

ж)


отг. а) 5; б) 4; в) 1; г) 12; д) 5; е) 12; ж) 8

3 зад. Колко различни петцифрени числа могат да се запишат с цифрите 1, 2, 3, 6, 9 без повторение на цифра ?


отг. Р5 = 5!
4 зад. Колко различни десет цифрени числа могат да се запишат, без да се повтарят?
Отг. Р10 – Р9 = 9.9!
5 зад. В компютърната зала в нашето училище има 13 компютъра и нашата група по информатика е от 13 ученика. Всяко компютърно място е номерирано.

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

б) Ако един ден двама души отсъстват, то по колко различни начина ще седнем?
Отг. а) Р11 = 11!; б)
6 зад. Група от 5 момчета и 6 момичета от нашият клас се записа на спортни танци.

а) По колко различни начина можем да образуваме танцова двоика ?

б) Ако едно момиче се отказва, а едно си избира точно един партньор, то колко различни двоики могат да се образуват ?
отг. a) 30 б) 16
7 зад. Да се определи колко прави са определени от:

а) 3 точки, които не лежат на една права;

б) 7 точки, от които никои три не лежат на една права;

в) 10 точки, ако 4 от тях лежат на една права, а другите са в общо положение.


Отг. а) ; б) ; в)
8 зад. Да се определи в колко точки се пресичат:

а) 5 прави, никои три от които не минават през една точка и никои две от които не са успоредни;

б) 7 прави, 3 от които минават през една точка, а останалите са в общо положение;

в) 8 прави, 3 от които са успоредни помежду си, а останалите са в общо положение.


Отг. a) ; б) ; в)

Теория на вероятностите
Всяко действие което осъшествяваме има вероятност да е успешно или неуспешно.

Самото действие ще наричаме събитие.

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

Събитие което може да се случи, а може и да се случи, се нарича случайно.

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

Две събития са съвместими, ако могат да се сбъднат при провеждането на един и същи опит.

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

Обединение на две събития А и В



А

В

С

0

0

0

0

1

1

1

0

1

1

1

1

Сечение на две събития А и В

А

В

С

0

0

0

0

1

0

1

0

0

1

1

1

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


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

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

За всяко събитие А и В са в сила следните свойства:

1)

2) , където е противоположното събитие.

3) Ако , то

Теорема за събиране на вероятностите:



  1. Ако две събития са несъвместими, то

  2. За всеки две събития А и В е в сила

Теорема за умножение на вероятности:

За всеки две независими събития А и В е в сила


Задачи за подготовка:


  1. Хвърлят се зар. Каква е вероятността да се появи 3 – ка .

Решение: Ще използваме формулата за класическа вероятност ,

m е 1, т.к. има една 3 – ка , а n е 6. Ако приемем, че А е вероятността да се падне 3, то Р(А) =

2) В една кутия има 3 бели, 4 черни, 5 червени и 6 сини топки. По случаен начин се изважда една топка.

а) Каква е вероятността извадената топка да е бяла?

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

в) Каква е вероятността след като сме извадили бяла топка, да извадим отнова бяла топка?

Решение: а) Нека събитието А е да сме извадили бяла топка.



б) Нека събитието В е извадената топка да е черна, тогава вероятността е

в) След като вече е извадена една бяла топка, то благоприятните изходи ще намалеят с един и


  1. Да се намери каква е вероятността при изтегляне на карта от една колода от 52 карти да се изтегли:

а) 10 – ка;

б) Асо каро;

в) Асо или 10 – ка;

г) След като при първото изтегляне се е паднало Асо, втори път да изтеглим отново Асо.

Решение:

а) В една колода имаме четири 10 – ки, от което следва, че

б) В една колода имаме четири Аса, от което следва, че

в) Събитията А = да се изтегли 10 – ка, и събитието В = да се изтегли асо, са несависими, тъй като сбъдването на едното изключва другото, то ще приложим теоремата за сбор на независими събития, а именно

г) Ще използваме теоремата за произведение, защото за да се сбъдне събитието С = изтегляне на асо, след като вече е изтеглено, нека означим с М = изтеглени са две аса



  1. Ученик от 10 клас останал на поправителен изпит по математика. Учебника съдържа 24 урока, а той успял да научи добре 15 от тях, ако изпитния билет включва задължитело материал от три урока, каква е вероятността и трите да ги е научил?

Решение:

  1. Хвърлят се едновременно 10 монети. Каква е вероятността точно 6 от тях да показват “герб”.

Решение: Благоприятните възможности са , а всички възможни изходи са 210 = 1024, от където се получава, че

  1. От колода от 52 карти са изтеглени 5 каква е вероятността сред изтеглените 5 карти да има поне едно асо.

Решение: Използвайки второто свойство, можем да намерим вероятността на противоположното събитие от изтеглениете 5 карти няма нито едно асо.



=>
Задачи за самостоятелна работа:
1 зад. Зар се хвърля три пъти. Каква е вероятността на събитието:

А = При хвърляне се пада 6 – ца;

В = След като първият път се е паднала 6 – ца и второто хвърляне също да е 6 – ца;

С = И трите хвърляния да са щестици;

D = При трите хвърляния да се падне 1 или 2;

Е = Сборът на точките от трите хвърляния да е 9;

F = Сборът от точките в трите хвърляния да е по малка от 16;

G = Сборът от точките да се дели на 2, но да не се дели на 3.


Отг. ; ; ; ; ; ;
2 зад. Разполагаме с колода от 52 карти. Каква е вероятността на събитието:

А = Да изтеглим дама пика;

В = Да изтеглим поп;

С = Да изтеглим четири аса;

D = Да изтеглим поп след като сме изтеглили асо;

E = При три последователни тегления, да изтеглим поне една десятка;

F = Да не изтеглим дама;
Oтг. ; ; ; ; ; ;

3 зад. В една кутия имаме 9 бели, 12 червени и 15 зелени топки. Каква е вероятността на събитието:

А = при изтегляне на една топка тя да е зелена;

В = при изтегляне на две топки те да са бели;

С = при изтегляне на три топки те да са с различни цветове

D = при изтегляне на пет топки има поне една бяла;

E = при изтегляне последователно на три топки, първат да е бяла, втората – червена , а третата – зелена.

Отг. Р(А) = ; Р(В) = ; Р(С) = 3.; Р(D) = 1 – ; Р(Е)=


4 зад. Хвърляме 20 монети. Каква е вероятността на събитието:

А = Всички да са “герб”;

В = Половината да са “герб”

С = На две от тях да има “герб”


Отг.
5 зад. Попълвам 10 фиша на тото 6 от 49. Каква е вероятността да спечеля?

Отг.


6 зад. Попълвам 10 фиша на Евроспорт. Във фиша са посочени 16 среши и за всяка е възможен един от три резултата – 1, Х, 2.. Каква е вероятността да спечеля ?
отг.


Сподели с приятели:




©obuch.info 2024
отнасят до администрацията

    Начална страница