Комбинаторика

От Администрация и управление
Направо към навигацията Направо към търсенето

Комбинаториката е математическа наука. Тя е възникнала много отдавна. През годините учени и математици са допринасяли за нейното усъвършенстване. Самата комбинаторика се определя от три основни дяла – пермутация, комбинация, вариация. Всеки от тях се характеризира с набор от формули и правила, чрез които се решават комбинаторните задачи. Комбинаториката се използва не само в сухия си вид - за решаване на задачи, но и в битието. Тя е всеобхватна наука, която се базира изцяло на точни изчисления и разсъждения. Много конструкции и произведения на изкуството са издигнати или направени благодарение на предварително използани комбинаторни зависимости.

История 

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


  • Николо Фонтана ( Тартария) род 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!)

Основни правила

  1. Правило за събиране:

Ако елементът а може да бъде избран по m начина, a елементът b по n различни начина, изборът на а или b може да се извърши по m + n начина. Правилото за събиране може да се обобщи за повече от две множества. Трябва броят на всички обекти да е равен на сбора от броя им в отделните групи.

  1. Правило за умножение:

Ако елементът а може да бъде избран по m начина и при всеки избор на а елементът b може да бъде избран по n начина, то изборът на наредената двойка (а,b) може да стане по m.n начинa. Правилото за умножение може да се обобщи за намиране броя на наредени тройки обекти, наредени четворки обекти.

  1. Пермутации на N–елемента:

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

Формула за броя на пермутациите:

  • Pn = 1.2.3.4....(n - 1)n. Произведението 1.2.3....(n - 1).n е прието да се означава с n! и се четe „ен факториел“
  • Рn = n!
  • 0! = 1
  1. Вариации от N–елемента k-ти клас

Вариациите без повторение на n елемента от k-ти клас (k < n) се наричат такива саединения всяко от които съдържа по k различни елемента от дадените n и се различават едно от друго или по елементите или по реда на елементите. Разликата между вариациите и пермутациите на елементите на някакво множество е единствено в това, че в една вариация не е задължително да участват всички елементи на множеството. Ясно е, че всяка пермутация е вид вариация, докато обратното не е вярно.

Фoрмула за броя на вариациите:

  • Броя на различните вариации от n елемента от k-ти клас се означава с:

V.png


  • броя на вариациите:

Vv.png


  • без повторение от n елемента от k-ти клас е:

Vvv.png


  • От определенията на пермутациите и вариациите следва че пермутациите на n елемента могат да се разглеждат като вариации от n елемента от n-ти клас.
  1. Комбинации от n-елемента k-ти клас

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

Формула за броя на комбинациите:

  • Броят на различните комбинации без повторение от n-елемента от k-ти клас се означава с:

C.png


  • Броя на комбинациите от n-елемента от k-ти клас е:

Cc.png


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

 

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

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


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

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


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

Решение: 6.6 = 36 различни начина може да се хвърлят заровете. Сборът 9 може да се получи при 3 – 6; 6 – 3; 4 – 5; 5 – 4, т.е. в 4 случая.


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

Отг. 16


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

Отг. 216; 18


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

Отг. 30


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

Отг. 12


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

Отг. 30.104.30.30 = 90 000 000

9. Колко са четирицифрените числа, в които се срещат само цифрите 1, 2, 3, 4, 5, 6 и 7 и никоя цифра не се повтаря?

Решение: Първата цифра може да бъде избрана по 7 начина. Да избереме коя да е от дадените цифри,например 7. За останалите три цифри от числото имаме възможност да изберем една от цифрите 1, 2, 3, 4, 5 и 6. Сега можем да приложим резултата от предишната задача - наредена тройка цифри може да се избере от 6 цифри по 6.5.4 начина. Тогава броят на всички разглеждани четирицифрени числа е 7.6.5.4 = 840.


10. Колко прави минават през 8 точки,никои 3 от които не лежат на 1 права?

Решение:

1.png


11. При участия в играта 6 от 49 на Спортния тотализатор играчите попълват фиш с 6 числа от 1 до 49. Колко различни фиша могат да бъдат попълнени?

Решение: Тъй като редът на попълването на числата в един фиш няма значение,то вcеки фиш е една комбинация на 49 елемента от 6-ти клас. съгласно формулата броят на различните фишове е :

2.png


12. Колко 10-цифрени числа могат да се състоят,като всяка цифра се използва веднъж?

Решение: P10 = n! = 10! = 1.2.3.4.5.6.7.8.9.10 = 3628800 P9 = n! = 9! = 1.2.3.4.5.6.7.8.9 = 362880 P10 - P9 = 3628800 - 362880 = 3265920


13. Фирма предлага нов модел автомобили с вазможности за избор на пет различни цвята,три типа двигател и два вида трансмисии. Колко различни модификации има този модел?

Решение: (5,3,2) = 5.3.2 = 30 вида


14. Колко пермутации могат да се състават от:

а) 4 елемента       б) 5 елемента       в) 7 елемента

Решение: a) P4 = n! = 4! = 1.2.3.4 = 6.4 = 24

б) P5 = n! = 5! = 1.2.3.4.5 = 120

в) P7 = n! = 7! = 1.2.3.4.5.6.7 = 5040


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

Решение:

3.png


16. Пресметнете броя на комбинациите (решенията са дадени направо в условието):

а)

4.png


б)

5.png


в)

6.png


г)

7.png


д)

8.png


17. При играта белот се раздават по 8 карти от 32 .Каква е вероятността при едно раздаване играч да получи 4 валета?

Решение:

9.png


18. Каква е вероятноста при игра на белот играч да получи кварта? Тоест четри поредни карти от един вид (спатии,кари,купи или пики)?

Решение:

10.png


19. От колода с 52 карти са истеглени 3 карти. Каква е вероятността те да са 3, 7, А?

Решение:

11.png


20. Колко са възможните комбинации в играта 5 от 35 на спортния тотализатор?

Решение:

12.png


21. Иван забравил последната цифра от телефонния номер на Петър. Каква е вероятността от 2 опита Иван да набере правилния номер.

Отговор: 1/5.


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

Решение: Р7 = 7! = 1.2.3.4.5.6.7 = 5040


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

Решение:

13.png


Визуални примери

Вижте още

Източници

  • Philippe Flajolet, Robert Sedgewick - Analytic Combinatorics, Cambridge University Press, 2008
  • S. E. Payne - Applied Combinatorics, University of Colorado, 2003
  • Albert Nijenhuis, Herbert S. Wilf - Combinatorial Algorithms, Academic Press Inc, 1978
  • Linfan Mao - Combinatorial Geometry with Application to Field Theory, InfoQuest, 2009
  • Deirdre Haskell, Anand Pillay, Charles Steinhorn - Model Theory, Algebra and Geometry, Cambridge University Press , 2000
  • Louis J. Billera, at al. - New Perspectives in Algebraic Combinatorics, Cambridge University Press, 1999
  • Anthony Hilton and John Talbot - Surveys in Combinatorics
  • Albert Nijenhuis and Herbert Wilf - Combinatorial Algorithms for Computers and Calculators ©1978-2007
  • Edward A. Bender and S. Gill Williamson - Foundations of Combinatorics with Applications ©2006 468 pages
  • Tom Siegfried - A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature ©2006
  • Jacob E. Goodman, János Pach, Emo Welzl - Combinatorial and Computational Geometry ©2005
  • M. Lothaire - Applied Combinatorics on Words ©2005 626 pages
  • Roger A. McCain - Game Theory: A Nontechnical Introduction to the Analysis of Strategy ©2004
  • M. Lothaire - Algebraic Combinatorics on Words ©2002 518 pages
  • Pavel Bleher, Alexander Its, editors - Random Matrix Models and Their Applications ©2001 496 pages
  • Philip J. Koopman - Architecture for Combinator Graph Reduction ©1990 176 pages

Външни препратки

Взето от „https://wiki.basaga.org/index.php?title=Комбинаторика&oldid=35“.