Кіріспе
Белгілі бір үлгілерді құрудың қанша тәсілмен болатынымен айналысатын комбинаторика саласы. Санау комбинаторикасы – бұл комбинаториканың белгілі бір үлгілерді құрудың қанша тәсілмен болатынымен айналысатын саласы. Осы типтегі мәселенің екі мысалы – комбинацияларды санау және пермутацияларды санау. Жалпы алғанда, табиғи сандармен индекстелген Si жиынтықтарының шексіз жиынтығы берілгенде, санау комбинаторикасы әр n үшін Sn жиынтығындағы нысандардың санын санайтын санау функциясын сипаттауға тырысады. Жиынтықтағы элементтердің санын санау өте кең математикалық мәселе болғанымен, қолдануларда туындайтын көптеген мәселелер салыстырмалы түрде қарапайым комбинаторлық сипаттамаға ие. Он екі жол пермутацияларды, комбинацияларды және бөлулерді санау үшін бірыңғай негіз ұсынады. Мұндай функциялардың ең қарапайым түрлері – жабық формулалар, оларды элементарлық функциялардың құрамы ретінде көрсетуге болады, мысалы, факториалдар, дәрежелер және т.б. Мысалы, төменде көрсетілгендей, n картадан тұратын колоданың әртүрлі реттелу мүмкіндіктерінің саны f(n) = n! болады. Жабық формуланы табу мәселесі алгебралық санау деп аталады және көбінесе рекурренттік қатынас немесе туынды функцияны алуды және оны қажетті жабық түрге жету үшін пайдалануды қамтиды. Көбінесе күрделі жабық формула саналатын нысандардың саны артқан сайын санау функциясының мінез-құлқы туралы аз мәлімет береді. Мұндай жағдайларда қарапайым асимптотикалық жуықтау артық болуы мүмкін. Егер функция асимптотикалық жуықтау болып табылады. Бұл жағдайда біз деп жазамыз.
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions. The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as shown below, the number of different possible orderings of a deck of n cards is f(n) = n!. The problem of finding a closed formula is known as algebraic enumeration, and frequently involves deriving a recurrence relation or generating function and using this to arrive at the desired closed form. Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows. In these cases, a simple asymptotic approximation may be preferable. A function is an asymptotic approximation to if as In this case, we write
Құрылғыларды құру функциялары
Комбинаторлық нысандар отбасыларын сипаттау үшін генерациялау функциялары қолданылады. Объекттер отбасын F(x) деп белгілейік, ал оның генерациялау функциясын – F(x). Онда
мұндағы – n өлшемді комбинаторлық нысандардың санын білдіреді. Сондықтан, n өлшемді комбинаторлық нысандардың саны – бұл коэффициент. Комбинаторлық нысандар отбасы бойынша жиі кездесетін операциялардың әсері және оның генерациялау функциясына тигізетін әсері енді қарастырылады. Кейде экспоненциалды генерациялау функциясы да қолданылады. Ол мынадай түрде болады:
Генерациялау функциясы анықталғаннан кейін, бұрынғы тәсілдермен алынған ақпаратты береді. Сонымен қатар, генерациялау функцияларындағы қосу, көбейту, дифференциалдау сияқты әртүрлі табиғи операциялар комбинаторлық мағынаға ие; бұл бір комбинаторлық мәселенің шешімін басқаларын шешу үшін пайдалануға мүмкіндік береді.
Қазақстан Республикасы
Екі комбинаторлық отбасы берілген, олардың тудыру функциялары F(x) және G(x) болса, осы екі отбасының ажыратылған біріктірілісі F(x) + G(x) тудыру функциясына ие.
Жұптар
Жоғарыда көрсетілгендей екі комбинаторлық отбасы үшін, екі отбасының декартылық көбейтіндісі (жұбы) F(x)G(x) туынды функциясын құрайды.
Комбинаторлық құрылымдар
Жоғарыда аталған операцияларды енді ағаштар (бинарлық және жазықты), Дайк жолдары мен циклдарды қоса алғанда, жиі кездесетін комбинаторлық объектілерді тізімдеуге қолдануға болады. Комбинаторлық құрылым атомдардан құралған. Мысалы, ағаштар үшін атомдар – түйіндер болады. Объектіні құрайтын атомдар белгіленген немесе белгіленбеген болуы мүмкін. Белгіленбеген атомдар бір-бірінен ажыратылмайды, ал белгіленген атомдар ерекшеленеді. Сондықтан, белгіленген атомдардан тұратын комбинаторлық объекті үшін екі немесе одан көп атомды ауыстыру арқылы жаңа объекті жасауға болады.