Дискретті математиканың саласы: Комбинаторика

Комбинаторика – математиканың дискрет саласы, сану және шектеулі құрылымдарды зерттеумен айналысады. Логика, физика, биология, информатикада қолданылады.

10 мин оқу

100%

Дереккөз: Combinatorics — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Дискретті математиканың саласы

Комбинаторика – математиканың есептеумен, нәтижелерді алу құралы ретінде де, мақсаты ретінде де, сондай-ақ шекті құрылымдардың белгілі бір қасиеттерімен айналысатын саласы. Ол математиканың көптеген басқа салаларымен тығыз байланысты және логикадан статистикалық физикаға дейін, эволюциялық биологиядан компьютер ғылымына дейін көптеген қолданысқа ие. Комбинаторика шешімі күрделі мәселелермен танымал. Комбинаторлық мәселелер таза математиканың көптеген салаларында, әсіресе алгебрада, ықтималдықтар теориясында, топологияда және геометрияда, сондай-ақ оның көптеген қолданыс салаларында туындайды. Көптеген комбинаторлық сұрақтар тарихи тұрғыдан оқшау қарастырылып, математикалық контекстте туындаған мәселенің жекелеген шешімін берген. Алайда, жиырмасыншы ғасырдың соңында қуатты және жалпы теориялық әдістер әзірленді, бұл комбинаториканы математиканың дербес саласына айналдырды. Комбинаториканың ең көне және ең оңай түсінілетін бөліктерінің бірі – графтар теориясы, ол өзі басқа салалармен көптеген табиғи байланыстарға ие. Комбинаторика компьютер ғылымында алгоритмдерді талдау кезінде формулалар мен шамалауларды алу үшін жиі қолданылады. Комбинаториканы зерттейтін математик – .

Тарих

Комбинаторлық негізгі ұғымдар мен санау нәтижелері ежелгі әлемде пайда болды. Үнді дәрігері Сушрута «Сушрута Самхита» еңбегінде 6 түрлі дәмнен 63 комбинация жасауға болатынын айтады, оларды біреуден бастап, екеуден, сосын басқаша топтастыра отырып, барлығы 26-1 мүмкіндікті есептейді. Грек тарихшысы Плутарх Крисипп (б.з.д. 3 ғасыр) пен Гиппарх (б.з.д. 2 ғасыр) арасындағы бір қиын санау мәселесі туралы пікірталасқа тоқталады, кейіннен бұл мәселенің Шредер-Гиппарх сандарымен байланысты екені анықталды. Одан бұрын, «Остомахион» еңбегінде Архимед (б.з.д. 3 ғасыр) мозаикалық жұмбақтың конфигурацияларының санын қарастырған болуы мүмкін, ал комбинаторлыққа қызығушылық Аполлонийдің жоғалған еңбектерінде де болған болуы мүмкін. Орта ғасырларда комбинаторика негізінен Еуропа цивилизациясының шеңберінен тыс жерлерде зерттелді. Үнді математигі Махавира (шамамен 850 ж.) пермутациялар мен комбинациялар санының формулаларын келтірді, және бұл формулалар б.з. 6 ғасырында-ақ үнді математиктеріне белгілі болған болуы мүмкін. Философ және астроном Рабби Ибрахим ибн Эзра (шамамен 1140 ж.) биномдық коэффициенттердің симметриясын дәлелдеді, ал 1321 жылы талмудист және математик Леви бен Герсон (Герсонид ретінде танымал) жабық формуланы тапты. Биномдық коэффициенттер арасындағы байланыстарды көрсететін графикалық диаграмма – арифметикалық үшбұрыш – математиктердің 10 ғасырға дейінгі трактаттарында ұсынылған және кейіннен Паскаль үшбұрышы деп аталды. Кейін, ортағасырлық Англияда колокол қоңыраулары (кампанология) пермутациялар бойынша Кейли графиктеріндегі Гамильтон циклдарының мысалдарын берді. Ренессанс кезеңінде математика мен ғылымның қалған бөлігімен бірге комбинаторика да қайта жанданды. Паскаль, Ньютон, Якоб Бернулли және Эйлердің еңбектері жаңа саланың негізін қалады. Қазіргі заманда Дж. Дж. Сильвестрдің (19 ғасырдың соңы) және Перси МакМахонның (20 ғасырдың басы) еңбектері санау және алгебралық комбинаториканың негізін салуға көмектесті. Осы кезеңде графтар теориясы да қызығушылықты арттырды, әсіресе төрт түс мәселесіне байланысты. 20 ғасырдың екінші жартысында комбинаторика қарқынды дамыды, нәтижесінде осы сала бойынша ондаған жаңа журналдар мен конференциялар құрылды. Бұл өсімге алгебрадан ықтималдық теориясына, функционалдық талдаудан сан теориясына дейінгі басқа салалармен жаңа байланыстар мен қолданбалар ықпал етті. Бұл байланыстар комбинаторика мен математиканың және теориялық информатиканың бөліктері арасындағы шекараларды жойды, бірақ сонымен бірге саланың ішінара фрагментациясына әкелді.

Basic combinatorial concepts and enumerative results appeared throughout the ancient world. Indian physician Sushruta asserts in Sushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 26 − 1 possibilities. Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to Schröder–Hipparchus numbers. Earlier, in the Ostomachion, Archimedes (3rd century BCE) may have considered the number of configurations of a tiling puzzle, while combinatorial interests possibly were present in lost works by Apollonius. In the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. The Indian mathematician Mahāvīra (c. 850) provided formulae for the number of permutations and combinations, and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE. The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) established the symmetry of binomial coefficients, while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321. The arithmetical triangle—a graphical diagram showing relationships among the binomial coefficients—was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle. Later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations. During the Renaissance, together with the rest of mathematics and the sciences, combinatorics enjoyed a rebirth. Works of Pascal, Newton, Jacob Bernoulli and Euler became foundational in the emerging field. In modern times, the works of J. J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) helped lay the foundation for enumerative and algebraic combinatorics. Graph theory also enjoyed an increase of interest at the same time, especially in connection with the four color problem. In the second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject. In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory, etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field.

Санақтық комбинаторика

Энумеративтік комбинаторика – комбинаториканың ең классикалық саласы болып табылады және нақты комбинаторлық объектілердің санын есептеуге бағытталған. Жиын ішіндегі элементтердің санын есептеу математиканың кең мәселесі болғанымен, қолданыста туындайтын көптеген мәселелердің салыстырмалы түрде қарапайым комбинаторлық сипаттамасы бар. Фибоначчи сандары – энумеративтік комбинаторикадағы мәселенің негізгі мысалы. Он екі жол пермутацияларды, комбинацияларды және бөлулерді есептеу үшін біртұтас аяздама ұсынады.

Аналитикалық комбинаторика

Аналитикалық комбинаторика күрделі талдау және ықтималдық теориясының құралдарын қолдана отырып, комбинаторлық құрылымдарды санаумен айналысады. Санамалық комбинаторика нәтижелерді сипаттау үшін нақты комбинаторлық формулалар мен тудыру функцияларын пайдаланса, аналитикалық комбинаторика асимптотикалық формулаларды алуға ұмтылады.

Бөлім теориясы

Партиция теориясы бүтін сандардың бөліністеріне қатысты әртүрлі санау және асимптотикалық мәселелерді зерттейді және q қатарлары, арнайы функциялар және ортогональды полиномдармен тығыз байланысты. Бастапқыда сандар теориясы мен анализдің бір бөлігі болған, қазір ол комбинаториканың бөлігі немесе тәуелсіз сала ретінде қарастырылады. Ол биективті тәсілді және анализ және аналитикалық сандар теориясындағы түрлі құралдарды қамтиды, сондай-ақ статистикалық механикамен байланысы бар. Бөліністерді Янг диаграммалары немесе Феррер диаграммалары арқылы графикалық түрде көрсетуге болады. Олар математика мен физиканың көптеген салаларында, оның ішінде симметриялық полиномдар мен симметриялық топтарды зерттеуде және жалпы топтық өкілдік теориясында кездеседі.

Граф теориясы

Графтар комбинаторикадағы негізгі объектілер болып табылады. Графтар теориясының қарастырылуы санаудан (мысалы, k қабырғасы бар n төбесіндегі графтардың саны) бастап, белгілі бір құрылымдарға (мысалы, Гамильтон циклдары) және алгебралық өрнектемелерге (мысалы, G графы және екі x және y саны берілгенде, Тютте полиномы TG(x,y) комбинаторлық тұрғыдан түсіндіріледі ме?) дейін жетеді. Графтар теориясы мен комбинаторика арасында өте күшті байланыс болғанымен, олар кейде жеке пәндер ретінде қарастырылады. Комбинаторлық әдістер көптеген графтар теориясы мәселелеріне қолданылса да, бұл екі ғылым әдетте әртүрлі типтегі мәселелерді шешу үшін пайдаланылады.

Құрылыс теориясы

Дизайн теориясы – белгілі бір қиылысу қасиеттеріне ие кіші жиындықтар жиынтығы болып табылатын комбинаторлық дизайндарды зерттейтін ғылым. Блоктық дизайн – комбинаторлық дизайнның ерекше түрі. Бұл сала комбинаториканың ең көне бөліктерінің бірі, мысалы, 1850 жылы ұсынылған Киркманның оқушы қыздарының мәселесі. Мәселенің шешімі – Штайнер жүйесінің ерекше жағдайы, олар шекті қарапайым топтарды жіктеуде маңызды рөл атқарады. Бұл сала кодтау теориясы және геометриялық комбинаторикамен де байланысты. Комбинаторлық дизайн теориясын эксперименттерді жобалау саласында қолдануға болады. Комбинаторлық дизайнның негізгі теориясының бір бөлігі статистик Рональд Фишердің биологиялық эксперименттерді жобалау жұмысында қалыптасқан. Қазіргі қолданыстары шекті геометрия, турнир кестелерін жасау, лотереялар, математикалық химия, математикалық биология, алгоритмдерді жобалау және талдау, желілер, топтық тестілеу және криптография сияқты көптеген салаларда кездеседі.

Түпкіленген геометрия

Шекті геометрия — нүктелерінің саны шектеулі геометриялық жүйелерді зерттейтін ғылым. Үзіліссіз геометрияда (Эвклид жазықтығы, нақты проективті кеңістік сияқты) кездесетін, бірақ комбинаторлық тұрғысынан анықталған құрылымдар негізгі зерттелу нысандары болып табылады. Бұл сала дизайн теориясы үшін көптеген мысалдар береді. Оны дискретті геометриямен (комбинаторлық геометриямен) шатастырмау керек.

Тәртіп теориясы

Тәртіп теориясы – шекті және шексіз ішінара реттелген жиынтықтарды зерттейтін ғылым. Ол "бұл одан кем" немесе "бұл одан ертерек" сияқты тұжырымдамаларды формалды түрде сипаттауға мүмкіндік береді. Ішінара реттерге алгебра, геометрия, сандар теориясы және комбинаторика мен графтар теориясы салаларында көптеген мысалдар кездеседі. Атақты кластар мен ішінара реттердің мысалдары решіктер (латтастар) және Буль алгебралары болып табылады.

Матроидтар теориясы

Матроид теориясы геометрияның бір бөлігін абстракциялайды. Ол векторлық кеңістіктегі векторлар жиындарының (әдетте, шекті жиындардың) қасиеттерін зерттейді, бұл қасиеттер сызықтық тәуелділік қатынасындағы нақты коэффициенттерге тәуелді емес. Матроид теориясы құрылымдық және санамалық қасиеттерді қамтиды. Бұл теорияны Хасслер Уитни енгізді және бастапқыда тәртіп теориясының бір бөлігі ретінде зерттелді. Қазіргі таңда матроид теориясы – комбинаториканың басқа салаларымен байланысы бар дербес зерттеу саласы.

Экстремалды комбинаторика

Экстремалды комбинаторика шекті объектілер жиынтығының (сандар, графтар, векторлар, жиынтықтар және т.б.) қаншалықты үлкен немесе қаншалықты кіші болуы мүмкін екенін зерттейді, егер олар белгілі бір шектеулерге бағынуы керек болса. Экстремалды комбинаториканың көп бөлігі жиынтық жүйелерінің кластарын қарастырады; бұл экстремалды жиынтықтар теориясы деп аталады. Мысалы, n элементтен тұратын жиында, бір-бірін жұптап қиылысатын k элементтен тұратын жиынтықтардың ең көп саны қандай? Бір жиынтықтың ешқайсысы басқа жиынтықтың ішінде қамтылмайтын ең көп саны қандай? Соңғы сұраққа экстремалды жиынтықтар теориясының көп бөлігін қалыптастырған Спернер теоремасы жауап береді. Бұл жағдайда қарастырылатын сұрақтар белгілі бір қасиеттерге ие болатын ең үлкен граф туралы. Мысалы, 2n төбесі бар ең үлкен үшбұрышсыз граф – Kn,n толық екі бөлікті граф. Көбінесе f(n) экстремалды жауабын нақты табу өте қиын, сондықтан тек асимптотикалық шамалауға болады. Рамсей теориясы – экстремалды комбинаториканың тағы бір бөлігі. Ол кез келген жеткілікті үлкен конфигурацияда белгілі бір рет болуы керек екенін көрсетеді. Бұл – қақпақ принципінің кеңейтілген түрі.

Ықтималдық комбинаторика

Ықтималдық комбинаторикада сұрақтар мынадай болып қойылады: кездейсоқ граф сияқты кездейсоқ дискретті объектіде белгілі бір қасиеттің болу ықтималдығы қандай? Мысалы, кездейсоқ графтағы үшбұрыштардың орташа саны қанша? Ықтималдық әдістер сонымен қатар, белгілі бір қасиеттері бар комбинаторлық объектілердің бар екенін анықтау үшін де қолданылады (олардың нақты мысалдарын табу қиын болуы мүмкін), осы қасиеттері бар объектіні кездейсоқ таңдау ықтималдығы 0-ден артық екенін байқау арқылы. Бұл тәсіл (көбінесе ықтималдық әдіс деп аталады) экстремалды комбинаторика және графтар теориясы салаларында қолданылуда өте тиімді болып көрінді. Бұл саламен тығыз байланысты Марков тізбектерін зерттеу, әсіресе комбинаторлық объектілерде. Мұнда да араласу уақытын бағалау үшін ықтималдық құралдары пайдаланылады. Бұл тақырыптағы пионерлік жұмыстарды жасаған Пол Эрдос есімімен жиі байланысты, ықтималдық комбинаторика дәстүрлі түрде комбинаториканың басқа салаларындағы мәселелерді зерттеуге арналған құралдар жиынтығы ретінде қарастырылды. Алайда, бұл сала соңғы кезде комбинаториканың жекелеген саласы ретінде дамыды.

Алгебралық комбинаторика

Алгебралық комбинаторика — математиканың абстрактілік алгебраның әдістерін, әсіресе топтық теория мен өкілдік теориясын, түрлі комбинаторлық жағдайларда қолданатын және керісінше, комбинаторлық тәсілдерді алгебра мәселелеріне қолданатын саласы. Алгебралық комбинаторика комбинаторлық және алгебралық әдістердің өзара әрекеттесуі ерекше күшті және маңызды болатын математика саласы ретінде кеңінен таныла бастады. Сондықтан комбинаторлық тақырыптар санау сипатында болуы мүмкін, немесе матроидтар, политоптар, ішінара реттелген жиынтықтар немесе шекті геометрияларды қамтуы мүмкін. Алгебралық тұрғыдан алғанда, топтық және өкілдік теориясынан өзге, тор теориясы және коммутативтік алгебра да жиі қолданылады.

Сөздерді комбинациялау

Сөздер бойынша комбинаторика формальды тілдерді зерттейді. Ол математиканың бірнеше салаларында, оның ішінде сандар теориясы, топтар теориясы және ықтималдықтар теориясында дербес түрде пайда болды. Оның қолданылу аясы – санау комбинаторикасы, фракталдық талдау, теориялық информатика, автоматтар теориясы және тіл білімі. Көптеген қолданыстары жаңа болғанымен, осы саладағы ең белгілі нәтиже – классикалық Чомский-Шутценбергер формальды грамматикалардың сыныптарының иерархиясы болып табылады.

Геометриялық комбинаторика

Геометриялық комбинаторика дөңгелек және дискретті геометриямен байланысты. Мысалы, дөңгелек политоптың әрбір өлшемде қанша беті болуы мүмкін деген сұрақтар қарастырылады. Политоптардың метрикалық қасиеттері де маңызды рөл атқарады, мысалы, дөңгелек политоптардың қатаңдығы туралы Коши теоремасы. Пермутоэдра, ассоциаэдра және Бирхофф политоптары сияқты арнайы политоптар да қарастырылады. Комбинаторлық геометрия – дискретті геометрияның тарихи атауы. Ол полиэдрлік комбинаторика (дөңгелек полиэдрлердің беттерін зерттеу), дөңгелек геометрия (дөңгелек жиынтықтарды зерттеу, әсіресе олардың қиылыстарының комбинаторикасын) және дискретті геометрия сияқты бірнеше кіші салаларды қамтиды, ал дискретті геометрия өз кезегінде есептеу геометриясына көптеген қолданыстарға ие. Регулярлы политоптарды, Архимед денелерін және тиістік сандарын зерттеу де геометриялық комбинаториканың бір бөлігі болып табылады. Сондай-ақ, пермутоэдр, ассоциаэдр және Бирхофф политопы сияқты арнайы политоптар қарастырылады.

Топологиялық комбинаторика

Топологиядағы түсініктер мен әдістердің комбинаторлық аналогтары графиктерді бояу, әділ бөлу, бөліктерге бөлу, ішінара реттелген жиынтықтар, шешім ағаштары, алқа проблемалары және дискретті Морзе теориясын зерттеу үшін пайдаланылады. Бұл комбинаторлық топологиямен шатастырылмауы керек, ол алгебралық топологияның бұрынғы атауы.

Арифметикалық комбинаторика

Арифметикалық комбинаторика сандар теориясы, комбинаторика, эргодикалық теория және гармониялық талдаудың өзара әрекеттесуінен туындады. Ол арифметикалық амалдармен (қосу, алу, көбейту және бөлу) байланысты комбинаторлық шамалаулар туралы ғылым. Аддитивті сандар теориясы (кейде аддитивті комбинаторика деп те аталады) тек қосу және алу амалдары қолданылатын ерекше жағдайды қарастырады. Арифметикалық комбинаторикадағы маңызды техникалардың бірі – динамикалық жүйелердің эргодикалық теориясы.

Шексіз комбинаторика

Бескінелік комбинаторика немесе комбинаторлық жиын теориясы – комбинаторикадағы идеялардың шексіз жиындарға кеңейтілуі. Бұл математикалық логика саласы – жиын теориясының бір бөлігі, бірақ жиын теориясы және экстремалды комбинаторика құралдары мен идеяларын қолданады. Зерттелетін нысандардың арасында үздіксіз графтар мен ағаштар, Рамзи теоремасын кеңейту және Мартин аксиомасы бар. Жақындағы зерттеулер континуум комбинаторикасымен және сингуляр кардиналдардың ізбасарларындағы комбинаторикамен айналысады. Джан Карло Рота геометриялық ықтималдықты сипаттау үшін "үздіксіз комбинаторика" терминін қолданды, себебі санау және өлшем арасында көптеген аналогиялар бар.

Комбинаторлық оңтайландыру

Комбинаторлық оңтайландыру – дискретті және комбинаторлық объектілердегі оңтайландыруды зерттейтін сала. Ол комбинаторика және графтар теориясының бір бөлігі ретінде пайда болды, бірақ қазір қолданбалы математика мен компьютерлік ғылымның дербес саласы ретінде қарастырылады, сондай-ақ операциялық зерттеулер, алгоритмдер теориясы және есептеу күрделігі теориясымен байланысты.

Кодтау теориясы

Кодтау теориясы қателерді түзейтін кодтардың алғашқы комбинаторлық құрылымдарымен дизайн теориясының бір бөлігі ретінде пайда болды. Пәннің басты мақсаты – тиімді және сенімді деректерді беру әдістерін жасау. Қазіргі таңдағыда бұл – ақпарат теориясының бір бөлігін құрайтын, зерттеудің кең саласы.

Дискрет және есептеу геометриясы

Дискрет геометрия (кейде комбинаторлық геометрия деп те аталады) комбинаториканың бір бөлігі ретінде пайда болды, оның алғашқы нәтижелері дөңес политоптар және тиісу сандарымен байланысты болды. Дискрет геометрияның есептеу геометриясына қолданылуымен қатар, бұл екі сала ішінара бірігіп, жеке ғылым саласына айналды. Геометриялық және топологиялық комбинаторикамен байланыстар сақталып қалды, оларды ертедегі дискрет геометрияның даму нәтижесі деп қарастыруға болады.

Комбинаторика және динамикалық жүйелер

Динамикалық жүйелердің комбинаторлық аспектілері – дамып келе жатқан тағы бір сала. Бұл жерде динамикалық жүйелер комбинаторлық объектілерде анықталуы мүмкін. Мысалы, графтық динамикалық жүйеге қараңыз.

Комбинаторика және физика

Комбинаторика мен физика, әсіресе статистикалық физика арасындағы байланыс күшейіп келеді. Мысал ретінде Исинг моделінің толық шешімін және Поттс моделінің бір жағынан, хроматикалық және Тютте полиномдарының екінші жағынан арасындағы байланысты атауға болады.