Kümənin parçalanması

İlk $n$ təbii ədədlərdən ibarət çoxluğu nəzərdən keçirək: N_n = \{1, 2, \ldots, n\}. Bölünmə, bu çoxluğun bir və ya bir neçə boş olmayan alt çoxluqların birləşməsi şəklində təqdim edilməsidir. Məsələn, n = 5 üçün bölünmə nümunələri:

Ümumilikdə, N_5 çoxluğunun $52$ bölünməsi mövcuddur. Qeyd edək ki, yalnız birləşdirilən alt çoxluqların sırası ilə fərqlənən bölünmələr fərqli sayılmır.

N_n çoxluğunun bölünmələrini leksikoqrafik olaraq sıralamaq mümkündür.

Bu sıralamanı müəyyən etmək üçün əvvəlcə N_n alt çoxluqlarında leksikoqrafik sıralama müəyyən edilir. Deyirik ki, A \subset N_n, B \subset N_n üçün $A$ leksikoqrafik olaraq $B$-dən kiçikdir (yazılır A \prec B), əgər aşağıdakılardan biri doğrudursa:

• Elə bir $i$ tapılar ki, i \in A, i \notin B və bütün j < i üçün j \in A o və yalnız o halda ki, j \in B, və elə bir k < i tapılar ki, k \notin A, k \in B;

• A \subset B və bütün i \in A, j \in B \setminus A üçün i < j.

Aydındır ki, bu münasibət N_n çoxluğunun alt çoxluqlarında tam sıralamadır. İndi isə kanonik təqdimat bölünməsini, birləşdirilən çoxluqların leksikoqrafik olaraq sıralandığı təqdimat kimi müəyyən edək.

Bölünmələr leksikoqrafik olaraq aşağıdakı kimi sıralanır. N_n = A_1 \cup A_2 \cup \ldots \cup A_k bölünməsi, N_n = B_1 \cup B_2 \cup \ldots \cup B_l bölünməsindən leksikoqrafik olaraq kiçikdir, əgər elə bir $i$ varsa ki, A_1 = B_1, A_2 = B_2, ..., A_{i-1} = B_{i-1} və A_i \prec B_i.

N_n çoxluğunun bölünməsi üçün leksikoqrafik sırada növbəti bölünməni tapın.