Кіріспе
Комбинаторикадағы санау техникасы Математиканың бір саласы – комбинаторикада, қосу-шығу принципі – екі шекті жиынның элементтер санын табудың танымал әдісін жалпылайтын санау техникасы. Символикалық түрде, егер A және B екі шекті жиын болса, |S| жиынның кардиналдығын көрсетеді (егер жиын шекті болса, ол жиынның элементтер саны ретінде қарастырылуы мүмкін). Формула екі жиынның өлшемдерінің қосындысы тым үлкен болуы мүмкін екендігін білдіреді, өйткені кейбір элементтер екі рет саналуы мүмкін. Екі рет саналған элементтер – екі жиынның қиылысындағы элементтер, ал санауды қиылыстың өлшемін алып тастау арқылы түзетуге болады. Екі жиынтық жағдайды жалпылау болып табылатын қосу-шығу принципі, үш жиынтық жағдайында одан да анық көрінеді, ол A, B және C жиынтықтары үшін мына формуламен беріледі:
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
where A and B are two finite sets and |S | indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection. The inclusion exclusion principle, being a generalization of the two set case, is perhaps more clearly seen in the case of three sets, which for the sets A, B and C is given by
This formula can be verified by counting how many times each region in the Venn diagram figure is included in the right hand side of the formula. In this case, when removing the contributions of over counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total. Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:
Include the cardinalities of the sets. Exclude the cardinalities of the pairwise intersections. Include the cardinalities of the triple wise intersections. Exclude the cardinalities of the quadruple wise intersections. Include the cardinalities of the quintuple wise intersections. Continue, until the cardinality of the n tuple wise intersection is included (if n is odd) or excluded (n even). The name comes from the idea that the principle is based on over generous inclusion, followed by compensating exclusion. This concept is attributed to Abraham de Moivre (1718), although it first appears in a paper of Daniel da Silva (1854) and later in a paper by J. J. Sylvester (1883). Sometimes the principle is referred to as the formula of Da Silva or Sylvester, due to these publications. The principle can be viewed as an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula. As finite probabilities are computed as counts relative to the cardinality of the probability space, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of measure theory. In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix. This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. As Gian Carlo Rota put it:
"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."
Бұл формуланы Венн диаграммасындағы әр аймақтың формуланың оң жағында қанша рет енгізілгенін санау арқылы тексеруге болады. Бұл жағдайда, артық саналған элементтердің үлесін алып тастаған кезде, үш жиынның өзара қиылысындағы элементтер саны тым көп шегеріледі, сондықтан дұрыс жиынтықты алу үшін оны қайта қосу керек. Осы мысалдардың нәтижелерін жалпылау арқылы қосу-шығу принципі туындайды. n жиынтықтың бірігуінің кардиналдығын табу үшін:
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
where A and B are two finite sets and |S | indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection. The inclusion exclusion principle, being a generalization of the two set case, is perhaps more clearly seen in the case of three sets, which for the sets A, B and C is given by
This formula can be verified by counting how many times each region in the Venn diagram figure is included in the right hand side of the formula. In this case, when removing the contributions of over counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total. Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:
Include the cardinalities of the sets. Exclude the cardinalities of the pairwise intersections. Include the cardinalities of the triple wise intersections. Exclude the cardinalities of the quadruple wise intersections. Include the cardinalities of the quintuple wise intersections. Continue, until the cardinality of the n tuple wise intersection is included (if n is odd) or excluded (n even). The name comes from the idea that the principle is based on over generous inclusion, followed by compensating exclusion. This concept is attributed to Abraham de Moivre (1718), although it first appears in a paper of Daniel da Silva (1854) and later in a paper by J. J. Sylvester (1883). Sometimes the principle is referred to as the formula of Da Silva or Sylvester, due to these publications. The principle can be viewed as an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula. As finite probabilities are computed as counts relative to the cardinality of the probability space, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of measure theory. In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix. This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. As Gian Carlo Rota put it:
"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."
Жиынтықтардың кардиналдықтарын қосыңыз. Жұптық қиылыстардың кардиналдықтарын шығарыңыз. Үштік қиылыстардың кардиналдықтарын қосыңыз. Төрттік қиылыстардың кардиналдықтарын шығарыңыз. Бестік қиылыстардың кардиналдықтарын қосыңыз. n-топтық қиылыстың кардиналдығы енгізілгенше (егер n тақ болса) немесе алынып тасталғанша (егер n жұп болса) жалғастырыңыз. Принциптің аты – жомарттықпен қосудан кейін, оны өтемақымен теңестіруден туындайды. Бұл идея Абрахам де Муаврге (1718) тиесілі, бірақ ол алғаш рет Дэниел да Силваның (1854) және кейіннен Дж. Дж. Сильвестрдің (1883) еңбектерінде пайда болады. Кейде принцип осы жарияланымдарға байланысты да Силва немесе Сильвестр формуласы деп аталады. Принципті сандар теориясында кеңінен қолданылатын елеу әдісінің мысалы ретінде қарастыруға болады және кейде елеу формуласы деп аталады. Шекті ықтималдықтар ықтималдық кеңістігінің кардиналдығына қатысты санақтар ретінде есептелетіндіктен, жиынтықтардың кардиналдығы шекті ықтималдықтармен ауыстырылған кезде, қосу-шығу принципінің формулалары жарамды болып қалады. Жалпы алғанда, принциптің екі түрін де өлшем теориясының ортақ шатыры астында қарастыруға болады. Абстрактілі жағдайда, қосу-шығу принципі белгілі бір матрицаның керісін есептеу ретінде берілуі мүмкін. Бұл керіс ерекше құрылымға ие, бұл принципті комбинаторикада және математиканың осыған байланысты салаларында өте құнды әдіс етеді. Джан Карло Рота айтқандай: "Дискретті ықтималдық және комбинаторлық теориядағы санаудың ең пайдалы принциптерінің бірі – қосу-шығу принципі. Бұл принципті шеберлікпен қолданғанда, көптеген комбинаторлық проблемаларды шешуге болады."
In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as
where A and B are two finite sets and |S | indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double counted elements are those in the intersection of the two sets and the count is corrected by subtracting the size of the intersection. The inclusion exclusion principle, being a generalization of the two set case, is perhaps more clearly seen in the case of three sets, which for the sets A, B and C is given by
This formula can be verified by counting how many times each region in the Venn diagram figure is included in the right hand side of the formula. In this case, when removing the contributions of over counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total. Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:
Include the cardinalities of the sets. Exclude the cardinalities of the pairwise intersections. Include the cardinalities of the triple wise intersections. Exclude the cardinalities of the quadruple wise intersections. Include the cardinalities of the quintuple wise intersections. Continue, until the cardinality of the n tuple wise intersection is included (if n is odd) or excluded (n even). The name comes from the idea that the principle is based on over generous inclusion, followed by compensating exclusion. This concept is attributed to Abraham de Moivre (1718), although it first appears in a paper of Daniel da Silva (1854) and later in a paper by J. J. Sylvester (1883). Sometimes the principle is referred to as the formula of Da Silva or Sylvester, due to these publications. The principle can be viewed as an example of the sieve method extensively used in number theory and is sometimes referred to as the sieve formula. As finite probabilities are computed as counts relative to the cardinality of the probability space, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of measure theory. In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix. This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. As Gian Carlo Rota put it:
"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."
Қолданбалар
Инклюзия-шығару принципі кеңінен қолданылады, және оның қолданылуының тек бірнеше мысалына ғана тоқталуға болады.
Санаудың бұзылуы
Инклюзия-исклюзия принципі шекті жиынның барлық ауысуларын санаудың комбинаторлық мәселесіне қолданылады. Жиынның ауысуы – бұл жиыннан өзіне бір-бірге сәйкес келу, онда тұрақты нүктелер жоқ. Инклюзия-исклюзия принципі арқылы егер жиынның кардиналдығы n болса, онда ауысулар саны [n! / e] тең болады, мұндағы [x] – x-ке ең жақын бүтін сан; толық дәлелдеме осы жерде қолжетімді, сондай-ақ жоғарыдағы мысалдар бөлімін қараңыз. Ауысулар санын санау мәселесі алғаш рет П.Р. де Монморттың (1678 – 1719) «Ойын-сауық ойындары туралы талдау тәжірибесі» атты еңбегінде кездеседі және «Монморт мәселесі» немесе оның берген атауымен, «кездесу мәселесі» деп белгілі болды. Бұл мәселе «Қаптама мәселесі» деп те аталады. Ауысулар саны n-нің субфакториалы деп те аталады, ол !n деп жазылады. Барлық бір-бірге сәйкес келулерге бірдей ықтималдық берілсе, онда кездейсоқ бір-бірге сәйкес келудің ауысу болу ықтималдығы n өскенде тез арада 1/e-ге жақындайды.
Қиылыстар санын есептеу
Де Морган заңымен біріктірілген қосу-шығару принципі жиындардың қиылысының кардиналдығын есептеу үшін де қолданылуы мүмкін. Кез келген k үшін, жа жалпы жиынға қатысты Аk-ның толықтығын белгілейік. Осы арқылы қиылысты табу мәселесі одақты табу мәселесіне айналады.
thereby turning the problem of finding an intersection into the problem of finding a union.
Графикті бояу
Инклюзивті-эксклюзивті принцип, графты түстіңге бояу сияқты, бірнеше NP-қатты графты бөлу мәселелері үшін алгоритмдердің негізін құрайды. Принциптің кең таралған қолданылуы – графтың хроматикалық полиномын құру болып табылады.
Екі жақты графиктің толық сәйкестігі
Екі жақты графтың толық шайқастырулар санын осы принцип арқылы есептеуге болады.
Ондағы функциялар саны
А және В шекті жиынтықтар берілгенде, А-дан В-ға дейін қанша сюръективті функция (онто-функциялар) бар? Жалпылықты жоғалтпай, A = {1, ..., k} және B = {1, ..., n} деп аламыз, себебі жиынтықтардың кардиналдықтары ғана маңызды. S-ті A-дан B-ге дейінгі барлық функциялар жиыны ретінде пайдаланып, және B-дегі әрбір i үшін Pi қасиетін "функция B-дегі i элементін қамтымайды" (i функцияның мәндер жиынында жоқ) деп анықтасақ, қосу-азайту принципі A мен B арасындағы сюръективті функциялар санын береді:
Тыйым салынған позициялармен пермутация
S = {1, , n} жиынының әрбір элементінің белгілі бір орындарда болуына тыйым салынған (мұнда пермутация S элементтерінің реттелген тізімі ретінде қарастырылады) пермутация, тыйым салынған орындармен пермутация деп аталады. Мысалы, S = {1,2,3,4} болғанда, 1-ші элемент 1-ші немесе 3-ші орында болуына, ал 2-ші элемент 4-ші орында болуына тыйым салынған жағдайдағы пермутациялар: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 және 4321. Ai жиыны – i-ші элементке орналасуға рұқсат етілмеген орындар жиыны, ал Pi қасиеті – пермутацияның i-ші элементті Ai жиынындағы орынға қою қасиеті. Барлық шектеулерді қанағаттандыратын пермутациялардың санын санау үшін қосымша-азайту принципін қолдануға болады. Берілген мысалда, P1 қасиетіне ие 12 = 2(3!) пермутация, P2 қасиетіне ие 6 = 3! пермутация бар, ал P3 немесе P4 қасиеттеріне ие пермутациялар жоқ, себебі бұл екі элемент үшін шектеулер қарастырылмаған. Сондықтан, шектеулерді қанағаттандыратын пермутациялардың саны: 4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10. Бұл есептеудегі соңғы 4 саны – P1 және P2 қасиеттеріне ие пермутациялардың саны. Формулаға басқа нөлдік емес үлестер жоқ.
4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10. The final 4 in this computation is the number of permutations having both properties P1 and P2. There are no other non zero contributions to the formula.
Екінші түрдегі Стерлинг нөмірлері
Екінші түрдегі Стирлинг сандары S(n,k) n элементтен тұратын жиынтықтың k бос емес ішкі жиынтыққа (белгісіз қораптарға) бөліну санын есептейді. Олар үшін нақты формуланы қосу-азайту принципін өте жақын мәселеге қолдану арқылы алуға болады, атап айтқанда, n жиынтығын k бос емес, бірақ ажыратылатын қораптарға (реттелген бос емес ішкі жиынтықтарға) бөлу санын есептеу арқылы. n жиынының барлық бөліністерінен тұратын әмбебап жиынтықты k (болуы мүмкін бос) ажыратылатын қораптарға, A1, A2, …, Ak және Pi қасиетін, яғни бөлісте Ai қорабы бос екенін пайдалану арқылы, қосу-азайту принципі байланысты нәтижеге жауап береді. k! - ға бөлу арқылы жасанды реттілікті жою екінші түрдегі Стирлинг санын береді.
Суатылған қосу-шығару принципі
Көптеген жағдайларда, принцип дәл формула бере алатын болса (әсіресе, Эратостеннің сырғасын қолданып, жай сандарды санауда), туындайтын формула пайдалы мазмұн ұсынбайды, себебі оның мүшелерінің саны тым көп. Егер әрбір мүше жеке-жеке дәл бағаланса, қателердің жиналуы қосу-азайту формуласының тікелей қолданылуы мүмкін емес екенін көрсетеді. Сандар теориясында осы қиындыққа Вигго Брун шешім берді. Бастапқыда баяу дамығанмен, оның идеяларын басқалар қолға алды және көптеген сырға салу әдістері пайда болды. Мысалы, олар дәл формуланың орнына "сырғалған" жиынтардың жоғарғы шектерін табуға тырысуы мүмкін. A1, …, An кез келген жиын болсын, ал p1, …, pn – жабық бірлік аралығындағы нақты сандар болсын. Онда, {0, …, n} жиынындағы әрбір жұп сан k үшін, индикатор функциялары келесі теңсіздікті орындайды: