7. óra
(2008.11.04.)
A beígért folytatás...
Halmazok partíciói
Egy n elemű halmaz nemüres halmazok diszjunkt uniójára való felbontásait keressük. Az {1, 2, 3, 4} halmaz partíciói:
$
\{1,2,3,4\} = \{1,2,3\}\cup\{4\} = \{1,2,4\}\cup\{3\} =
\{1,3,4\}\cup{2} = \{2,3,4\}\cup\{1\} = \{1,2\}\cup\{3,4\}
= \{1,3\}\cup\{2,4\} =
$
$
=\{1,4\}\cup\{2,3\} = \{1,2\}\cup\{3\}\cup\{4\} = \{1,3\}\cup\{2\}\cup\{4\} = \{1,4\}\cup\{2\}\cup\{3\}
= \{2,3\}\cup\{1\}\cup\{4\} =
$
$
=\{2,4\}\cup\{1\}\cup\{3\} = \{3,4\}\cup\{1\}\cup\{2\} = \{1\}\cup\{2\}\cup\{3\}\cup\{4\}
$
Partíció generáló algoritmus
Egy véges $\{1, 2, \ldots, n\}$ halmaz minden partícióija egyértelműen kódolható egy olyan $a_1, a_2,\ldots, a_n$ sorozattal,
melyre
$a_1 = 0, a_{j+1} \le 1 + max(a_1, \ldots, a_j) $ $ (1 \le j < n)$,
ahol
$a_j = a_k$ akkor és csak akkor teljesül,
ha $j$ és $k$ ugyanabba a részhalmazba esik,
továbbá $a_j~ $ a lehető legkisebb értéket kapja, amikor $j$ a legkisebb szám részhalmazában.
Például $n = 4$-re az alábbi kódolást kapjuk:
| partíció | kód | Partíció | kód | |
| {1234} | 0000 | {14}{23} | 0110 | |
| {123}{4} | 0001 | {1}{234} | 0111 | |
| {124}{3} | 0010 | {1}{23}{4} | 0112 | |
| {12}{34} | 0011 | {14}{2}{3} | 0120 | |
| {12}{3}{4} | 0012 | {1}{24}{3} | 0121 | |
| {134}{2} | 0100 | {1}{2}{34} | 0122 | |
| {13}{24} | 0101 | {1}{2}{3}{4} | 0123 | |
| {13}{2}{4} | 0102 |
Az algoritmus a $b_1,\ldots,b_n$ változók használatával generálja a partíciók kódjait, ahol $b_{j+1} = 1+\max(a_1, \ldots, a_j)$.
A C1 ciklus a kód utolsó elemét növeli, amíg lehet. Ha elérte a maximumot, a C2 ciklusban keresünk egy még növelhető elemet. Ha találunk ilyet, megnöveljük, és a mögötte lévő kódrész elemeit lenullázzuk.
$n = 3$-ra a következő sorrendben kapjuk meg a partíciók kódját:
000, 001, 010, 011, 012,
000, 001, 010, 011, 012,
Partíciók száma
| halmaz elemszáma | partíciók száma |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 15 |
| 5 | 52 |
| 6 | 203 |
| 7 | 877 |
| 8 | 4140 |
| 9 | 2114 |
| 10 | 115975 |
| 11 | 678570 |
| 12 | 4213597 |
| 13 | 27644437 |
| 14 | 190899322 |
| 15 | 1382958545 |
| 16 | 10480142147 |
| 17 | 82864869804 |
| 18 | 682076806159 |
| 19 | 5832742205057 |
| 20 | 51724158235372 |
| 21 | 474869816156751 |
| 22 | 4506715738447323 |