Կցման և արտաքսման սկզբունք կամ կոմբինատոր գումարման սկզբունք (en. Inclusion–exclusion principle), կոմբինատորիկայի հաշվողական մեթոդ է, որը թույլ է տալիս գտնել վերջավոր բազմությունների գումարման արդյունքում ստացված տարրերի քանակը՝ հաշվի առնելով նրանց ընդհանուր հատույթները:

$|A\cup B|=|A|+|B|-|A\cap B|$

Վերը նշված բանաձևում, A-ն և B-ն երկու վերջավոր բազմություններ են և |S|-ը ցույց է տալիս S ունիվերսալ բազմության կարդինալությունը (որը կարող է դիտարկվել որպես բազմության տարրերի քանակ՝ հզորություն, եթե բազմությունը վերջավոր է): Բանաձևն արտահայտում է այն փաստը, որ երկու բազմությունների գումարը կարող է չափազանց մեծ լինել, քանի որ որոշ տարրեր կարող են երկու անգամ գումարվել: Կրկնակի հաշվված տարրերն այն տարրերն են, որոնք գտնվում են երկու բազմությունների հատույթում։ Հաշվարկը ճշգրիտ կատարելու համար անհրաժեշտ է երկու բազմությունների գումարից հանել դրանց հատումը, տարրերի կրկնությունը բացառելու համար։

Կցման-արտաքսման (ներառման-բացառման) սկզբունքը, լինելով բազմությունների գումարման ընդհանրացում, թերևս ավելի պարզ երևում է երեք բազմությունների դեպքում, որոնք A, B և C բազմությունների համար տրված են.

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

Այս բանաձևը կարելի է ստուգել՝ հաշվելով, թե քանի անգամ է Վենի գծապատկերում յուրաքանչյուր հատված ներառվել բանաձևի աջ կողմում։ Երբ չափից շատ հաշված տարրերի ներդրումները հանվում են, երեք բազմությունների հատույթի տարրերը չափազանց շատ են հանվում։ Այդ պատճառով դրանք պետք է կրկին ավելացնել՝ ճիշտ ընդհանուր արդյունքը ստանալու համար։

Կցման-արտաքսման սկզբունք, որը պատկերված է Վենի գծապատկերով երեք հավաքածուների համար

Այս օրինակների արդյունքների ընդհանրացումը տալիս է կցման-արտքասման սկզբունքը: n բազմությունների միավորման հզորությունը (կամ կարդինալությունը) գտնելու համար.

Ներառել բազմությունների հզորությունները
Բացառել զույգային բազմությունների հատույթները
Ներառել եռյակ բազմությունների հատույթները
Բացառել քառյակ բազմությունների հատույթներրը
Ներառել հնգյակ բազմությունների հատույթները
Շարունակեք այսպես, մինչև հասնեք n-նյակ հատույթների հզորությանը, որը պետք է ներառվի, եթե n-ը կենտ է, կամ բացառվի, եթե n-ն զույգ է։

Ծագումնաբանություն

Անունը գալիս է այն մտքից, որ սկզբունքը հիմնված է չափից ավելի անգամ տարրերի ընդգրկման վրա, որին հաջորդում է փոխհատուցվող բացառումը: Այս սկզբունքը վերագրվում է Աբրահամ դը Մուավրին (1718)^[1], չնայած այն առաջին անգամ հայտնվում է Դենիել դա Սիլվայի (1854)^[2] աշխատության մեջ, իսկ ավելի ուշ՝ Ջ.Ջեյ Սիլվեստրի (1883 թ.)^[3] աշխատության մեջ։ Երբեմն սկզբունքը կոչվում է Դա Սիլվայի կամ Սիլվեստրի բանաձև՝ իրենց հրապարակումների շնորհիվ։ Սկզբունքը կարելի է դիտարկել որպես թվերի տեսության մեջ լայնորեն օգտագործվող մաղի մեթոդի (անգլ.՝ sieve method) օրինակ և երբեմն կոչվում է մաղի բանաձև^[4]։

Քանի որ վերջավոր հավանականությունները հաշվարկվում են որպես հավանականության տարածության հզորության հետ կապված հաշվարկներ, ներառման-բացառման սկզբունքի բանաձևերը մնում են ուժի մեջ, երբ բազմությունների հզորությունները փոխարինվում են վերջավոր հավանականություններով: Ավելի ընդհանուր առմամբ, սկզբունքի երկու տարբերակներն էլ կարող են դրվել չափումների տեսության ընդհանուր հովանու ներքո:

Կապը մատրիցների հետ

Շատ աբստրակտ շրջանակում կցման-արտաքսման սկզբունքը կարող ենք պատկերացնել որպես մաթեմատիկական կառուցվածք, որը կապ ունի մատրիցների հետ։ Այնպիսի խնդիրներում, որտեղ հաշվում ենք իրադարձությունների հավանականություններ կամ բազմությունների տարրերի քանակներ, մենք հաճախ կառուցում ենք հավասարումներ, որոնք կախված են միմյանցից։ Դրանք կարելի է ներկայացնել մատրիցի տեսքով։ Մատրիցի հակադարձը թույլ է տալիս լուծել սկզբնական խնդիրն ավելի հեշտ և տրամաբանական կերպով։ Այդ հակադարձն ունի հատուկ կառուցվածք, ինչը սկզբունքը դարձնում է բացառիկ արժեքավոր տեխնիկա կոմբինատորիկայի և մաթեմատիկայի հարակից ոլորտներում։ Ինչպես Ջան-Կառլո Ռոտան ասել է^[5]․

«Դիսկրետ հավանականությունների և կոմբինատորիկայի տեսության մեջ ամենաօգտակար հաշվարկման սկզբունքներից մեկը հանդիսանում է հայտնի ներառման-բացառման սկզբունքը։ Հմտորեն կիրառվելու դեպքում այս սկզբունքը լուծում է տվել բազմաթիվ կոմբինատոր խնդիրների»։

Բանաձև

Կցման-արտաքսման սկզբունքը սահմանում է, որ (A1, ..., An) վերջավոր բազմությունների համար.

\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|.

Կցման-արտաքսման բանաձևի յուրաքանչյուր քայլ աստիճանաբար հստակեցնում է հաշվարկը, մինչև, ի վերջո, Վենի գծապատկերի յուրաքանչյուր մաս ներառվի ուղիղ մեկ անգամ:

Վերը նշված ընդհանուր տեսքով տրվող բանաձևի հակիրճ տարբերակն է․

\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)

կամ

\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|.

Բանաձևի բացատրություն

Վերջավոր բազմությունների վերջավոր միավորումը հաշվելու համար նախ գումարեք առանձին բազմությունների հզորությունները, այնուհետև հանեք այն տարրերի թիվը, որոնք հայտնվում են առնվազն երկու բազմություններում, այնուհետև ավելացրեք տարրերի թիվը, որոնք հայտնվում են առնվազն երեքում, ապա հանել տարրերի թիվը, որոնք հայտնվում են առնվազն չորսում և այլն: Այս գործընթացը միշտ ավարտվում է, քանի որ տարրերի կրկնությունների թիվը չի կարող գերազանցել բազմությունների սկզբնական քանակը։ Օրինակ, եթե $n=4$ , ապա չեն կարող լինել տարրեր, որոնք հայտնվում են ավելի քան $4$ անգամ; համարժեքորեն, չեն կարող լինել տարրեր, որոնք հայտնվում են առնվազն $5$ անգամ:

Կիրառության մեջ առավել տարածված է բանաձևի լրացումներով տարբերակը։ Այսինքն՝ թույլ տալով, որ S-ը լինի վերջավոր ունիվերսալ բազմություն, որը պարունակում է բոլոր ${\bar {A_{i}}}$ -ները և համարենք ${\bar {A_{i}}}$ -ները վերջիններիս լրացումը։ Կիրառելով Դե Մորգանի կանոնները ստացվում է․

\left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.

Որպես հասկացության մեկ այլ դրսևորում, համարենք, որ (P1, ..., Pn)-ը այն հատկությունների ցանկն է, որոնք S բազմության տարրերը կարող են ունենալ կամ չունենալ, ապա կցման-արտաքսման սկզբունքը հնարավորություն է տալիս հաշվարկել S-ի այն տարրերի թիվը, որոնք չունեն հատկություններից որևէ մեկը: Պարզապես համարենք ${A_{i}}$ -ն S ունիվերսալ բազմության այն տարրերի ենթաբազմությունը, որը ունի ${\bar {P_{i}}}$ հատկություն և օգտագործի սկզբունքի լրացումներով տարբերակը: Այս տարբերակը պատկանում է Ջ. Ջ. Սիլվեսթերին։

Ուշադրություն դարձնենք, որ եթե հաշվի առնենք աջ կողմում գտնվող միայն առաջին $m<n$ գումարները (սկզբունքի ընդհանուր ձևով), ապա կստանանք իրական արժեքից առավել մեծ թիվ, եթե $m$ -ը կենտ է, և առավել փոքր թիվ, եթե $m$ -ը զույգ է:

Կիրառության օրինակ

Օրինակ, որը նկարագրում է հաշվարկի ընթացքում հաշվարկի հավանական խախտման խնդիրը։

Ենթադրենք, կա քարտերի շարան, որոնք համարակալված են 1-ից մինչև n։ Ենթադրենք, m-րդ քարտը ճիշտ դիրքում է, եթե դա շարանի $m$ -րդ քարտն է: Քանի՞ եղանակով (քանակը կնշանակվի՝ W), կարելի է խառնել քարտերը, որ առնվազն 1 քարտ լինի ճիշտ դիրքում։

Սկսեք սահմանելով ${A_{m}}$ բազմությունը, որը $m$ -րդ քարտի ճիշտ դիքով բոլոր հնարավոր դասավորությունների քանկն է։ Հետևաբար դասավորությունների քանակը, որտեղ առնվազն մեկ քարտ իր տեղում է կլինի․

W=\left|\bigcup _{m=1}^{n}A_{m}\right|.

Կիրառենք կցման-արտաքսման սկզբունքը․

W=\sum _{m_{1}=1}^{n}|A_{m_{1}}|-\sum _{1\leqslant m_{1}<m_{2}\leqslant n}|A_{m_{1}}\cap A_{m_{2}}|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}|A_{m_{1}}\cap \cdots \cap A_{m_{p}}|+\cdots

( $A_{m_{1}}\cap \cdots \cap A_{m_{p}}$ )-ի յուրաքանչյուր արժեք ներկայացնում է դասավորություների շարք, որը ունի առնվազն $p$ քանակությամբ ( ${m_{1},...,m_{i}}$ ) ճիշտ դիրքում: Նկատի ունենանք, որ p քանակությամբ ճիշտ տեղում գտնվող տարրերի քանակը կախված է միայն $p$ -ից, ոչ թե $m$ -ի որոշակի արժեքներից: Օրինակ՝ 1-ին, 3-րդ և 17-րդ քարտերը ճիշտ դիրքում ունեցող դասասվորությունների թիվը նույնն է, ինչ 2-րդ, 5-րդ և 13-րդ քարտերը ճիշտ դիրքերում: Կարևոր է միայն, որ n քարտերից 3-ն ընտրվել են ճիշտ դիրքում: Այսպիսով կան ${\textstyle {n \choose p}}$ հավասար քանակությամբ բաղադրիչներ $p$ -րդ գումարման մեջ:

W={n \choose 1}|A_{1}|-{n \choose 2}|A_{1}\cap A_{2}|+\cdots +(-1)^{p-1}{n \choose p}|A_{1}\cap \cdots \cap A_{p}|+\cdots

$|A_{1}\cap \cdots \cap A_{p}|$ իրենից ներկայացնում է այն դասավորությունների քանակը, որոնք պարունակում են $p$ հատ ճիշտ դիրքում գտնվող քարտ, որը հավասար է n − p կամ (n − p)!։ Արդյունքում կստանանք․

{\begin{aligned}W&={n \choose 1}(n-1)!-{n \choose 2}(n-2)!+\cdots +(-1)^{p-1}{n \choose p}(n-p)!+\cdots \\&=\sum _{p=1}^{n}(-1)^{p-1}{n \choose p}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!(n-p)!}}(n-p)!\\&=\sum _{p=1}^{n}(-1)^{p-1}{\frac {n!}{p!}}\end{aligned}}

Դասավորությունը, որտեղ ոչ մի քարտ ճիշտ դիրքում չէ, կոչվում է շեղում անգլ.՝ derangement): Ընդունելով, որ (n!)-ը դասավորությունների ընդհանուր քանակն է, կստանանք հաշվարկի շեղման պատահական առաջացման հավանականությունը, ստորև բերված բանաձևով։

Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},

Ստացված արդյունքը իրենից ներկայացնում է Թեյլորի շարքի մոտարկում, սակայն այստեղ գումարը հաշվվում է մինչև n-րդ անդամը։ Այսինքն $Q$ շարքի հաշվարկը սահմանափակվում է $n+1$ անդամով և դա փոքր ինչ կտարբերվի e⁻¹-ի ճշգրիտ արժեքից։ Բայց $n$ -ի մեծացման դեպքում $Q$ -ն ավելի ու ավելի մոտ կլինի e⁻¹-ին կամ 37%-ին։

Մասնավոր դեպք

Իրավիճակը, որը երևում է վերը նշված շեղումների օրինակում, բավական հաճախ է տեղի ունենում: Այսինքն՝ երբ կցման-արտաքսման սկզբունքի բանաձևերում հանդիպող հատման բազմությունների չափսերը կախված են միայն այդ հատումների մեջ ընդգրկված բազմությունների քանակից, բայց ոչ այն բազմություններից, որոնք դրանց կազմում են։ Սահմանվում է․

A_{J}:=\bigcap _{j\in J}A_{j}

ունի նույն հզորությունը, օրինակ՝ α_k = |A_J|, յուրաքանչյուր k-տարրային ենթաբազմության J-ի համար, որտեղ J-ն պատկանում է {1, ..., n}․ Ստացվում է․

\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.

Կամ, լրացումներով տարբերակը, որտեղ S համընդհանուր բազմությունն ունի հզորություն α₀,

\left|S\smallsetminus \bigcup _{i=1}^{n}A_{i}\right|=\alpha _{0}-\sum _{k=0}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.

Ընդհանրացված բանաձև

Տրված է S ունիվերսալ բազմության մեջ A₁, A₂, ..., A_n ենթաբազմությունների խումբը (ընտանիքը), ընդ որում կրկնությունները թույլատրվում են: Կցման-արտաքսման սկզբունքը հաշվարկում է S բազմության մեջ ընկած այն տարրերի թիվը, որոնք չեն պատանում ենթաբազմություններից ոչ մեկին: Այս գաղափարի ընդհանրացված տարբերակը թույլ է տալիս հաշվել S-ի այն տարրերի քանակը, որոնք պատկանում են հենց որոշակի ֆիքսված m ենթաբազմություններին։

Ենթադրենք, որ N = [n] = {1,2,...,n}: Եթե սահմանենք $A_{\emptyset }=S$ , ապա կցման–արտքասման սկզբունքը կարելի է գրել նոր ձևով՝ օգտագործելով նախորդ բաժնի նշանակումը։ S ունիվերսալ բազմության այն տարրերի թիվը, որոնք չեն պատկանում A_i ենթաբազմություններից ոչ մեկին․

\sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.

Եթե I-ը N ինդեքսային բազմության ֆիքսված ենթաբազմություն է, ապա այն տարրերի քանակը, որոնք պատկանում են A_i-ին յուրաքանչյուր i∈I-ի համար և չեն պատկանում ոչ մի այլ ենթաբազմությանը, հաշվարկվում է հետևյալ բանաձևով^[6]՝

\sum _{I\subseteq J}(-1)^{|J|-|I|}|A_{J}|.

Սահմանենք բազմությունները․

B_{k}=A_{I\cup \{k\}}{\text{ for }}k\in N\smallsetminus I.

Մենք փնտրում ենք B_k-ին չպատկանող այն տարրերի թիվը $B_{\emptyset }=A_{I}$ պայմանի կիրառման դեպքում․

\sum _{K\subseteq N\smallsetminus I}(-1)^{|K|}|B_{K}|.

Համապատասխանությունը K ↔ J = I ∪ K ենթաբազմությունների միջև, որտեղ K ենթաբազմություն N \ I-ի, իսկ J ենթաբազմություն է N'-ի, որը պարունակում է I-ն, բիեկցիա է։ Եթե J և K համապատասխանում են այս համապատասխանության ներքո, ապա B_K = A_J, ինչը ցույց է տալիս, որ արդյունքը ճիշտ է։

Հանհրահաշվական ապացույց

Ալգեբրական ապացույց կարող է ստացվել օգտագործելով ցուցիչ ֆունկցիաներ (հայտնի նաև որպես բնութագրական ֆունկցիաներ): Ցուցիչ ֆունկցիան բազմության S ունիվերսալ բազմության համար, որը պատկանում է X բազմությանը, հետևյալ ֆունկցիան է՝

{\begin{aligned}&\mathbf {1} _{S}:X\to \{0,1\}\\&\mathbf {1} _{S}(x)={\begin{cases}1&x\in S\\0&x\notin S\end{cases}}\end{aligned}}

Եթե $A$ -ն և $B$ -ն $X$ -ի երկու ենթաբազմություններ են, ապա

\mathbf {1} _{A}\cdot \mathbf {1} _{B}=\mathbf {1} _{A\cap B}.

Նշանակենք A-ն A₁, ..., A_n բազմությունների միավորում՝ ${\textstyle \bigcup _{i=1}^{n}A_{i}}$ ։ Ներառման-բացառման սկզբունքը ընդհանուր տեսքով ապացուցելու համար, նախ պետք է հաստատենք հետևյալ հավասարությունը։

\mathbf {1} _{A}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop |I|=k}\mathbf {1} _{A_{I}}

ցուցիչ ֆունկցիայի համար կլինի․

A_{I}=\bigcap _{i\in I}A_{i}.

Ստորև բերված է ֆունկցիան․

\left(\mathbf {1} _{A}-\mathbf {1} _{A_{1}}\right)\left(\mathbf {1} _{A}-\mathbf {1} _{A_{2}}\right)\cdots \left(\mathbf {1} _{A}-\mathbf {1} _{A_{n}}\right)=0,

Եթե x-ը չպատկանում է A-ին, ապա բոլոր գործոնները 0−0 = 0 են, իսկ եթե x-ը պատկանում է որոշ «A_m»-ին, ապա համապատասխան «m^th» գործոնը 1−1=0 է։ Ընդլայնելով ձախ կողմի բազմապատկումը՝ ստանում ենք այս բաժնի 4-րդ հավասարությունը։

Նշումներ

↑ Roberts & Tesman 2009, pg. 405
↑ Mazur 2010, pg. 94
↑ van Lint & Wilson 1992, pg. 77
↑ van Lint & Wilson 1992, pg. 77
↑ Rota, Gian-Carlo (1964), «On the foundations of combinatorial theory I. Theory of Möbius functions», Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2 (4): 340–368, doi:10.1007/BF00531932, S2CID 121334025
↑ Cameron 1994, pg. 78

Ծանոթագրություններ

Allenby, R.B.J.T.; Slomson, Alan (2010), How to Count: An Introduction to Combinatorics, Discrete Mathematics and Its Applications (2 ed.), CRC Press, էջեր 51–60, ISBN 9781420082609
Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), «Set partitioning via inclusion–exclusion», SIAM Journal on Computing, 39 (2): 546–563, CiteSeerX 10.1.1.526.9573, doi:10.1137/070683933
Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice–Hall, ISBN 9780136020400
Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 0-521-45761-0
Fernández, Roberto; Fröhlich, Jürg; Alan D., Sokal (1992), Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory, Texts an Monographs in Physics, Berlin: Springer-Verlag, էջեր xviii+444, ISBN 3-540-54358-9, MR 1219313, Zbl 0761.60061
Graham, R.L.; Grötschel, M.; Lovász, L. (1995), Hand Book of Combinatorics (volume-2), MIT Press – North Holland, ISBN 9780262071710
Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman&Hall/CRC, ISBN 9781584887430
Hazewinkel, Michiel, ed. (2001) [1994], «Inclusion-and-exclusion principle», Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
Mazur, David R. (2010), Combinatorics A Guided Tour, The Mathematical Association of America, ISBN 9780883857625
Roberts, Fred S.; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, ISBN 9781420099829
Stanley, Richard P. (1986), Enumerative Combinatorics Volume I, Wadsworth & Brooks/Cole, ISBN 0534065465

Տես նաև

[Roberts_2009_loc=pg._405-1] Roberts & Tesman 2009, pg. 405

[2] Mazur 2010, pg. 94

[3] van Lint & Wilson 1992, pg. 77

[4] van Lint & Wilson 1992, pg. 77

[5] Rota, Gian-Carlo (1964), «On the foundations of combinatorial theory I. Theory of Möbius functions», Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2 (4): 340–368, doi:10.1007/BF00531932, S2CID 121334025

[6] Cameron 1994, pg. 78

[1]

[2]

[3]

[4]

[5]

[6]