Կցման և արտաքսման սկզբունք

**Կցման և արտաքսման սկզբունք** կամ **կոմբինատոր գումարման սկզբունք** (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), չնայած այն առաջին անգամ հայտնվում է Դենիել դա Սիլվայի (1854) աշխատության մեջ, իսկ ավելի ուշ՝ Ջ.Ջեյ Սիլվեստրի (1883 թ.) աշխատության մեջ։ Երբեմն սկզբունքը կոչվում է Դա Սիլվայի կամ Սիլվեստրի բանաձև՝ իրենց հրապարակումների շնորհիվ։ Սկզբունքը կարելի է դիտարկել որպես թվերի տեսության մեջ լայնորեն օգտագործվող մաղի մեթոդի (sieve method) օրինակ և երբեմն կոչվում է մաղի բանաձև։

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

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

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

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

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

:\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 

կամ

:\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^} derangement): Ընդունելով, որ (n!)-ը դասավորությունների ընդհանուր քանակն է, կստանանք հաշվարկի շեղման պատահական առաջացման հավանականությունը, ստորև բերված բանաձևով։

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

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

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

:A_J:=\bigcap_{j\in J} A_j

ունի նույն հզորությունը, օրինակ՝  *α<sub>k</sub>* = |*A<sub>J</sub>*|, յուրաքանչյուր *k*-տարրային ենթաբազմության *J*-ի համար, որտեղ J-ն պատկանում է {1, ..., n}․ Ստացվում է․
:\left |\bigcup_{i=1}^n A_i\right|  =\sum_{k=1}^n (-1)^{k-1}\binom nk \alpha_k.

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

:\left |S \smallsetminus \bigcup_{i=1}^n A_i\right|  =\alpha_0 - \sum_{k=0}^n (-1)^{k-1}\binom nk \alpha_k.

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

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

: \sum_{J \subseteq [n]} (-1)^ |A_J|.

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

: \sum_{I \subseteq J} (-1)^ |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)^|B_K|.

Համապատասխանությունը *K* ↔ *J* = *I* ∪ *K* ենթաբազմությունների միջև, որտեղ  *K* ենթաբազմություն *N*&nbsp;\&nbsp;*I*-ի, իսկ *J* ենթաբազմություն է *N'-ի, որը պարունակում է *I*-ն, բիեկցիա է։ Եթե *J* և *K* համապատասխանում են այս համապատասխանության ներքո, ապա *B*<sub>K</sub> = *A*<sub>J</sub>, ինչը ցույց է տալիս, որ արդյունքը ճիշտ է։

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

:<math>\begin{align}
&\mathbf{1}_S: X \to \{0,1\} \\
&\mathbf{1}_S(x) = \begin{cases} 1 & x \in S\\ 0 & x \notin S \end{cases}
\end{align}</math>

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

:<math>\mathbf{1}_A \cdot\mathbf{1}_B = \mathbf{1}_{A\cap B}.</math>

Նշանակենք *A*-ն *A*<sub>1</sub>, ..., *An'' բազմությունների միավորում՝ \bigcup_{i=1}^n 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-ը պատկանում է որոշ «Am»-ին, ապա համապատասխան «mth» գործոնը 1−1=0 է։ Ընդլայնելով ձախ կողմի բազմապատկումը՝ ստանում ենք այս բաժնի 4-րդ հավասարությունը։

= Նշումներ =

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

= Տես նաև =
* Բազմությունների տեսություն
* Հավանականությունների տեսության պատմություն
* Դիսկրետ մաթեմատիկա

Կատեգորիա:Բազմությանների հզորություն
Կատեգորիա:Բազմությունների տեսության հիմնական հասկացություններ
Կատեգորիա:Դիսկրետ մաթեմատիկա
Կատեգորիա:Հավանականությունների տեսության և մաթեմատիկական վիճակագրություն
Կատեգորիա:Մաթեմատիկա
Կատեգորիա:Մաթեմատիկական տրամաբանություն