Ендіру және шығару формуласы. Жиындарды бөліктеу

Кез келген жиын үшін ендіру және шығару формуласын қорытайық:

4-тжырым. Х_i; i=1,…,n, n2 ақырлы жиындары берілсін. Олай болса |X₁X₂…X_n|=(|X₁|+…+|X_n|)–(|X₁X₂|+|X₁X₃|+…+|X_n-1X_n|)+(|X₁X₂X₃|+ …+|X_n-2X_n-1X_n|)-…+(-1)ⁿ⁺¹|X₁X₂…X_n|.

Салдар. Айталық Х – ақырлы жиын болсын, Х₁, …, Х_n – Х-тің ішкі жиындары. Онда ішкі жиындардың ешбіріне тиісті емес хХ элементтердің саны мына

|X\(X₁X₂…X_n)|=|X|-(|X₁|+…+|X_n|)+(|X₁X₂|+… |X_n-1X_n|)-…-

(-1)ⁿ|X₁…X_n| формула бойынша есептеуге болады.

Ендіру және шығару формуласын жазудың кең тараған формасы төмендегідей. Айталық, Х N элементтен тұратын ақырлы жиын, ₁,…, _n Х-тің элементтерінде бар болуы да, болмауы да мүмкін қасиеттер. X_i арқылы _i қасиеттері бар элементтерден құралған жиынды белгілейміз. Яғни Х_i = {xX | _i(x)}, i=1…, n.

N( ) арқылы қасиеттерінің бәріне ие Х элементтерінің санын белгілейік:

N( )=| |. ₁,…,_n қасиеттердің ешқайсысы жоқ элементтің санын N₀=|X\(X₁…X_n)| деп белгілейік.

ОлайболсаN0=N–S1+S2-…+(-1)nSn=N+ ,

мұндағыS_k= , k=1,…,n.

Мысалы, егер n=3,ондаN₀=N–N(₁)–N(₂)–N(₃)+N(₁,₂)+N(₁, ₃)+N(₂,₃)–N(₁, ₂, ₃).

Мысал.Айталық,Х={1,2,…,10}, ₁(x):"х–жұп", ₂(х):"x>6", ₃(x):"20 есептейік. N₀ = 10-5-4-5+2+2+1-0=1 (шынында, Х-ң ешқандай қасиеті жоқ элементі 1 _i, i = 1, 2, 3).

Ендіру және шығару формуласын шығарып пайдаланатын тағы бір есепті қарастырайық.

Тәртіпсіздік туралы есеп. Әр түрлі а₁, а₂, …, a_n n зат және әр түрлі

b₁, b₂,…, b_n жәшіктер бар. a_i заттарының ешқайсысы b_i жәшігіне түспейтіндей етіп, a_i бұйымдары қанша әдәспен жәшіктерге салуға болады? Басқаша айтсақ, кез келген i=1, 2, …, n үшін a_ii болатындай

1, 2, …, n сандарының қанша алмастырулары a₁, a₂, …, a_n бар? Яғни кез келген элементтің образы өзінің образына тең болмайтындай қанша алмастыру бар?

Берілген Х жиыны ретінде бұйымдардың жәшіктерге барлық мүмкін орналасуларының жиынтығын аламыз.Олай болса N=| X |=n! i қасиеттерін енгізейік: "ai bi жәшігінде бар", i=1,…,n. ) саны ij бұйымы b_ij j=1,…,k жәшігінде бар болатын орналасулар (n-k)!-ға тең.

Бірақ онда k бұйымның өздерінің S_kжәшіктеріне түсетін орналасулар саны:

S_k =

Енді ендіру және шығару формуласын пайдаланып, ешқандай қасиет орындалмайтын (яғни ешқандай ai бұйымы bi жәшігіне түспейді) орналасу саны:

N₀=N+ .

Жақшадағы өрнек - е-1 шексіз қатар жіктеуінің 1-ші мүшелері, ендеше

Егер бізді тәртіпсіздіктің саны ғана емес, а_i=i дәл k орында болатын,