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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.