Комбинаториката: изкуството да броим невъзможно големи неща
Комбинаториката:
изкуството да броим невъзможно големи неща
Колко мелодии могат да се съставят от осем ноти? Колко различни осемсимволни пароли са възможни? Колко начина има да наредите книгите на рафта? Комбинаториката е клонът на математиката, който отговаря на тези въпроси — и в процеса разкрива, че Вселената е непредставимо по-голяма, отколкото изглежда.
Представете си, че сте организатор на музикален фестивал и трябва да наредите 10 изпълнителя на сцена. Колко различни наредби са възможни? Отговорът е 3 628 800. Ако сменяте наредбата всяка секунда, ще ви трябват над 40 дни, за да изпробвате всички. Ако добавите още двама изпълнителя — 12 общо — вече имате почти 480 милиона варианта. С 20 изпълнителя числото вече надвишава броя на секундите, изминали от Големия взрив досега.
Тази лавинообразна експлозия на възможностите е в сърцето на комбинаториката — математическата дисциплина, която изучава броенето, наредбите, изборите и разпределенията на крайни обекти. Тя е едновременно изненадващо практична (стои зад криптографията, генетиката, логистиката и алгоритмите) и изненадващо дълбока (някои от най-трудните открити проблеми в математиката са комбинаторни).
Математикът Федерико Ардила, известен и като диджей, описва комбинаториката като „изкуството да търсиш полезни отговори, скрити сред непредставимо голям брой възможности". Именно тази формулировка улавя парадокса на дисциплината: задачите изглеждат прости за задаване, но отговорите могат да бъдат астрономически — и намирането на правилния подход изисква дълбоко разбиране на структурата.
Редът има значение: пермутациите
Нека започнем с основния въпрос: по колко начина могат да бъдат наредени дадени обекти? Ако имате пет книги и искате да ги наредите на рафт, отговорът е 120. Ако имате десет — 3 628 800. Двадесет книги дават число с 18 цифри. Тези наредби се наричат пермутации.
Интуицията зад тях е проста: имате \(n\) избора за първото място, \(n-1\) за второто (защото един обект вече е заел първото място), \(n-2\) за третото и така нататък. Умножете всичко и получавате:
\[n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1.\]Символът \(n!\) се чете „\(n\) факториел" и расте изключително бързо. Нека да го видим нагледно:
За сравнение: оценките за броя на атомите в наблюдаемата Вселена са от порядъка на \(10^{80}\). Броят на пермутациите на 60 обекта надвишава тази стойност. Със 100 обекта навлизаме в числа, за които нямаме дори интуитивна физическа представа.
Но пермутациите не трябва да включват всички обекти. Ако от 8 участника в турнир трябва да наредим само подиума (1-во, 2-ро, 3-то място), броят на наредбите е:
\[P(8, 3) = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336.\]Логиката е следната: имаме 8 избора за първо място, след това 7 (един вече взет) и 6 за трето. Разделянето с \(5!\) „спира" факториела точно там, където ни трябва.
Редът няма значение: комбинациите
Понякога обаче редът не е важен. Ако трябва да изберете 3 студенти от 8 за работна група, екипът „Алиса, Боб и Чарли" е същият като „Боб, Чарли и Алиса". Не съществува „първо", „второ" и „трето" място — просто трима избрани. Тези избори се наричат комбинации.
Броят им е по-малък от пермутациите, защото много пермутации отговарят на един и същ избор. Конкретно: 3 избрани обекта могат да бъдат наредени по \(3! = 6\) начина, така че:
\[C(8, 3) = \frac{P(8, 3)}{3!} = \frac{336}{6} = 56.\]Общата формула е:
\[C(n, k) = \binom{n}{k} = \frac{n!}{k!\,(n-k)!}.\]Числото \(\binom{n}{k}\) се чете „\(n\) над \(k\)" или „биномен коефициент". То е едно от фундаменталните числа в математиката — появява се в биномната теорема, в теорията на вероятностите, в триъгълника на Паскал и в редица теореми на алгебрата и анализа.
Разграничението между пермутации и комбинации: всеки избор на 3 от 5 елемента отговаря на 6 пермутации (3! наредби), затова \(C(5,3) = P(5,3) / 3! = 60/6 = 10\).
Средновековният ислям и раждането на комбинаториката
Комбинаториката не е изобретение на съвременността. Нейните корени се намират в много различни цивилизации и епохи. Сред ранните пионери особено изпъква средновековният ислямски свят.
Арабските учени от VIII до XIII век работят интензивно върху задачи на броенето в контекста на лингвистиката и музиката. Въпросът „колко думи от \(k\) букви могат да се образуват от дадена азбука?" е не просто теоретичен — той има пряко отношение към разбирането на Корана и арабската поезия. Броенето на ритмичните схеми в поезията, на допустимите думи в езика, на мелодичните модуси в музикалната теория — всичко това изисква систематично мислене за пермутации и комбинации.
Особено интересен е арабският принос към комбинаторните идентичности — правила, свързващи различни начини за броене на едно и също нещо. Изследователи установяват, че много от тях са открити или систематизирани в учените среди на ислямския свят векове преди да бъдат преоткрити в Европа. Техниката за изработване на пискюли от копринени нишки с различни цветове, например, е превърната в математическа задача: по колко начина могат да се наредят нишките?
Колко мелодии са възможни?
Нека направим конкретна оценка, която ще ни отвори очите за мащаба на комбинаторните числа.
Ако разгледаме западната музика, тя използва 12 различни тона в рамките на октавата. Добавете към това 8 различни ритмични продължителности за всяка нота (цяла, половина, четвъртина...). Ако дефинираме „мелодия" като последователност от 16 ноти, всяка с фиксирана височина и продължителност, броят на различните мелодии в рамките на този математически модел е:
\[(12 \times 8)^{16} = 96^{16} \approx 5{,}2 \times 10^{31}.\]Това е число с 32 цифри — много повече от броя на звездите в наблюдаемата Вселена (около \(10^{24}\)). Сред тях огромното мнозинство никога не е звучало човешко ухо. Вероятно никога и няма да прозвучи.
Но тук идва същественото: не всички тези мелодии звучат добре. Не всички са „музикални" в какъвто и да е смисъл. Задачата на композитора — или на музикалния алгоритъм — е да се ориентира в това огромно пространство от възможности и да намери онова малко подмножество, което звучи хармонично, смислено и красиво. Това е комбинаторика в нейната приложна форма.
Точно тази идея описва Федерико Ардила — математик в Университета на Сан Франциско и активен диджей. В интервю за Quanta Magazine той разказва как математиката и музиката работят по сходен начин: „И в двете търсиш структура в огромно пространство от възможности. Намирането на красивото в безкрайния хаос е проблемът и там, и тук."
Триъгълникът на Паскал и скритите симетрии
Биномните коефициенти \(\binom{n}{k}\) крият поразително много симетрии. Когато ги наредим в триъгълник — познат като триъгълникът на Паскал, макар Паскал да не е негов автор (арабски и китайски математици го описват векове по-рано) — се появяват закономерности, видими с просто око:
Всяко число в триъгълника е сумата от двете числа непосредствено над него. Ред \(n\) съдържа точно биномните коефициенти \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\). Сумата на всеки ред е \(2^n\).
Свойствата на триъгълника са безброй. Сумата на всеки ред е степен на двойката. Диагоналите дават триъгълните числа, кубическите числа, числата на Фибоначи. Във всеки ред с прост номер всички числа, различни от крайните 1, се делят на номера на реда. Ако оцветите четните числа в един цвят и нечетните — в друг, се появява фракталът на Серпински. Всичко това е скрито в простичката схема за добавяне на две съседни числа.
Пътища в решетка и изоморфни задачи
Едно от най-елегантните приложения на комбинаториката е броенето на пътища в решетка. Представете си, че сте на пресечка в град с правоъгълни улици (като Манхатън). Искате да стигнете от ъгъла (0,0) до ъгъла (3,2) — т.е. 3 блока на изток и 2 блока на север. Можете да се движите само на изток или на север. Колко различни маршрута имате?
Ключовото наблюдение: всеки маршрут е последователност от 5 стъпки, от които точно 3 са „Изток" и точно 2 са „Север". Броят на маршрутите е броят на начините да изберете кои 2 от 5-те стъпки ще бъдат „Север":
\[\binom{5}{2} = \frac{5!}{2!\,3!} = 10.\]Ако решетката е \(m \times n\), отговорът е \(\binom{m+n}{m}\). Но тук идва нещо по-дълбоко.
Примери за задачи, изоморфни на броенето на пътища в решетка:
- Наредби с повторения — колко думи можете да съставите от буквите на „МАТЕМАТИКА"?
- Разпределяне на еднакви топки в кутии — по колко начина 7 еднакви топки могат да се сложат в 3 кутии?
- Последователности от тренировки — 4 упражнения за крака и 6 за ръце могат да се наредят по \(\binom{10}{4} = 210\) различни начина.
- Случайно движение — обект, движещ се случайно нагоре или надясно с равна вероятност, достига дадена точка с вероятност \(\binom{m+n}{m} / 2^{m+n}\).
Разширяване в 3D: кубична решетка
Предимството на този начин на описание — маршрутите като наредби на букви — е, че лесно се обобщава. При тримерна решетка \(5 \times 5 \times 5\) — движение само напред, нагоре или надясно — трябва да направим 5 стъпки от всеки тип, общо 15 стъпки. Броят на пътищата е:
\[\frac{15!}{5!\,5!\,5!} = 756\,756.\]Над три четвърти милиона пътища в малък куб! Методът работи за всяко измерение: в \(k\)-мерна решетка с \(n_i\) стъпки по всяка ос, броят на пътищата е многочленният коефициент \(\frac{(n_1+\ldots+n_k)!}{n_1!\,\cdots\,n_k!}\).
Многочленните коефициенти и принципът на умножението
Комбинаториката разполага с мощен инструмент, наречен принцип на умножението (или правило на продукта): ако едно действие може да се извърши по \(m\) начина, а независимо от него друго действие — по \(n\) начина, то двете заедно могат да се извършат по \(m \cdot n\) начина.
Принципът изглежда очевиден, но приложенията му често съвсем не са. Нека разгледаме следната задача: имаме три комисии, всяка с по 5 членове, и трябва да изберем председател, заместник-председател и секретар — по един от всяка комисия. Колко различни ръководства са възможни? По принципа на умножението: \(5 \times 5 \times 5 = 125\). Ако променим условието и разрешим изборът да се прави измежду всички 15 души, но поискаме председателят и заместник-председателят да са от различни комисии, задачата вече става по-сложна — и точно тогава комбинаториката показва своята дълбочина.
Топчета в кутии и принципът на гнездото
Комбинаториката изучава не само броенето, но и граничните теореми — резултати, казващи „каквото и да се случи, нещо определено ще бъде вярно". Най-простият от тях е принципът на Дирихле (или принципът на гнездото): ако имате \(n+1\) топчета и \(n\) кутии, поне една кутия съдържа поне две топчета.
Звучи тривиално, но приложенията са далеч от тривиални. Ако в София живеят повече от 365 000 души, то поне двама са родени на един и същи ден от годината. Ако имате 13 карти от тесте от 52, то поне 4 са от един и същи цвят. Ако изберете 5 точки вътре в равностранен триъгълник със страна 2, поне 2 от тях са на разстояние най-много 1 една от друга.
В теорията на графите, в компютърните науки и в криптографията принципът на Дирихле е основен инструмент за доказателства. Той стои зад доказателствата, че никоя хеш функция не може да бъде инективна (всяко компресиране неизбежно създава „сблъсъци"), и зад анализа на рождения парадокс — контраинтуитивния факт, че в група от само 23 души вероятността двама да имат един рожден ден е над 50%.
Парадоксът с рождените дни: броенето на двойки
Колко души трябват в една стая, за да е вероятно поне двама от тях да имат общ рожден ден? Повечето хора интуитивно казват „около 180" (половината от 365 дни). Верният отговор е само 23. При 23 души вероятността да има съвпадение е над 50%. При 60 души е над 99%.
Защо е толкова малко? Ключът е комбинаторен: не сравняваме всеки човек с конкретен рожден ден, а търсим съвпадение между произволни двойки. При 23 души броят на уникалните двойки е: \[\binom{23}{2} = \frac{23 \cdot 22}{2} = 253.\] 253 двойки, всяка с малка, но ненулева вероятност за съвпадение — и кумулативният ефект надхвърля 50%.
• Вторият може да е роден на всеки от останалите 364 дни: вероятност \(364/365\).
• Третият — на някой от 363: вероятност \(363/365\).
• И т.н.
Вероятността всички \(n\) да имат различни рождени дни е: \[P(\text{без съвп.}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365-n+1}{365}.\] При \(n = 23\) тази стойност пада под 0,5, т.е. вероятността за поне едно съвпадение надхвърля 50%.
Парадоксът с рождените дни не е само забавна загадка — той има пряко приложение в криптографията. При хеш функция с \(M\) различни изходни стойности, атакуващ може да намери два различни входа с един и същ изход (т.нар. сблъсък) след около \(\sqrt{M}\) опита — много по-малко от \(M\). Именно затова SHA-1 (160-битов изход, \(M \approx 10^{48}\)) изисква само около \(\sqrt{10^{48}} = 10^{24}\) опита за намиране на сблъсък. Тази уязвимост — наречена birthday attack — е причината съвременните хеш функции да използват 256 или 512 бита.
Деранжирания: когато никой не получава своето
Представете си, че сте в ресторант и гардеробиерът губи всички билетчета. Когато гостите си тръгват, той раздава шапките напълно случайно. Каква е вероятността никой от \(n\) гости да не получи собствената си шапка? Тази класическа задача — известна като задачата за шапките или problème des rencontres — е поставена за пръв път от Пиер Реймон дьо Монморт през 1708 г. и решена от него пет години по-късно.
Пермутация, при която никой елемент не е на първоначалното си място, се нарича деранжиране. Броят на деранжиранията на \(n\) елемента се бележи с \(!n\) (чете се „субфакториел на \(n\)") и се изчислява чрез принципа на включванията-изключванията:
\[!n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right).\]Забележете, че за малки стойности получаваме: \(!1 = 0\), \(!2 = 1\), \(!3 = 2\), \(!4 = 9\), \(!5 = 44\). За \(n = 4\) от общо \(4! = 24\) пермутации само 9 са деранжирания.
Деранжиранията имат много практически приложения. Secret Santa (жребий, при който всеки подарява на точно един член от групата, без да подарява на себе си) е точно деранжиране: търсим пермутация без фиксирани точки. Алгоритъмът за генериране на такъв жребий трябва внимателно да избягва ситуациите, в които някой изтегля собственото си име. При 10 участника вероятността случаен жребий да е валиден Secret Santa е около 36,8%.
Деранжиранията са свързани и с полиномите на топовете в шахматната комбинаторика, и с криптографски шифри без фиксирани точки (за да се избегне ситуацията, в която буквата се кодира сама в себе си — именно такава структурна слабост е била сред причините Enigma да бъде разбита).
Свръхпермутациите: загадка от интернет
Ако мислите, че пермутациите са напълно разбрана тема, историята на свръхпермутациите ще ви изненада. Задачата е следната: каква е най-късата последователност от символи, която съдържа като непрекъснат фрагмент всяка пермутация на \(n\) различни символа?
За \(n = 1\): просто „1". За \(n = 2\): „121" съдържа и „12", и „21" — 3 символа. За \(n = 3\): „123121321" съдържа всичките шест пермутации на „123" — 9 символа. Колко символа трябва за \(n = 4\) (24 пермутации)?
В продължение на десетилетия математиците знаят само горни граници. Долните граници — т.е. доказателства, че не може да се направи по-кратко — са много по-трудни. Ситуацията се променя по невероятен начин.
През 2011 г. в онлайн форум, посветен на аниме, потребител с псевдоним Anonymous публикува математическо доказателство за долната граница на свръхпермутациите — и то се оказва вярно и нетривиално. Никой не знае кой е анонимният автор. Идентичността му остава загадка и до днес.
После, през 2018 г., австралийският научнофантастичен писател Грег Иган — известен с математически прецизните си романи — публикува в Twitter доказателство на горната граница за свръхпермутациите, което е значително по-тясно от всичко познато дотогава. Математиците от цял свят анализират доказателството за няколко дни и потвърждават: то е вярно.
Броенето в реалния свят: алгоритми и комбинаторна оптимизация
Комбинаториката е в сърцето на голяма част от съвременните алгоритми. Логистичните компании трябва да намерят оптимален маршрут за доставки: ако има 20 точки за доставка, маршрутите са \(19!/2 \approx 6 \times 10^{16}\) — повече, отколкото може да изпробва дори суперкомпютър. Spotify трябва да нареди милиони песни в плейлисти по начин, задоволяващ предпочитания на потребителите. Фармацевтичните компании трябва да изберат кои молекули да тестват от огромно пространство от потенциални лекарства.
Решаването на тези задачи „с груба сила" (проверка на всички варианти) е невъзможно. Затова компютърните учени разработват алгоритми за комбинаторна оптимизация — умни методи, които търсят добро решение в огромното пространство от възможности, без да проверяват всичко. Сред тях са:
- Динамично програмиране — разлага голяма задача на по-малки подзадачи, запомня решенията им и ги използва повторно.
- Алчни алгоритми — при всяка стъпка правят локално оптималния избор с надежда, че той ще доведе до глобален оптимум.
- Стохастично търсене — случайно разглеждат части от пространството, насочвани от хевристики.
- Алгоритми за апроксимация — намират решение, гарантирано в рамките на определен процент от оптималното.
Много от най-важните нерешени проблеми в компютърните науки са именно комбинаторни. Известният въпрос „P = NP?" пита дали задачи, чиито решения са лесни за проверка, са и лесни за намиране. Ако P ≠ NP (каквото повечето учени смятат), то много комбинаторни проблеми вероятно нямат ефективно решение. Именно идеята, че някои задачи са лесни за проверка, но трудни за решаване, стои в основата на едни от най-важните въпроси в теоретичната информатика и криптографията.
Броене с припокриване: принципът на включванията-изключванията
Понякога се налага да броим обекти, притежаващи поне едно от няколко свойства. Ако имате 100 числа от 1 до 100 и искате да преброите тези, делящи се на 2 или на 3, не можете просто да съберете делящите се на 2 (50 числа) и делящите се на 3 (33 числа), защото числата, делящи се на 6, ще ги преброите два пъти. Правилният отговор е:
\[|A \cup B| = |A| + |B| - |A \cap B| = 50 + 33 - 16 = 67.\]Това е принципът на включванията-изключванията. Той се обобщава за произволен брой множества и е основен инструмент в комбинаториката, теорията на вероятностите и теорията на числата. Чрез него се доказва формулата за функцията на Ойлер (броят на числата до \(n\), взаимно прости с \(n\)), която стои в основата на RSA криптографията.
Числата на Каталан: скоби, дървета и полигони
Колко начина има да поставите правилно \(n\) двойки скоби? За \(n = 3\) двойки скоби, валидните наредби са: ((())), (()()), (())(), ()(()), ()()() — точно 5. За \(n = 4\) са 14. За \(n = 5\) са 42. Тези числа принадлежат на една от най-прочутите редици в комбинаториката — числата на Каталан.
Формулата е: \[C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}.\]
Първите числа на Каталан са: 1, 1, 2, 5, 14, 42, 132, 429, 1430... Те нарастват приблизително като \(4^n / (n^{3/2} \sqrt{\pi})\) — много по-бавно от факториела, но все пак доста бързо.
Историята на числата е интересна сама по себе си. Леонард Ойлер пръв ги изследва в контекста на триангулирането на полигони (1751). Китайският математик Минганту ги открива независимо около 1730 г. Европейското им именуване е по Йожен Шарл Каталан (1814–1894), който ги изследва в контекста на правилното скобуване.
Петте валидни наредби на 3 двойки скоби — и всяка от тях отговаря на структурно идентична задача за дървета, пътища в решетка и триангулиране.
Числото \(C_n\) се появява в толкова много на пръв поглед несвързани задачи, че изследователят Ричард Стенли посвещава цял раздел в своята „Enumerative Combinatorics" с 66 различни интерпретации на числата на Каталан. Сред тях:
- Балансирани скоби — \(C_n\) е броят на правилно вложените последователности от \(n\) двойки скоби.
- Двоични дървета — \(C_n\) е броят на структурно различните двоични дървета с \(n+1\) листа.
- Триангулиране на полигон — \(C_n\) е броят на начините да разделите \((n+2)\)-ъгълник на триъгълници, свързвайки върховете с непресичащи се диагонали.
- Пътеки под диагонала — \(C_n\) е броят на монотонните пътища в \(n \times n\) решетка, които не пресичат главния диагонал.
- Думи на Дик — последователности от \(n\) единици и \(n\) нули, при които всеки начален сегмент съдържа поне толкова единици, колкото нули.
Рекурентната формула \(C_{n+1} = \sum_{k=0}^{n} C_k \cdot C_{n-k}\) показва дълбока самоподобна структура: задача с \(n+1\) елемента се разпада на две подзадачи с общ размер \(n\). Тази структура е основна при анализа на алгоритми за парсване на изрази в компилаторите, за обхождане на двоични дървета и за оптимално умножаване на матрици.
Генерирането на случайни наредби: Spotify, тестето карти и алгоритъмът на Фишер-Йейтс
Как се разбърква тесте карти по наистина случаен начин? Как алгоритъмът за „разбъркване" на Spotify избира следващата песен? Зад тези въпроси стои комбинаторен алгоритъм.
Наивният подход — избери случайна позиция за всяка карта — не работи. Той поражда неравномерно разпределение. Правилният алгоритъм е алгоритъмът на Фишер-Йейтс (1938, усъвършенстван от Дурстенфелд 1964):
- Стартирай с пълния списък.
- За всяка позиция \(i\) от края към началото: избери случайна позиция \(j\) с \(j \leq i\) и размени елементите на позиции \(i\) и \(j\).
Резултатът: всяка от \(n!\) пермутации е еднакво вероятна. Алгоритъмът работи за \(O(n)\) стъпки. Той е едновременно оптимален (не може да се направи по-бързо) и точен (дава наистина равномерно разпределение). Когато Spotify твърди, че разбърква плейлиста ви „случайно", зад кулисите работи точно такъв или подобен алгоритъм.
Полиноми на топовете: шах, деранжирания и разпределяне без конфликти
Задачата за топовете в шаха изглежда проста: по колко начина могат да бъдат наредени \(n\) ненападащи топа на \(n \times n\) дъска (никой два да не са в един ред или колона)? Отговорът е \(n!\) — точно толкова, колкото пермутациите на \(n\) елемента. Всяка допустима наредба на топовете съответства на пермутация, при която \(i\)-ят ред съдържа топ в колона \(\sigma(i)\).
Но задачата става по-интересна, когато забраним определени клетки. Например: 4 служители трябва да бъдат разпределени по 4 отдела, но служител 1 не може да работи в отдел 3, а служител 3 — в отдели 1 и 2. По колко начина може да стане разпределянето? Това е точно задача за топове върху дъска с забранени клетки.
Полиномът на топовете \(R_B(x) = \sum_{k=0}^{n} r_k x^k\) за дъска \(B\) е генерираща функция, в която коефициентът \(r_k\) е броят на начините за разполагане на \(k\) ненападащи топа върху \(B\). Ключовата теорема свързва полиномите на топовете с пермутациите с ограничения:
\[\text{Брой допустими пермутации} = \sum_{k=0}^{n} (-1)^k r_k (n-k)!\]Забележете: при забранена главна диагонала (не се позволява \(\sigma(i) = i\)) точно се получава формулата за деранжиранията! Деранжиранията са специален случай на задачата за топовете.
Полиномите на топовете са пример за двойно броене с тегла — техника, при която приписваме тегло на всяка конфигурация и сумираме по всички. Те са едновременно средство за изчисления и теоретичен мост между пермутациите, принципа на включванията-изключванията и теорията на деранжиранията.
Топологична комбинаторика: Hex и лемата на Шпернер
Може би най-изненадващото приложение на комбинаториката е в доказателствата на теореми, които на пръв поглед нямат нищо общо с броенето. Ето един пример.
Представете си партия на Hex — настолна игра на дъска с шестоъгълни клетки. Двама играчи се редуват, запълвайки клетки. Първият иска да свърже левия с десния край на дъската, вторият — горния с долния. В Hex не може да има равенство: точно един от двамата непременно ще успее. Доказателството на този факт е изненадващо комбинаторно — и е свързано с топологичната лема на Шпернер.
Лемата на Шпернер казва нещо просто: ако правилно оцветите триъгълника и неговото триъгълно деление, то винаги съществува малко триъгълниче, чиито три върха имат три различни цвята. Доказателството е красив пример за двойно броене — техника, при която броим едно и също нещо по два различни начина и сравняваме резултатите.
В интервю за Quanta Magazine математикът Федерико Ардила казва, че комбинаториката е дисциплина, в която „решенията са скрити сред невъзможно много варианти и трябва да се открие структурата, за да се намерят." Именно тази структура е мостът между брутната сила на броенето и елегантността на математиката. — по интервю с Федерико Ардила, Quanta Magazine (2021)
Ключови моменти в историята на комбинаториката
- Индийският учен Пингала описва схеми в санскритската поезия, свързани с биномните коефициенти — хиляди години преди Паскал.
- Арабски учени систематизират комбинаторни задачи в контекста на лингвистиката, поезията и музиката.
- Китайският математик Джу Шъцзи публикува „триъгълника на Паскал" (известен в Китай като триъгълник на Ян Хуей) два века преди Паскал.
- Блез Паскал и Пиер дьо Ферма разработват теорията на вероятностите, тясно свързана с комбинаториката.
- Пиер Реймон дьо Монморт поставя и решава задачата за деранжиранията (задачата за шапките) — открива, че вероятността клони към 1/e.
- Китайският математик Минганту открива числата на Каталан — 120 години преди Каталан.
- Леонард Ойлер решава задачата за кьонигсбергските мостове — основополагащ момент за теорията на графите и дискретната математика.
- Ойлер изследва триангулирането на полигони и открива числата на Каталан независимо.
- Йожен Каталан изследва редицата, която днес носи неговото име, в контекста на правилното скобуване.
- Емануел Шпернер формулира своята лема и своята теорема — два основни резултата, които по-късно стават фундаментални за комбинаториката и топологията.
- Рандолф Фишер и Фрэнк Йейтс публикуват алгоритъм за случайно пермутиране, залегнал в основата на компютърното разбъркване.
- Ричард Стенли описва 66 различни интерпретации на числата на Каталан в „Enumerative Combinatorics".
- Анонимен потребител в интернет форум публикува доказателство на долната граница за свръхпермутациите — авторът и до днес е неизвестен.
- Научнофантастичният писател Грег Иган публикува в Twitter доказателство за нова, по-добра горна граница за свръхпермутациите, бързо потвърдено от математиците.
Защо комбинаториката е толкова трудна — и толкова красива
От всички клонове на математиката комбинаториката може би е най-лесна за задаване на въпроси и най-трудна за отговаряне. Задачата „колко начина има да наредите 10 числа?" е разбираема за ученик от 5 клас. Доказателствата на конкретни комбинаторни теореми могат да задържат в работата си цели поколения математици.
Причината е, че комбинаториката се занимава с дискретни структури — крайни или изброими обекти — при които непрекъснатите методи на анализа и алгебрата не работят директно. Всяка задача изисква нов поглед, нова идея, нова техника. Няма единна формула, обхващаща всичко.
Но именно в тази особеност се крие красотата. Комбинаториката е математиката на изненадата. Числата, които на пръв поглед изглеждат просто резултат от формули, понякога крият дълбоки структури. Привидно различни задачи се оказват едно и също. Анонимен потребител в интернет форум решава проблем, занимавал специалисти десетилетия.
В света, в който алгоритмите вземат решения вместо нас, в който ДНК секвенирането обработва милиарди данни и в който криптографията пази всяка наша комуникация — комбинаториката е по-важна от всякога. В крайна сметка изкуството да броим невъзможно големи неща е и изкуството да откриваме ред в хаоса.
Източници
- BetterExplained. Easy Permutations and Combinations. betterexplained.com
- BetterExplained. Navigate a Grid Using Combinations And Permutations. betterexplained.com
- BetterExplained. Why do we multiply combinations? betterexplained.com
- Mathigon. Combinatorics | World of Mathematics. mathigon.org
- Plus Magazine. How many melodies are there? plus.maths.org
- AMS Feature Column. Rook Polynomials: A Straight-Forward Problem. 2022. mathvoices.ams.org
- Pak, I. History of Catalan Numbers. In: Catalan Numbers, Cambridge University Press, 2015. cambridge.org
- MAA Convergence. Combining Strands of Many Colors: Episodes from Medieval Islam for the Mathematics Classroom. old.maa.org
- MAA Convergence. Combining Strands of Many Colors: Tassels of Colored Silk. old.maa.org
- MAA Reviews. Combinatorics: Ancient and Modern. old.maa.org
- Strogatz, S. Federico Ardila on Math, Music and the Space of Possibilities. Quanta Magazine, 29 March 2021. quantamagazine.org
- Klarreich, E. Mystery Math Whiz and Novelist Advance Permutation Problem. Quanta Magazine, 5 November 2018. quantamagazine.org
- Klarreich, E. What a Math Party Game Tells Us About Graph Theory. Quanta Magazine, 24 March 2022. quantamagazine.org
- Graham, R. L., Knuth, D. E. & Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. 2nd ed., Addison-Wesley, 1994. (Стандартно академично ръководство по комбинаторика.)
- Stanley, R. P. Enumerative Combinatorics. Vol. 1, 2nd ed., Cambridge University Press, 2011.
- Wikipedia. Derangement. en.wikipedia.org
- Brilliant.org. Birthday Paradox. brilliant.org
- Scientific American. Probability and the Birthday Paradox. scientificamerican.com
Още от поредицата „Математика & съвременен свят“
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Прием в университети в чужбина (ISEE, SAT, A-Level)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар