Liczby Stirlinga II rodzaju (dla podzbiorów)

Opisują liczbę sposobów podziału zbioru n elementowego na k niepustych podzbiorów.

Symbol Stirlinga Liczby Stirlinga II. Czytamy "k podzbiorów n".

Wiemy, że:

Liczby Stirlinga II

Liczby Stirlinga II

Dla n > 0:

Liczby Stirlinga II

Liczby Stirlinga II

Liczby Stirlinga II

Dla n < k:

Liczby Stirlinga II

Dla n = k:

Liczby Stirlinga II

Kolejne liczby obliczamy z rekurencyjnego wzoru:

Liczby Stirlinga II dla n > 0

Aby ułatwić zapis sprowadzimy liczby do parteru:

Liczby Stirlinga II

Wykonajmy parę obliczeń:

Liczby Stirlinga II

 

Liczby Stirlinga II

Liczby Stirlinga II

 

Liczby Stirlinga II

Liczby Stirlinga II

Liczby Stirlinga II

 

Liczby Stirlinga II

Liczby Stirlinga II

Liczby Stirlinga II

Liczby Stirlinga II

Możemy to ująć w tabelce:

Liczby Stirlinga II rodzaju
n\k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
0 1                         
1 01                        
2 011                       
3 0131                      
4 01761                     
5 011525101                    
6 01319065151                   
7 0163301350140211                  
8 0112796617011050266281                 
9 012553025777069512646462361                
10 0151193303410542525228275880750451               
11 0110232850114575024673017948763987118801155551              
12 0120478652661150113794001323652627396159027222751705661             
13 01409526162525325307508501932131257154241899612359502393252431781            
14 01819178897010391745400750356343637349329280209123205135130752752660663367911           
15 01163832375101423559502107669204206932734087413332166278406712849012662650147947810647045501051          
16 01327677141686171798901109619055027349265583281882604214176405382078425019375499028936908275711816562060201201         
17 01655352145782569433729056527516511750574989825708104786204159950289528822303275833415051206097862022324491017824990078201361        
18 01131071644390102798806985289580955451106872510391974624834001890360650101061753957553711216380383910049081256328866125854638840877836720099961531       
19 012621431934481011125966695014758928471069308160177914929246348391709751003480114461462680547729703378512941321779123466951300289243916024357753013916778527136125971711      
20 015242875806064464523211590174920609050043060788953841114355404565215170932662679120112826447255917584964655190084242948641101663339161068660380630252458045232920022350954741285156751901     
21 01104857517423436251815090700503791262568401265856794628048231095721494813251101534708412327247646520471187132291275268268516890016833042030178120490921833114930400450013087462580809944464349527991023435192852101    
22 01209715152280794507277786238251913782191205516330533934522560276237996744011423990799916201241963303533920835143799377954366282500870286108823356051137224968618684813295165281331345615943200260465740041404142047533746291389850234852311   
23 014194303156863355012916342574750964168881841009989698579834054382641999117305974195501990040012320068811796900959340129731346048642513089511001672162773483930401282560341390686291758071158479404429331762361127264499169888032364885369797817791859550283362531  
24 0183886074706320080611681056634501485000783495250609023603608453031677463851804540823182821583205051206225743260725001082540817849315006310016569577556024930204590758260688883605792200013620910216410001958202422470802067718246555516109499369159248492544538807391701169727792454606339022761 
25 0116777215141197991025467712897388102436684974110751370264170000024302278324829987163106902237211183685801167921451092973005120316339217538750080235590443846266036226262078487468011448507334374426025958110360896000429939465534720052665516169596048063331393110327567859492516621896967562201947501685195053200450402503001

Równoważnym wzorem jest:

Liczby Stirlinga II

Przykład

Liczba podziałów zbioru 4 elementowego złożonego na 2 elementowe podzbiory wynosi 7 .

Możemy je wszystkie wypisać, aby to sprawdzić:

{0,1,2}{3}
{0,1,3}{2}
{0,2,3}{1}
{1,2,3}{0}
{0,1}{2,3}
{0,2}{1,3}
{0,3}{1,2}

Sprawdzamy:

Start
7
Koniec