Жұмыс бағдарламасы (силлабус) осы мамандықттардың Қр мжмбс 08. 329-2006, Қр мжмбс 08. 33-2006 Мемлекеттік стандартына сәйкес құрылған


Орналастыру және функционал бейнелеу



бет79/214
Дата13.02.2017
өлшемі21,8 Mb.
#9109
түріМазмұндама
1   ...   75   76   77   78   79   80   81   82   ...   214
Орналастыру және функционал бейнелеу.

Комбинаторикалық классикалық есептерінің бірі, қандай да бір объектілердің «жәшіктерде» белгілі бір шектеулер орындалатындай орналастыру санын анықтау болып табылады. Бұл есепті төмендегідей тұжырымдауға болады:



Айталық Х = r, Y = n. Барлық бейнелеулер f : X  Y санын YХ белгілейік. Берілген шектеулерді қанағаттандыратын қанша f : X  Y функционал бейнелеулер бар? Егер бұл бейнелеулерге шектеулер жоқ болса төмендегідей тұжырым келтіруге болады.

5-тұжырым. YХ  = = nr = YX.

Шынында, Х={x1,…,xr} болсын. Олай болса кез келген бейнелеуді f:ХY реттелген (f(x1), f(x2),…,f(xr)), мұндағы f(xi)Y, тізбегі түрінде кескіндеуге болады, яғни біз функционал бейнелеулер мен саны nr-ге тең, көлемі n болатын Y жиынынан алынған қайталанба реттелген таңдамалар жиынының арасында өзара бір мәнді сәйкестік орнаттық.

(Егер Х - объектілер, Y- "жәшіктер" болса, онда f функция әрбір хХ объектісі үшін объект орналасқан f(x)Y жәшігін көрсетеді).

Бірден артық емес объект орналасқан жәшігі бар орналасудың санын табу қиын емес, ондай теру бір мәнді функцияларға сәйкес (инъективті бейнелеу).



6-тұжырым. Иньективті бейнелеулердің f:XY(яғни f(x1)=f(x2)х12) саны .

Шынында да, бұл жағдайда реттелген тізбек (f(x1), f(x2), …, f(xr)) әр түрлі болуы керек, яғни бұл тізбек қайталанбайтын теру болып табылады.



Салдар. Егер Sn - өзіне өзін бейнелейтін n-элементті барлық биективті бейнелеулердің жиыны болса олардың саны |Sn|

Негізгі әдебиет: 1[130-134]; 2[159-164].

Қосымша әдебиет: 7[50-80] .

Бақылау сұрақтары:

Қосу, көбейту ережелерін атаңыз.

Реттелген, реттелмеген таңдамалар қалай аталады?

Орналасу, теру сандарын қандай формулалармен есептеуге болады?

Қанша функционал бейнелеулер f : X  Y бар?

Өзіне өзін бейнелейтін қанша биективті бейнелеу құрастыруға болады?

10-Дәріс тақырыбы: Жиындарды бөліктеу. (2 сағат)



Дәріс конспектісі:

n-элементті жиынды k ішкі жиынға бөліктеу деп , , ij Хi, i= орындалатын { X1, X2, …, Xk } кез келген жиындар үйірін түсінеміз. Х-ті к блокқа бөлетін бөліктеулер жиынын Пк(х) деп белгілейік. |Пк(х)|. Бұдан әрине, S(n, k)=0 үшін kn; S(0, 0)=1 деп алынады. n-элементті жиынды К блокқа бөлетін бөліктеулер санын S(n, k) = |Пк(х)| белгілейміз.

1-тұжырым. S(n, k)= S(n-1, k-1)+kS(n-1, k) егер 0kn; S(n, n)=1 егер n0 ; S(n, 0)=0 егер n0. 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   ...   75   76   77   78   79   80   81   82   ...   214




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет