10-Дәріс тақырыбы: Жиындарды бөліктеу (2 сағат)
Дәріс конспектісі:
n-элементті жиынды k ішкі жиынға бөліктеу деп  ,  , ij Хi, i= орындалатын { X1, X2, …, Xk } кез келген жиындар үйірін түсінеміз. Х-ті к блокқа бөлетін бөліктеулер жиынын Пк(х) деп белгілейік. |Пк(х)|. Бұдан әрине, S(n, k)=0 үшін kn; S(0, 0)=1 деп алынады. n-элементті жиынды К блокқа бөлетін бөліктеулер санын S(n, k) = |Пк(х)| белгілейміз.
1 - тұжырым. S(n, k)= S(n-1, k-1)+kS(n-1, k) егер 0kn; S(n, n)=1 егер n0 ; S(n, 0)=0 егер n0. S(n, k) саны II ретті Стирлинг саны деп аталады. Шынында да бірінші және үшінші формулалар түсінікті: 1 формуланы дәлелдеу үшін {1, 2, …, n} жиынын к блокқа бөлетін барлық бөліктеулердің жиынын қарастырамыз. Бұл жиын үлкен 2 класқа бөлінеді: бір элементті {n} блогы бар бөліктеулер және n-қуаты 1 деп үлкен блоктың элементі болып саналатын бөліктеулер. Бірінші класта S(n-1, k-1) блок бар, ал екіншісінде S(n-1, k). Себебі бұл кластың {1, 2, …, n-1} жиынын к блокқа бөлетін әр бөліктеуінде бұл класта әр блокқа кезекпен n элементін қосудан алынған к бөліктеуі сәйкес келеді. Мысалы, S(4, 2) = S(3, 1) + 2S(3, 2) = 1 + 2(S(2, 1) + 2S(2, 2)) = 1 + 2(1+2) = 7.
Егер Х = {1, 2, 3, 4} онда бұл жиынды 2 блокқа бөлетін 7 бөліктеу төменгідей:
{{1, 2, 3}, {4}} ;{{2, 3, 4}, {1}};{{1, 2, 4}, {3}};{{1, 2}, {3, 4}};
{{1, 3, 4}, {2}};{{1, 4}, {2, 3}}; {{1, 3}, {2, 4}};II ретті Стирлинг сандарын үшбұрышты кесте түрінде орналастыруға болады:
k
n
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
…
|
1
|
1
|
|
|
|
|
|
|
…
|
2
|
1
|
1
|
|
|
|
|
|
…
|
3
|
1
|
3
|
1
|
|
|
|
|
…
|
4
|
1
|
7
|
6
|
1
|
|
|
|
…
|
5
|
1
|
15
|
25
|
10
|
1
|
|
|
…
|
6
|
1
|
31
|
90
|
65
|
15
|
1
|
|
…
|
7
|
1
|
63
|
301
|
350
|
140
|
21
|
1
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
…
|
Кестенің шеткі бірлерден басқа әр элементі есептелетін элементтен жоғарғы жолда орналасқан санды к-ға көбейтіп, оның сол жағындағы элементпен қосқаннан алынады.
Енді ақырлы Х жиынын Х1, Х2, …, Хk (k1) (мұндағы әр Xi ni элементтен тұрады) ішкі жиындарына бөлетін бөліктеулердің санын анықтайық:
, , ij Хi=ni, i= ; спектісі.ы. ады.  екені белгілі. Кейбір i нөмірі үшін Хi= болуы мүмкін. Тұрақатн ni үшін бөліктеулер санын  деп белгілейік (Мұндағы бөліктеулердегі ішкі жиындар жиынтығы реттелген жиындар тізбегі болып табылады.
2 - тұжырым.  =  .
Шынында да, әрбір Хi ішкі жиынын қайталанбайтын теру деп қарауға болады, олай болса,
=    …  =
Мысал. 25 адамнан тұратын топқа староста сайланды. 12 адам келісті, 10 қарсы болды, 3-і қалыс қалды. Мұндай сайлау қанша әдіспен жүргізіледі?  =  = 1487285800.
Енді i=1, 2, …, n үшін әрқайсысында i элементі бар mi ішкі жиыны бар болатын ( )|X|=n, Х жиынын қанша ішкі жиынға бөлуге болатынын есептейік: Мұнда алдыңғы жағдайға қарағанда ішкі жиындарды таңдау реттелмеген. Мысалы, Х = {1, 2, 3, 4, 5}жиыны үшін келесі үш бөліктеу бірдей.
{1, 3}, {4}, {2, 5}; {4}, {2, 5}, {1, 3}; {2, 5}, {4}, {1, 3}
Бұл бөліктеуде m1=1, m2=2, m3=m4=m5=0.Аталған бөліктеулердің санын N(m1, m2, …, mn) арқылы белгілейміз. 3 - тұжырым. N(m1, m2, …, mn) = 
Қарастырылып отырған реттелмеген бөліктеудің әрқайсысын m1!m2!…mn! тәсілмен төмендегі реттелген бөліктеуге түрлендіруге болады:
 мұндағы,
 = . Мұндай реттелген бөліктеудің саны:  
Ал реттелмеген бөліктеудің саны бұдан m1!…mn! есе аз.
Мысал. 25 адамнан тұратын топты әрқайсысы 5 адамнан 5 коалацияға қанша әдіспен топтастыруға болады? |X| = 25, m1=…=m4=0, m5=5, m6=…=m25=0;
N(0, 0, 0, 0, 5, 0, …, 0) =  = 5194672859376.
Ендіру және шығару формуласы. Жиындарды бөліктеу Айталық, Х1, Х2 – ақырлы жиындар берілсін. Егер Х1Х2 = , онда |Х1Х2| = |Х1|+|Х2|. Егер Х1Х2 , онда |Х1|+|Х2| жиынында Х1Х2 алынған элемент 2 рет есепке алынады, демек |Х1Х2| = |Х1|+|Х2| - | Х1Х2|.
Кез келген жиын үшін ендіру және шығару формуласын қорытайық:
4 - тұжырым. Хi ; i = 1, …, n, n2 ақырлы жиындары берілсін. Олай болса |X1X2…Xn| = (|X1| + … + |Xn|) – (|X1X2| + |X1X3| + … + |Xn-1Xn|) + (|X1X2X3| + … + |Xn-2Xn-1Xn|) - … + (-1)n+1|X1X2…Xn|.
Салдар. Айталық Х – ақырлы жиын болсын, Х1, …, Хn – Х-тің ішкі жиындары. Онда ішкі жиындардың ешбіріне тиісті емес хХ элементтердің саны мына
|X \ ( X1X2…Xn)| = |X| - (|X1| + … + |Xn|) + (|X1X2| + … |Xn-1 Xn|) - … - (-1)n|X1…Xn| формула бойынша есептеуге болады.
Ендіру және шығару формуласын жазудың кең тараған формасы төмендегідей. Айталық, Х N элементтен тұратын ақырлы жиын, 1, …, n Х-тің элементтерінде бар болуы да, болмауы да мүмкін қасиеттер. Xi арқылы i қасиеттері бар элементтерден құралған жиынды белгілейміз. Яғни Хi = {xX | i(x)}, i=1…, n.
N( ) арқылы қасиеттерінің бәріне ие Х элементтерінің санын белгілейік:
N() = |  |. 1, …, n қасиеттердің ешқайсысы жоқ элементтің санын N0 = | X \ (X1…Xn) | деп белгілейік. Олай болса
N0 = N–S1 +S2 - …+ (-1)nSn = N + , мұндағы Sk =  , k=1, …, n.
Мысалы, егер n=3,ондаN0 = N– N(1) – N(2) – N(3) + N(1,2) +N(1, 3) + N(2, 3) – N(1, 2, 3).
Мысал. Айталық, Х = {1, 2, …, 10}, 1(x) : "х – жұп", 2(х) : "x>6", 3(x) : "20 есептейік. N0 = 10-5-4-5+2+2+1-0=1 (шынында, Х-ң ешқандай қасиеті жоқ элементі 1 i, i = 1, 2, 3).
Ендіру және шығару формуласын шығарып пайдаланатын тағы бір есепті қарастырайық.
Тәртіпсіздік туралы есеп. Әр түрлі а1, а2, …, an n зат және әр түрлі b1, b2, …, bn жәшіктер бар. ai заттарының ешқайсысы bi жәшігіне түспейтіндей етіп, ai бұйымдары қанша әдәспен жәшіктерге салуға болады? Басқаша айтсақ, кез келген i = 1, 2, …, n үшін aii болатындай
1
|
2
|
…
|
i
|
…
|
N
|
a1
|
a2
|
…
|
ai
|
…
|
an
|
1, 2, …, n сандарының қанша алмастырулары a1, a2, …, an бар? Яғни кез келген элементтің образы өзінің образына тең болмайтындай қанша алмастыру бар?
Берілген Х жиыны ретінде бұйымдардың жәшіктерге барлық мүмкін орналасуларының жиынтығын аламыз.Олай болса N=| X |=n! i қасиеттерін енгізейік: "ai bi жәшігінде бар", i = 1, …, n. N() саны ij бұйымы bij j = 1, …, k жәшігінде бар болатын орналасулар (n-k)!-ға тең.
Бірақ онда k бұйымның өздерінің Sk жәшіктеріне түсетін орналасулар саны:
Sk = 
Енді ендіру және шығару формуласын пайдаланып, ешқандай қасиет орындалмайтын (яғни ешқандай ai  бұйымы bi жәшігіне түспейді) орналасу саны:
N0=N+ .
Жақшадағы өрнек - е-1 шексіз қатар жіктеуінің 1-ші мүшелері, ендеше  - n символдан тұратын тәртіпсіздіктер санына жақсы жуықтайды.
Егер бізді тәртіпсіздіктің саны ғана емес, аi=i дәл k орында болатын, 1, 2, …, n құралған а1, …, an алмастырулардың санын да анықтау керек болса, онда «кездесу» деп аталатын басқа есеп туады. Оның шешімі: n-нен k санды  тәсілмен таңдауға болады, таңдағаннан кейін оны қалған n-k символдағы тәртіпсіздіктердің санына көбейту керек. Сонда
Nk =  
 .
Негізгі әдебиет: 1[136-143]; 2[164-166].
Қосымша әдебиет: 7[50-80] .
Бақылау сұрақтары:
1.Сізге жиындарды бөліктеудің қандай типтері белгілі?
2. Стирлинг саны қалай есептеледі?
3. 4 жиын үшін ендіру және шығару формуласын құрыңыз.
4. Тәртіпсіздік туралы есепті сипаттаңыз.
5. Кездесу есебін келтіріңіз.
Достарыңызбен бөлісу: |
