Olkoot A ja B epätyhjiä äärellisiä joukkoja, |A| = k ja |B| = n. Montako erilaista surjektiivista kuvausta on A:lta B:lle?
Meneekö kotikonstein vai tarviiko työllistää jotain hienompaa koneistoa?
Meneekö kotikonstein vai tarviiko työllistää jotain hienompaa koneistoa?
Vastaukset 1
Vanhimmat
Surjektioiden määrä voidaan lausua toisen luokan Stirlingin lukujen avulla.
Nämä Stirlingin luvut S(k,n) määritellään niiden tapojen lkm:nä, joilla k:n alkion joukko voidaan jakaa n:än epätyhjään osajoukkoon. Tällöin surjektioita k:lta n:lle on n!S(k,n)
(jokaiselle n:lle osajoukolle valitaan yksi kuva-alkio n:stä mahdollisesta).
Stirlingin luvuille on kaavoja ja rekursioyhtälöitä. Näitä käyttäen saadaan esim. seuraava kaava surjektioiden määrälle:
n!S(k,n) = Sum_i [(-1)^i nCr(n,i)(n-i)^k],
missä Sum_i on summa i=0,...,n ja nCr(n,i) on binomikerroin "n yli i".
Googleta "Stirling numbers of the second kind", jos kiinnostaa enemmän.