i i “Razpet-razkosanje” — 2010/6/1 — 9:20 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 15 (1987/1988) Številka 4 Strani 244–249 Marko Razpet: ŠTEVILO RAZKOSANJ KONČNE MNOŽICE Ključne besede: matematika, teorija števil, razkosanje množice, Stir- lingova števila druge vrste, Bellova števila, rekurzivne formule. Elektronska verzija: http://www.presek.si/15/902-Razpet.pdf c© 1988 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. STEVILO RAZKOSANJ KONČNE MNOŽICE V neki družini so štirje otroci : Anton, Berta, Ciril in Darja. Zelo radi se seveda igrajo. Nas pa zanima odgovor na vprašanje: Na koliko različnih načinov se lahko igrajo po skupinah (tudi en sam otrok že sestavlja skupino)? Med zavita oklepaja naštejmo, kateri otroci se lahko igrajo skupaj. Najprepro- stejša je možnost, da se sploh ne razdelijo: {Anton, Berta, Ciril, Darja} Kar na sedem različnih načinov se lahko igrajo v dveh skupinah: { Anton} {Berta, Ciril, Darja} { Berta 1 {Anton, Ciril, Darja} { Ciril} {Anton, Berta, Darja 1 fDarja} {Anton, Berta, Ciril} { Anton, Berta ~ { Ciril, Darja} { Anton, Ciril} { Berta, Darja 1 n. Hitro se vidi, da je SIn, 1) = 1 in SIn, n) = 1. Primer 2. Iz primera 1 razberemo: S( 1, 1) = 1, S(2, 1) = 1, S(2, 2) = 1, S(3 , 1) = 1,S(3, 2) = 3,S(3, 3) = 1, T(1) = 1, T(2) = 2, T(3) = 5. 2 računskega stališča bo najvažnejša povezava med števili SIn, ml, to je rekurzivna formula. Števila SIn, m) se v matematičn i literaturi imenujejo Stirlingava števila druge vrste, števila T(n) pa Bel/ava števila. Obstajajo tudi Stirlingova števila prve vrste, ki pa jih tu ne bomo obravnavali. Dokažimo izrek 1. Stirlingova števila SIn, m) povezuje rekurzivna formula: S(n+l,m) =mS(n,m) +S(n,m-l), m >2 (2) Dokaz . Naj ima množ ica B n elementov, množica A pa enega več, recimo ao. Množico A razkosamo v dveh korakih na m podmnožic. Najprej razkosamo množico B na m podmnožic, kar je mogoče narediti na SIn, m) načinov po shemi 245 , ... t ~ ,... {} t~,{} , ... {~ } Sin, m) Vsaki od teh podmnožic, ki so na shemi označene kar z zavitimi oklepaji, doda- mo element 80' Na ta način dobimo m Sin, m) razkosanj množice A na m pod- množic. S tem nismo dobili še vseh razkosanj množice A na m podmnožic. Manjkajo še tista, pri katerih je ena od nastopajočih podmnožic . { 80 \ • Do teh razkosan] pridemo tako, da razkosamo množico B na m-1 podmnožic, kar lahko naredimo na Sin, m-1) načinov po shemi m -1 ~ .{ 1, tJ , {\; {\ { L {\ , t~; {, ~ V zavite oklepaje za podpičji vstavimo element 80 ' S tem smo dobili še preosta- la razkosanja množice A na m podmnožic, torej Sin + 1, m) = m Sin, m) + +S(n,m-1). Zaradi rekurzivne formule, ki smo jo pravkar dokazali, lahko števila SIn, m) razvrstimo v trikotnik, ki ga bomo imenovali Stirlingov trikotnik druge vrste. V prvem stolpcu in na hipotenuzi tega trikotnika so same enice, ostala števila pa tvorimo po shemi: Sin.rn -1) +S(n,m).m =S(n+ 1,m) Začetek tega neskončnega trikotnika, kateremu dodamo še 8ellova števila, je takle: 246 1 1 2 3 1 5 7 6 1 15 15 25 10 1 52 31 90 65 15 1 203 63 301 350 140 21 877 I n 1 2 3 4 5 6 7 m 2 3 4 5 6 7 T(n) Stirlingova števila druge vrste SIn, m) in Bellova števila T(n) V nadaljevanju bomo posegli še po Pascalovem trikotniku, o katerem je bilo v Preseku že precej napisanega. Če ga zapišemo v prejšnjem stilu, dobimo: m O 2 3 4 5 6 1 2 1 3 3 1 4 6 4 1 5 10 10 5 1 6 15 20 15 6 n ----------------------------------------- O 1 2 3 4 5 6 Pascalov trikotnik Števila v Pascalovem trikotniku se imenujejo binomski koeficienti, ker se pojavljajo kot koeficienti v razvoju n-te potence binoma. Na križišču n-te vrstice in m-tega stolpca v Pascalovem trikotniku je binomski koeficient, ki ga označujemo s simbolom (~) in bere- mo "n nad m", Osnovni lastnosti binomskih koeficientov sta lastnosti simetričnosti in Pascalova identiteta : (n ) = (n ) ( n ) + (n) = (n + 1) m n-m' m-1 m m (3) Morda je bralec že opazil, da na prv i vzporednici hipotenuze v Stirlingovem trikotniku druge vrste ležijo trikotniška števila, o katerih je v Preseku tudi že bilo precej napisanega. Dokažimo trditev 1. Števila na prvi vzporednici hipotenuze v Stirlingovem trikotniku druge vrste so trikotniška števila, dana s formulo (4) za n = 2, 3, 4, 'OO • Dokaz. Formulo (4) dokažemo preprosto s popolno indukcijo . Za n = 2 je 5(2, 1) = 1 in 247 (~) = 1, torej formula drži. Sedaj je na vrsti indukcijski korak. Pr ivzemimo, da (4) drži za neko naravno število n > 2. Po formuli (2) dobimo: SIn + 1, n) = n SIn, n) + SIn, n - 1) = n + (~) = (~) + (~) Pascalova identiteta nam da končno SIn + 1, n) = (n; 1 ) kar je trditev (4) za število n + 1. Po principu popolne indukcije velja (4) za vsa naravna števila, večja od 2. Naloga 1. Na podoben način dokažite, da so števila na drugi vzporednici hipotenuze v Stirlingovem trikotniku druge vrste dana s formulo za n = 3, 4, 5, .... Naloga 2. Z nastavkom SIn, n - 2) = (~ ) + 3 (~) SIn, n - 3) = a (~) + b (~) + c (~) (5) za n = 4, 5, 6, ... poskusite najte formulo za števila na tretji vzporednici hipotenuze v Stirlingovem trikotniku druge vrste. Na vprašanje, kako se izražajo števila SIn, m) v zaključeni obliki, odgovorimo brez dokaza: m!S(n, m) = m" - (n;) (m - 1)n + (n;) (m - 2)n + ... + (_1)m-1 ( m~ 1) (6) Zanimivo je morda v zvezi s tem še tole: število mIS(n, m) je število vseh surjektivnih funkcij iz množice z n elementi na množico z m elementi. Bellova števila T(n) se izražajo še bolj komplicirano, z neskončno vrsto in s številom e (e = 2,71828 ..l: eTIn) = 1n/1! + 2nl2! + 3n/31 + '" (7) Pač pa lahko iz že znanih števil T(1), T(2), T(3) , .. ., T(n) izračunamo naslednje število Tin + 1) po formuli: T(n + 1) = 1 + (~) T(1) + (~) T(2) + ...+ (~) T(n) (8) Aitken je na podlagi te formule in Pascalove identitete ugotovil, da Bellova števila T(n) lahko izračunamo tudi s pomočjo trikotnika števil: 1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 52 248