Екі шектеулі жиынға қатысты есептердің жүйелі жіктелуі

Кіріспе

Екі шекті жиынға қатысты 12 байланысты санамалық мәселенің жүйелі жіктелуі. Комбинаторикада "он екі жол" – екі шекті жиынға қатысты 12 байланысты санамалық мәселенің жүйелі жіктелуі болып табылады, оған жиынның немесе санның пермутацияларын, комбинацияларын, көп жиынтықтарын және бөліктерін санаудың классикалық мәселелері кіреді. Бұл жіктелу идеясы Джан Карло Ротаға тиесілі, ал атауын Джоэл Спенсер ұсынған.

Пікірлер

Он екі жолдағы түрлі проблемаларды әртүрлі бағыттардан қарастыруға болады.

Топтар мен қораптар

Дәстүрлі түрде он екі жолдағы көптеген мәселелер функцияларды анықтаудың орнына шарларды қораптарға орналастыру (немесе ұқсас бейнелеу) арқылы тұжырымдалған. N жиынтығын шарлар жиынтығымен, ал X жиынтығын қораптар жиынтығымен анықтауға болады; функция шарларды қораптарға тарату жолын сипаттайды, атап айтқанда, әрбір шарды бір қорапқа орналастыру арқылы. Функция өзінің анықталу облысындағы әрбір мәнге бірегей бейне сәйкестендіреді; бұл қасиет кез келген шардың тек бір ғана қорапқа түсуімен (сонымен қатар, ешбір шар қораптардың сыртында қалмауы керек деген талаппен) көрінеді, ал кез келген қорап кез келген сандағы шарларды қабылдай алады. Функцияның инъективті болуын талап ету бір қорапқа бірден көп шар салуға тыйым салуды білдіреді, ал сюръективті болуын талап ету әрбір қорапта кем дегенде бір шар болуын талап етуді білдіреді. N немесе X жиындарының пермутацияларын есепке алу шарларды немесе қораптарды тиісінше "айырмасыз" деп атау арқылы көрінеді. Бұл дәл емес тұжырымдама, егер шарларды немесе қораптарды алмастыру арқылы бір конфигурацияны екіншісіне түрлендіруге болады, онда әртүрлі конфигурацияларды бөлектеп санамауға болатынын көрсетуге арналған. Бұл түрлендіру мүмкіндігі пермутациялар арқылы іс-қимыл арқылы формальды түрде бекітіледі.

Сынама алу

Статистикада кейбір жағдайларды іріктеме түрінде қарастырудың тағы бір жолы бар. X нысаннан (немесе адамдардан) тұратын популяцияны елестетіңіз, оның ішінде біз N-ді таңдаймыз. Әдетте екі түрлі схема сипатталады: "қайта салумен іріктеме" және "қайта салмай іріктеме". Бірінші жағдайда (қайта салумен іріктеме), нысанды таңдағаннан кейін, оны популяцияға қайта қоямыз, сонда оны қайта таңдау мүмкіндігі болады. Нәтижесінде, әрбір таңдау басқа барлық таңдаулардан тәуелсіз болады, ал іріктемелер жиынтығы техникалық тұрғыдан тәуелсіз және бірдей таралымды деп аталады. Екінші жағдайда болса, нысанды таңдағаннан кейін, оны бөліп қоямыз, яғни оны қайта таңдауға болмайды. Бұл таңдау әрекеті келесі барлық таңдауларға әсер етеді (сол нысанды қайта көруге болмайды), сондықтан таңдауларымыз бір-біріне тәуелді болады. Іріктеме схемаларының екінші айырмашылығы – реттілік маңыздылығы. Мысалы, егер бізде он нысан болса, оның екеуін таңдасақ, онда (4, 7) таңдауы (7, 4) таңдауынан өзгеше болады, егер реттілік маңызды болса; ал егер реттілік маңызды болмаса, онда (4, 7) және (7, 4) таңдаулары эквивалентті болады. Төмендегі кестедегі алғашқы екі қатар мен баған қайта салумен және қайта салмай іріктеме жасауды, реттілік маңыздылығын ескере отырып немесе ескермей іріктеме жасауды көрсетеді. Қайта салумен іріктеме жасау жағдайлары "Кез келген" деп белгіленген бағанда, ал қайта салмай іріктеме жасау жағдайлары "Инъективті" деп белгіленген бағанда табылады. Реттілік маңызды жағдайлары "Ерекше" деп белгіленген қатарда, ал реттілік маңызды емес жағдайлары "Sn орбиталары" деп белгіленген қатарда кездеседі. Әрбір кесте жазбасы белгілі бір іріктеме схемасында қанша түрлі таңдау жиынтығы бар екенін көрсетеді. Осы кестедегі үш жазба ықтималдық таралымына сәйкес келеді. Қайта салумен іріктеме жасау, реттілік маңызды болғанда, N жеке кездейсоқ айнымалылардың бірлескен таралымын сипаттауға тең, олардың әрқайсысы X-тік категориялық таралымға ие. Алайда, реттілік маңызды емес болғанда, қайта салумен іріктеме жасау, X-тік категориядан N санды тартудың бір мультиномиалды таралымын сипаттауға тең, онда әрбір категорияның саны ғана маңызды. Қайта салмай іріктеме жасау, реттілік маңызды емес болғанда, бір мультивариантты гипергеометриялық таралымға тең. Реттілік маңызды болғанда қайта салмай іріктеме жасау, ықтималдық таралымына сәйкес келмейді. Барлық инъективті жағдайларда (қайта салмай іріктеме жасау), егер N ≤ X болмаса, таңдау жиынтықтарының саны нөлге тең. ("Салыстырылатын" жоғарыдағы жағдайларда тиісті таралымның үлгілік кеңістігінің әрбір элементі бөлек таңдау жиынтығына сәйкес келеді, сондықтан тиісті қораптағы сан берілген таралым үшін үлгілік кеңістіктің мөлшерін көрсетеді.) Іріктеме тұрғысынан алғанда, "Сюрективті" деп белгіленген баған біршама ерекше: Біз әрбір нысанды кем дегенде бір рет таңдағанша, қайта салумен іріктеме жасауды жалғастырамыз. Содан кейін, қанша таңдау жасағанымызды санап, егер ол N-ге тең болмаса, бүкіл жиынтықты алып тастап, қайталаймыз. Бұл купон жинаушының мәселесімен салыстыруға болады, онда процесс X купонды "жинауды" (қайта салумен іріктеме жасау арқылы) қамтиды, әрбір купон кем дегенде бір рет көрінгенге дейін. Барлық сюрективті жағдайларда, егер N ≥ X болмаса, таңдау жиынтықтарының саны нөлге тең.

Another way to think of some of the cases is in terms of sampling, in statistics. Imagine a population of X items (or people), of which we choose N. Two different schemes are normally described, known as "sampling with replacement" and "sampling without replacement". In the former case (sampling with replacement), once we've chosen an item, we put it back in the population, so that we might choose it again. The result is that each choice is independent of all the other choices, and the set of samples is technically referred to as independent identically distributed. In the latter case, however, once we have chosen an item, we put it aside so that we can not choose it again. This means that the act of choosing an item has an effect on all the following choices (the particular item can not be seen again), so our choices are dependent on one another. A second distinction among sampling schemes is whether ordering matters. For example, if we have ten items, of which we choose two, then the choice (4, 7) is different from (7, 4) if ordering matters; on the other hand, if ordering does not matter, then the choices (4, 7) and (7, 4) are equivalent. The first two rows and columns of the table below correspond to sampling with and without replacement, with and without consideration of order. The cases of sampling with replacement are found in the column labeled "Any ", while the cases of sampling without replacement are found in the column labeled "Injective ". The cases where ordering matters are found in the row labeled "Distinct," and the cases where ordering does not matter are found in the row labeled "Sn orbits". Each table entry indicates how many different sets of choices there are, in a particular sampling scheme. Three of these table entries also correspond to probability distributions. Sampling with replacement where ordering matters is comparable to describing the joint distribution of N separate random variables, each with an X fold categorical distribution. Sampling with replacement where ordering does not matter, however, is comparable to describing a single multinomial distribution of N draws from an X fold category, where only the number seen of each category matters. Sampling without replacement where ordering does not matter is comparable to a single multivariate hypergeometric distribution. Sampling without replacement where order does matter does not seem to correspond to a probability distribution. In all the injective cases (sampling without replacement), the number of sets of choices is zero unless N ≤ X. ("Comparable" in the above cases means that each element of the sample space of the corresponding distribution corresponds to a separate set of choices, and hence the number in the appropriate box indicates the size of the sample space for the given distribution.) From the perspective of sampling, the column labeled "Surjective " is somewhat strange: Essentially, we keep sampling with replacement until we have chosen each item at least once. Then, we count how many choices we have made, and if it is not equal to N, throw out the entire set and repeat. This is vaguely comparable to the coupon collector's problem, where the process involves "collecting" (by sampling with replacement) a set of X coupons until each coupon has been seen at least once. In all surjective cases, the number of sets of choices is zero unless N ≥ X.

Таңбалау, таңдау, топтастыру

Функцияны X немесе N тұрғысынан қарастыруға болады. Бұл әртүрлі көзқарастарға әкеледі:

Функция N-нің әрбір элементін X элементімен белгілейді. Функция N-нің әрбір элементі үшін X жиынынан бір элементті таңдайды (сайлайды), барлығы n таңдау жасалады. Функция X элементіне сәйкес келетін N элементтерін топтастырады. Бұл көзқарастардың бәрі барлық жағдайларға бірдей қолайлы емес. Белгілеу және таңдау көзқарастары X элементтерінің орналасуымен (пермутациясымен) жақсы үйлесімді емес, себебі бұл белгілерді немесе таңдауды өзгертеді; ал топтау көзқарасы X элементтерін еркін орналастыруға болмаса, конфигурация туралы толық ақпаратты бермейді. N орналастырылмаған (пермутацияланбаған) кезде белгілеу мен таңдау көзқарастары шамалы тең, бірақ орналастырылғанда (пермутацияланғанда) таңдау көзқарасы артық қолайлы. Таңдауды ретсіз таңдау ретінде қарастыруға болады: X элементтерінен n элементтің (көп) жиынтығын бір рет таңдау жасалады.

Жазылу және таңдау қайталаумен немесе қайталамаумен

N элементтерінің белгіленуі ретінде қарағанда, соңғысы тізбек ретінде орналасқан деп есептеуге болады, ал X-тен алынған белгілер оларға бірінен кейін бірі тағайындалады. Инъективтілік талабы белгіні екінші рет қолдануға болмайды дегенді білдіреді; нәтижесінде, белгілердің тізбегінде қайталау болмайды. Мұндай талап болмаған жағдайда, "қайталаулармен тізбек" термині қолданылады, яғни белгілер бірнеше рет қолданылуы мүмкін (бірақ кездейсоқ қайталаусыз тізбектерге де рұқсат етіледі). X элементтерінің ретсіз таңдамасы ретінде қарағанда, осыған ұқсас айырмашылық қолданылады. Егер инъективтілік талап етілсе, таңдама X-тің n әртүрлі элементін қамтуы керек, сондықтан ол X-тің n өлшемді кіші жиыны, сондай-ақ n комбинациясы деп аталады. Талап болмаса, X-тің бір және сол элементі таңдамада бірнеше рет кездесуі мүмкін, нәтижесінде X элементтерінің n өлшемді көп жиыны, сондай-ақ n көпкомбинациясы немесе қайталамалы n комбинациясы пайда болады. N элементтерін белгілеу тұрғысынан, сюръективтілік талабы әрбір белгі кемінде бір рет қолданылуы керек дегенді білдіреді; X-тен таңдау тұрғысынан, X-тің әрбір элементі таңдамаға кемінде бір рет енуі керек. Сүржекциямен белгілеу N элементтерін топтастыруға, содан кейін әр топты X элементімен белгілеуге тең, сондықтан математикалық тұрғыдан сипаттау одан да күрделі.

Жинақтар мен сандардың бөліністері

N элементтерінің топтастырылуы ретінде қарағанда (бұл X пермутациялары бойынша бірін анықтауді білдіреді), сюръективті болу талабы топтардың санының дәл x-ке тең болуын қамтамасыз етеді. Бұл талап болмаған жағдайда топтардың саны ең көп дегенде x-ке жетеді. Инъективті болу талабы N-нің әрбір элементінің өзі жеке топ құруын білдіреді, бұл ең көп дегенде бір ғана жарамды топтастыруға мүмкіндік береді де, нәтижесінде қызығушылықты тудырмайтын санау есебіне әкеледі. Егер N пермутациялары бойынша да бірін анықтаса, онда топтардың өзі ұмытылып, тек олардың мөлшері ғана сақталады. Бұл мөлшерлер нақты ретпен келмейді, сондай-ақ бір мөлшер бірнеше рет қайталанып кездесуі мүмкін; оларды n санының қосындысына тең болатын сандардың кемітулі тізімі түрінде орналастыруға болады. Бұл n санын дәл x (сюръективтілік үшін) немесе ең көп дегенде x (кез келген жағдайда) бөлікке бөлудің комбинаторлық түсінігін береді.

Әр түрлі істердің егжей-тегжейі

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

Инъективті функциялар:

Бұл жағдайда біз X жиынынан алынған n ерекше элементтердің тізбектерін қарастырамыз, бірақ әр элементке X жиынының пермутациясын қолдану арқылы бір-бірінен алынған тізбектерді теңестіреміз. Екі түрлі тізбекті әрқашан теңестіруге болатынын байқау оңай: пермутация бірінші тізбектің i-элементін екінші тізбектің i-элементімен сәйкестендіруі керек, және екі тізбекте де бірде-бір мән екі рет қайталанбас болғандықтан, бұл талаптар бір-біріне қайшы келмейді. Бірінші тізбекте кездеспейтін элементтерді екінші тізбекте кездеспейтін элементтермен кез келген тәртіппен сәйкестендіру қалады. Нәтиженің n және x-ке тәуелді болуын қамтамасыз ететін жалғыз фактор – бұл мұндай тізбектердің болуы үшін n ≤ x шарты, бұл «көгершін принципі» арқылы анықталады. Сондықтан, бұл сан Иверсон жақшасын қолдана отырып былай көрсетіледі: .

Инъективті функциялар:

Бұл жағдай бұрынғы жағдайға келтіріледі: X-тен алынған n түрлі элементтің барлық тізбектерін олардың әрқайсысына X-тің өзгерісін қолдану арқылы бір-біріне айналдыруға болады, сондықтан элементтердің ретін өзгерту де ешқандай жаңа теңдестіруге алып келмейді; саны өзгермейді.

Суръективті функциялар:

Бұл жағдай N-ді x (бос емес) ішкі жиынға бөлуге немесе N-де дәл x классы бар эквиваленттілік қатынастарын санауға тең. Шындығында, кез келген сюръективті функция f: N → X үшін, f бойынша бірдей бейнеге ие болу қатынасы осындай эквиваленттілік қатынас болып табылады және X-тің кез келген өзгерісі қолданылғанда ол өзгермейді; керісінше, мұндай эквиваленттілік қатынасты x эквиваленттілік класына X элементтерін белгілі бір тәртіппен тағайындау арқылы сюръективті функцияға айналдыруға болады. Мұндай бөлістердің немесе эквиваленттілік қатынастардың саны анықтама бойынша екінші түрдегі Стерлинг саны S(n,x) болып табылады, сонымен қатар оның мәні рекурсивті қатынас немесе туынды функциялар арқылы сипатталуы мүмкін, бірақ биномдық коэффициенттерден айырмашылығы, бұл сандар үшін қосындыны қажет ететін жабық формула жоқ.

Функциялардың пермутациясына дейін

Бұл жағдай өршу функцияларына сәйкес келетін жағдайға ұқсас, бірақ x-тің кейбір элементтері ешқандай эквиваленттілік класына жатпауы мүмкін (функцияларды X жиынының орналасуына дейін қарастыратындықтан, қандай элементтерге қатысты екені маңызды емес, тек олардың саны ғана маңызды). Осының салдарынан, N жиынындағы ең көп дегенде x классы бар эквиваленттілік қатынастар саналады, ал нәтиже аталған жағдайдан x-ке дейінгі мәндерді қосу арқылы алынады. Егер x ≥ n болса, x-тің мөлшері ешқандай шектеу қоймайды, және n элементтен тұратын жиынтықтағы барлық эквиваленттілік қатынастар саналады (яғни, мұндай жиынтықтың барлық бөліністері); сондықтан Белл саны Bn үшін формула беріледі.

Суръективті функциялар:

Бұл жағдай n санын нөлден өзге x бөлікке бөлуді санауға баламалы. X жиынының пермутацияларына дейін сюръективті функцияларды санау жағдайымен салыстырғанда, мұнда функция N жиынын бөлетін эквиваленттік сыныптардың мөлшері ғана сақталады (әр мөлшердің қайталануымен қоса), себебі екі эквиваленттік қатынас N жиынының пермутациясы арқылы бір-біріне айналдырыла алады, егер және тек егер олардың сыныптарының мөлшері сәйкес келсе. Осы айырмашылық n-нің бөліну ұғымын N жиынының бөліну ұғымынан ерекшелендіреді, сондықтан анықтама бойынша n санын нөлден өзге x бөлікке бөлудің px(n) саны алынады.

Функциялардың және пермутациялардың

Бұл жағдай n санын ≤ x бөлікке бөлумен эквивалентті. Қауымдастыру алдыңғы жағдаймен бірдей, бірақ енді бөліністің кейбір бөліктері 0-ге тең болуы мүмкін. (Атап айтқанда, олар функцияның бейнесінде жоқ X элементтеріне сәйкес келеді.) n-ді ең көп дегенде x нөлдік емес бөлікке бөлуді қажетті сандағы нөлдерді қосу арқылы осындай бөлініске кеңейтуге болады, және бұл барлық мүмкіндіктерді дәл бір рет қамтиды, сондықтан нәтиже мына арқылы беріледі. x бөліктерінің әрқайсысына 1-ді қосу арқылы n + x санын x нөлдік емес бөлікке бөлуге жетеміз, және бұл сәйкестік биективті; демек, берілген өрнекті оны былай жазу арқылы жеңілдетуге болады.

Жалпылау

Біз N және X-ке басқа пермутациялардың әсер етуіне мүмкіндік беру арқылы одан әрі жалпылай аламыз. Егер G – N пермутацияларының тобы болса, ал H – X пермутацияларының тобы болса, онда біз функциялардың эквиваленттік кластарын санаймыз. Екі функция f және F эквивалентті деп есептеледі, егер және тек қана егер, осындай бар болса, болады. Бұл кеңейту циклдық және диэдрлік пермутациялар, сондай-ақ сандар мен жиынтықтардың циклдық және диэдрлік бөліністері сияқты ұғымдарға әкеледі.