Лабораторна робота 34-c
Відновлення розбиття за його номером
(використання дерева пошуку)
Для множини {1, 2, 3, . . . , 31, 32}
розбиттям з номером 58064670049908713818925644 буде
{1, 5, 31} {2, 10, 11, 12, 30} {3, 18, 22} {4, 17, 28} {6, 14, 20, 32} {7, 9, 16} {8, 15} {13, 29} {19} {21, 23} {24, 25} {26, 27}
До речі, кількість розбиттів для множини {1,...,n} визначається числами Белла:
n | Bell(n) |
1 | 1 | 2 | 2 | 3 | 5 | 4 | 15 | 5 | 52 | 6 | 203 | 7 | 877 | 8 | 4140 | 9 | 21147 | 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 | 23 | 44152005855084346 | 24 | 445958869294805289 | 25 | 4638590332229999353 | 26 | 49631246523618756274 | 27 | 545717047936059989389 | 28 | 6160539404599934652455 | 29 | 71339801938860275191172 | 30 | 846749014511809332450147 | 31 | 10293358946226376485095653 | 32 | 128064670049908713818925644 | 33 | 1629595892846007606764728147 | 34 | 21195039388640360462388656799 | 35 | 281600203019560266563340426570 | 36 | 3819714729894818339975525681317 | 37 | 52868366208550447901945575624941 | 38 | 746289892095625330523099540639146 | 39 | 10738823330774692832768857986425209 | 40 | 157450588391204931289324344702531067 | 41 | 2351152507740617628200694077243788988 | 42 | 35742549198872617291353508656626642567 | 43 | 552950118797165484321714693280737767385 | 44 | 8701963427387055089023600531855797148876 | 45 | 139258505266263669602347053993654079693415 | 46 | 2265418219334494002928484444705392276158355 | 47 | 37450059502461511196505342096431510120174682 | 48 | 628919796303118415420210454071849537746015761 | 49 | 10726137154573358400342215518590002633917247281 | 50 | 185724268771078270438257767181908917499221852770 |
|