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

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

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

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

Шынында, Х={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 жәшігін көрсетеді).

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

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

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

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

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, 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 (k1) (мұндағы әр X_i n_i элементтен тұрады) ішкі жиындарына бөлетін бөліктеулердің санын анықтайық:

2 - тұжырым. .

Шынында да, әрбір Х_i ішкі жиынын қайталанбайтын теру деп қарауға болады, олай болса,

Мысал. 25 адамнан тұратын топқа староста сайланды. 12 адам келісті, 10 қарсы болды, 3-і қалыс қалды. Мұндай сайлау қанша әдіспен жүргізіледі?

Енді 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}

Бұл бөліктеуде m₁=1, m₂=2, m₃=m₄=m₅=0.Аталған бөліктеулердің санын N(m₁, m₂, …, m_n) арқылы белгілейміз. 3 - тұжырым.

Қарастырылып отырған реттелмеген бөліктеудің әрқайсысын m₁!m₂!…m_n! тәсілмен төмендегі реттелген бөліктеуге түрлендіруге болады:

Ал реттелмеген бөліктеудің саны бұдан m₁!…m_n! есе аз.

Мысал. 25 адамнан тұратын топты әрқайсысы 5 адамнан 5 коалацияға қанша әдіспен топтастыруға болады? |X| = 25, m₁=…=m₄=0, m₅=5, m₆=…=m₂₅=0;

N(0, 0, 0, 0, 5, 0, …, 0) = =5194672859376.