Кіріспе
Математикада, әсіресе комбинаторикада, k дәрежесіндегі комбинаторлық сан жүйесі (кейбір оң бүтін сан k үшін), сондай-ақ комбинадика деп аталады, немесе бүтін санның Маколей бейнелеуі – табиғи сандар (0-ді қоса алғанда) N мен k комбинациялары арасындағы сәйкестік. Комбинациялар ck > c2 > c1 ≥ 0 қатаң түрде кемуші тізбектер ретінде көрсетіледі, мұнда әр ci берілген k комбинациядағы таңдалған элементтің индексіне сәйкес келеді. Әртүрлі сандар әртүрлі k комбинацияларына сәйкес келеді және оларды лексикографиялық тәртіппен тудырады. К-ден кіші сандар {0, 1, ..., n − 1} жиынының барлық k комбинацияларына сәйкес келеді. Сәйкестік k комбинациялары алынған жиынның n мөлшеріне тәуелді емес, сондықтан оны N-ден N жиынынан алынған k комбинацияларына бағытталған функция ретінде қарастыруға болады; осы тұрғыдан қарағанда сәйкестік – биекция. (ck, ..., c2, c1) комбинациясына сәйкес келетін N санының кез келген теріс емес N санына бірегей тізбек сәйкес келетіндігін алғаш Д.Х. Лемер байқаған. Шындығында, ашкөз алгоритм N-ге сәйкес k комбинациясын табады: ck-ны максималды етіп таңдаңыз, содан кейін ck-1-ді максималды етіп таңдаңыз, және т.с.с. Жоғарыдағы формула бойынша k комбинациясынан (ck, ..., c2, c1) N санын табу «ранжирлеу» деп аталады, ал кері операция (ашкөз алгоритммен берілген) «ранжирлеусіздендіру» деп аталады; бұл операциялар көптеген компьютерлік алгебра жүйелерінде және есептеу математикасында осы атаулармен белгілі. Бастапқыда қолданылған «бүтін сандардың комбинаторлық бейнелеуі» термині Кнут тарапынан «комбинаторлық сан жүйесі» деп қысқартылды, ол сонымен қатар одан да ертерек анықтама келтіреді; «комбинадикалық» терминін Джеймс Маккаффри енгізді (бұрынғы терминологияға немесе жұмыстарға сілтеме жасамай). Факториалдық сан жүйесінен айырмашылығы, k дәрежесіндегі комбинаторлық сан жүйесі аралас радикс жүйесі емес: «цифр» ci арқылы көрсетілген N санының бөлігі оны орындық мәнмен көбейту арқылы ғана алынбайды. Комбинаторлық сан жүйесінің негізгі қолданылуы – бұл лексикографиялық реттегі берілген позициядағы k комбинациясын жылдам есептеуге мүмкіндік беруі, оған дейінгі k комбинацияларын нақты тізімдеудің қажеті болмайды; бұл, мысалы, берілген жиынның k комбинациясын кездейсоқ түрде құруға мүмкіндік береді. K комбинацияларын санаудың көптеген қолданыстары бар, олардың ішінде бағдарламалық жасақтаманы тестілеу, үлгі алу, сапаны бақылау және лотерея ойындарын талдау.
The fact that a unique sequence corresponds to any non negative number N was first observed by D. H. Lehmer. Indeed, a greedy algorithm finds the k combination corresponding to N: take ck maximal with , then take ck−1 maximal with , and so forth. Finding the number N, using the formula above, from the k combination (ck, , c2, c1) is also known as "ranking", and the opposite operation (given by the greedy algorithm) as "unranking"; the operations are known by these names in most computer algebra systems, and in computational mathematics. The originally used term "combinatorial representation of integers" was shortened to "combinatorial number system" by Knuth,
who also gives a much older reference;
the term "combinadic" is introduced by James McCaffrey (without reference to previous terminology or work). Unlike the factorial number system, the combinatorial number system of degree k is not a mixed radix system: the part of the number N represented by a "digit" ci is not obtained from it by simply multiplying by a place value. The main application of the combinatorial number system is that it allows rapid computation of the k combination that is at a given position in the lexicographic ordering, without having to explicitly list the k combinations preceding it; this allows for instance random generation of k combinations of a given set. Enumeration of k combinations has many applications, among which are software testing, sampling, quality control, and the analysis of lottery games.
Тапсырыс комбинациялары
S жиынтығының k комбинациясы – S жиынтығының k (әр түрлі) элементтен тұратын кіші жиынтығы болып табылады. Комбинаторлық сандық жүйенің басты мақсаты – n элементтен тұратын S жиынтығының барлық мүмкін k комбинацияларын әрқайсысын бір санмен көрсету. Кез келген n үшін, {0, 1, ..., n-1} жиынын осы мақсатқа сай жиын ретінде таңдап алғанда, берілген k комбинациясы C-нің көрсетілуі n-нің мәніне тәуелсіз болады (бірақ n жеткілікті үлкен болуы керек); яғни, C-ді n-ді арттыру арқылы үлкен жиынның кіші жиынтығы ретінде қарастырғанда, C-ні білдіретін сан өзгермейді. Осылайша, комбинаторлық сандар жүйесі үшін C-ні барлық натурал сандар жиынының k комбинациясы ретінде қарастырады, n-ді тікелей атамай. {0, 1, ..., n-1} жиынының k комбинацияларын білдіретін сандар, {0, 1, ..., n-1} жиынына кірмейтін k комбинацияларын білдіретін сандардан кем болуын қамтамасыз ету үшін, k комбинацияларын олардың ең үлкен элементтері бойынша бірінші салыстыру қағидасымен реттеу керек. Бұл қасиетке ие ең табиғи рет – олардың элементтерінің кемдеу ретімен лексикографиялық рет. Мысалы, C = {0,3,4,6,9} және C′ = {0,1,3,7,9} екі комбинацияны салыстырғанда, C, C′-дан бұрын келеді, себебі олардың ең үлкен бөлігі 9 бірдей, бірақ C-нің келесі ең үлкен бөлігі 6, ал C′-ның келесі ең үлкен бөлігі 7-ге тең; лексикографиялық салыстырылатын тізбектер (9,6,4,3,0) және (9,7,3,1,0) болады. Бұл реттеуді сипаттаудың тағы бір жолы – комбинацияларды санның екілік көрсетіліміндегі k белгілі біттерді сипаттаушы ретінде қарастыру, сондықтан C = {c1, ..., ck} саныны сипаттайды (бұл натурал сандардың барлық шекті жиындарына ерекше сандарды сәйкестендіреді); содан кейін k комбинацияларын салыстыруды байланысты екілік сандарды салыстыру арқылы жасауға болады. Мысалда, C және C′ сәйкесінше 1001011001₂ = 60110 және 1010001011₂ = 65110 сандарына сәйкес келеді, бұл тағы да C, C′-дан бұрын келе жатқанын көрсетеді. Алайда, бұл сан k комбинациясын көрсету үшін қажетті сан емес, себебі көптеген екілік сандарда k-дан өзгеше белгілі біттердің саны бар; C-нің (тек) k комбинациялардың реттелген тізіміндегі салыстырмалы орнын табу қажет.
In order to ensure that the numbers representing the k combinations of {0, 1, , n − 1} are less than those representing k combinations not contained in {0, 1, , n − 1}, the k combinations must be ordered in such a way that their largest elements are compared first. The most natural ordering that has this property is lexicographic ordering of the decreasing sequence of their elements. So comparing the 5 combinations C = {0,3,4,6,9} and C′ = {0,1,3,7,9}, one has that C comes before C′, since they have the same largest part 9, but the next largest part 6 of C is less than the next largest part 7 of C′; the sequences compared lexicographically are (9,6,4,3,0) and (9,7,3,1,0). Another way to describe this ordering is view combinations as describing the k raised bits in the binary representation of a number, so that C = {c1, , ck} describes the number
(this associates distinct numbers to all finite sets of natural numbers); then comparison of k combinations can be done by comparing the associated binary numbers. In the example C and C′ correspond to numbers 10010110012 = 60110 and 10100010112 = 65110, which again shows that C comes before C′. This number is not however the one one wants to represent the k combination with, since many binary numbers have a number of raised bits different from k; one wants to find the relative position of C in the ordered list of (only) k combinations.
Комбинацияның тапсырыс берудегі орны
К-деңгейлі комбинациялық сандар жүйесінде С комбинациясына сәйкес келетін сан – берілген реттелудегі С-ден қатаң төменгі k комбинациялардың саны. Бұл санды C = {ck, …, c2, c1} және ck > … > c2 > c1 арқылы келесідей есептеуге болады. Реттелудің анықтамасынан, С-ден қатаң төменгі әрбір k комбинациясы S үшін, S-де ck, …, ci+1 элементтері бар, ал ci-ден үлкен басқа элемент жоқ, мұндай бірегей i индексі болады. Сондықтан k комбинацияларын S бойынша i-нің 1, 2, …, k мүмкін мәндеріне сәйкес топтастыруға болады және әр топты жеке-жеке санауға болады. i-нің берілген мәні үшін S-ге ck, …, ci+1 элементтерін қосу қажет, ал S-тің қалған i элементі ci-ден кіші болатын ci сандық бірліктердің ішінде таңдалуы керек; мұндай кез келген таңдау С-ден қатаң төменгі k комбинациясын береді. Мүмкін болатын таңдаулардың саны , демек, бұл i тобындағы комбинациялардың саны; С-ден қатаң төменгі k комбинациялардың жалпы саны келесідей:
ck, , ci+1 in S, and the remaining i elements of S must be chosen from the ci non negative integers strictly less than ci; moreover any such choice will result in a k combinations S strictly less than C. The number of possible choices is , which is therefore the number of combinations in group i; the total number of k combinations strictly less than C then is
және бұл k комбинацияларының реттелген тізіміндегі С индексі (0-ден басталады). Әрине, әрбір N ∈ N үшін тізімдегі N индексінде дәл бір k комбинациясы бар (k ≥ 1 болғанда, себебі тізім шексіз), сондықтан жоғарыдағы аргумент әрбір N санын берілген түріндегі k биномдық коэффициенттерінің қосындысы ретінде дәл бір жолмен жазуға болатынын көрсетеді.
Берілген санның k-комбинациясын табу
Берілген формула берілген k комбинацияның лексикографиялық тәртібіндегі орнын дереу табуға мүмкіндік береді. Берілген N орнындағы k комбинациясын табу процесі керісінше, біршама көбірек жұмыс талап етеді, бірақ бәрібір түсінікті. Лексикографиялық тәртібінің анықтамасына сәйкес, ең үлкен элементі ck-мен ерекшеленетін екі k комбинациясы осы ең үлкен элементтерді салыстыру арқылы реттеледі, сондықтан ең үлкен элементінің мәні бірдей барлық комбинациялар тізімде тікелей орналасады. Сонымен қатар, ck ең үлкен элемент ретіндегі ең кіші комбинация болып табылады, және оның барлық i < k үшін ci = i - 1 (осы комбинация үшін өрнектегі барлық мүшелер нөлге тең). Сондықтан ck – k > 1 болған жағдайда, k комбинациясының қалған элементтері k - 1 дәрежелі комбинаторлық сан жүйесіндегі санға сәйкес келетін k - 1 комбинациясын құрайды, демек оны N және k орнына және k - 1 үшін сол әдіспен жалғастыру арқылы табуға болады.
Мысал
Мысалы, 72-ші орындағы 5-комбинацияны анықтағысы келеді делік. n = 4, 5, 6 үшін мәндер тізбегі 0, 1, 6, 21, 56, 126, 252 болып табылады, олардың ішіндегі 72-ден аспайтынының ең үлкені 56, n = 8 үшін. Сондықтан c5 = 8, ал қалған элементтер 4-комбинацияны құрайды. n = 3, 4, 5 үшін мәндер тізбегі 0, 1, 5, 15, 35 болып табылады, олардың ішіндегі 16-дан аспайтынының ең үлкені 15, n = 6 үшін, сондықтан c4 = 6. 3-комбинацияны іздеуді жалғастыра отырып, c3 = 3 екенін табамыз, бұл соңғы бірлікті қолданады; бұл белгілейді, және қалған ci мәндері ең үлкен мәндер болады, атап айтқанда, . Осылайша біз 5-комбинацияны {8, 6, 3, 1, 0} деп таптық.