i
i
“458-Kramar-naslov” — 2009/6/10 — 9:20 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 8 (1980/1981)
Številka 1
Strani 13–18
Edvard Kramar:
ŠTEVILO RAZDELITEV ENAKIH PREDMETOV NA
SKUPINE
Ključne besede: matematika, kombinatorika, razdelitve, množica.
Elektronska verzija: http://www.presek.si/8/458-Kramar.pdf
c© 1980 Društvo matematikov, fizikov in astronomov Slovenije
c© 2009 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.
šTEVILO RAZDELITEV ENAKIHPREDMETOV NA SKUPINE
Dedek Mraz je pri pripravljanju daril za otro ke imel še 10 po-
maran č, ki j i h je hot e l dodat i v t r i v re čk e , ki še niso bil e
zap rte . Ker je ho t e l biti či m bolj prav ič en, j e na j pr ej pois -
kal vse možne por a zde l i t ve teh pomaranč na tri k u p č k e . Dobil
j e 8 raz de l i t ev : 8+1+1, 7+2+1, 6+3+1, 6+2+2, 5+3+2 , 5+4+1,
4+4+2, 4+3+3 . Naz adnj e se je od l o č i l za eno od teh mož nosti in
kup čke razde lil v najprimernejše vreč ke . Zastav i l pa s i je
vpra šan je, a l i s e da že vna prej ugo t ov i t i , koliko je ta ki h po-
razdelitev pri , danem š t evi l u pom aranč, da pri grupiran ju ne bi
mo r d a poza bi l na ka kšno r az del i t ev .
Posku sim o pr ob lem, na ka t ere ga je naletel Dedek Mraz, rešiti
za s pl oš nejš e pr i mere . Vp r aš a j mo se, na kolik o nač i no v lahk o
nar ed imo iz n e na ki h pr edmetov k s kupi n. Lahko bi tud i r e kl i ,
na kol i ko nač inov lah ko pišemo dan o š t ev i l o n na k pozit ivni h
sumanda v , pr i č emer vr s t ni red s uma ndcv n i va žen (na primer
razd el itvi 6 = 1+2+3 in 6 = 2+3+1 sta za nas isti) .
Na me s to zgor nj e nal oge s i naj prej ogl e jmo ne koli ko spremenjen o
na logo, ven dar bomo l ahko i z r ešitv e t e naloge takoj i zpeljali
tudi ~eš i t e v za pr vo t no . Vpr a š a nj e je, na kol ik o n ač i no v la hko
r azde l i mo n enakih predmetov na k večje mu k s kupin . O z n a či m o z
r k (n ) š t evi l o teh možnosti . č e p r a v je vpra š anje zelo l ahko r ~
zuml j i vo, ni lah ko dobiti f ormulo za š t ev i l o rk(n ) za polju~
ni nar avni š t ev i l i n in k . Pokazali bomo pot do t a ke f or mule
za najbolj prepr oste pr i mere. Dogovorimo s e še, da pr i zapisu
porazdel i te v ni čelnih čl e n o v ne bomo pisal i, razen pri razd e li
t vi š te v i l a O (O = O) . Tore j bom o zapi sa li 6 = 4+2 namest o
6 = 4+2+0+0 .
Najp r ej je oč i t no r l"(n ) = 1 za vsak o š t ev ilo pre dmetov . Tudi
do š t ev ila r2( n) bomo hitr o pr iš li . Naj bo najprej n s odo
št ev i lo , pot em imamo nas l ednje raz de litve št ev i la n :
n = n , n = (n-1) + 1, . .. , n = nl 2 + nl 2
13
to re j n l 2 + 1 = ( n+2 )/2 možnosti. Pri l i hem n pa dobimo
n ::: n , n ( n -1 ) + 1 n = ( n+ 1 )/2 + ( n - 1 ) / 2
s e prav i ( n - l)/ 2 + = (n +1)/ 2 možnost i , Oba rezult a ta l ah ko
za pišemo z e no f or mu l o na pr i mer t a kole :
l" 2 ( n ) = ( n+ 1+( 1+( - 1 ) n ) / 2 ) / 2
Pri t em smo mo r a l i pi s a t i s umand ( 1+(- 1) n)/ 2 , ki ur avn av a
f or mul o za prime r sodega i n pr imer li hega š te vil a n . Za pra kt i
čno ra bo lah ko zgornji iz r a z š e poeno stavim o , č e vpe l jemo na s -
ledn j i sim bo l : za dani št evil i m in n na j bo O( m, n ) = 1 , če
j e n de l j i v z m in O(m, n ) = O , če ni de l jiv t er O(m, O) = 1.
Pri tem sta m in n po l ju bn i nara vn i š t ev i l i . S to oznako la hko
zgor nj o f or mu l o pišemo v obli ki
l" 2 ( n) = ( n+1+0( 2 , n) )/2
To f or mu lo smo i zpel jali za n = 2 , 3 , . . . , ve l ja pa t ud i za
n = O in n = 1 , ka j t i ted a j dobim o 1" 2 (0 ) =1" 2(1 ) =1 . ka r je
smise lno, s aj imata ti š t ev i l i le po eno razd elitev: O = O ,
1 = 1 .
Ogle jmo si še, do kak š nega obr azca pr i demo za š t ev i l o r azde li-
t ev n pr edmetov na k v e č jem u 3 skupine. Do š t evi l a l" 3 (n ) bomo
pr išli v več kor ak i h , pr i te m pa s i bomo pomag a l i z že i zpe l j s
no f ormul o za l" 2 (n ) . Mi s l imo si , da mor amo n ena kih krog el
razdelit i na k v e č j e mu 3 k upč k e . Vse mo žn e n a č i n e l ahko dobi mo
tak ole: Najp r e j po iščemo vse r azde litve na kve čjemu dva k upčk a,
t eh ra zd elit ev j e l" 2( n ) in jih lahk o štejemo za razdelit ve
na k ve čj emu 3 ku p čk e , pri č e m er j e e n k u p ček pra zen . V druge m
kor a ku damo na vs a kega od t r eh k u p č k o v po eno kr ogl o , pr eost a-
l i h n -3 krog e l (č e j e n > 3) pa r azde li mo t a ko, da jih damo
ka korko li na kv ečj e mu dva k u p čk a . števi l o ra zde l i t ev na t em kQ
ra ku j e en ak o l" 2 ( n -3 ) in vse te ra zde li t ve s o o či t no dr ug ač ­
ne od ra zd el i t ev v prve m kora ku . V t retjem kor ak u d amo najprej
na vsak kupče k po dve kr og l i , č e jih je dovol j, pr eost ale pa
porazdelimo na kv e č j e m u pr va dva k u pčk a . S tem dobim o še
14
r 2(n-6) porazdel itev. Ta postopek ponavlj amo tako do lgo, dok -
l e r nam ne zmanjka krogel . Oč itn o so ra zdelitve , ki j ih do bimo,
vse r a zl ičn e . š t ev i l o razdel i te v r 3( n) torej l ah ko izrazi mo
z zvezo
kj er č l en e pri šte va mo t a ko dol go, dokl er j e š t ev i l o v okl epaj u
še v e č j e al i enako n ič . Pr i tem š e upošt evamo r 2(0) = r2( 1) =
= 1 •
Za ilu stra ci jo si oglej mo zg or nj i posto pe k pr i n = 8 . Naj -
pr ej imamo rz(8 ) 5 razdelite v na k v eč jemu dva dela : 8 = 8 ,
8 = 7+ 1, 8 = 6+2, 8 5+3, 8 = 4+4 . Te razd e l itve l ahko š tej§
mo tu d i za razde l itve na k v ečjemu t r i del e . V dr ugem korak u de
mo na vsa k kup če k po en o kro g lo , os t a l ih 5 pa razdel imo na kv§
čjemu dva de l a : 5 = 5, 5 = 4+1 in 5 = 3+2 č e upoštevamo ,
da imamo na vsakem , k upčk u že po eno kro g lo, dobim o : 8 = 6+ 1+1,
8 = 5+2+1 i n 8 = 4+3+1, tor ej še r2 (8 - 3 ) = r 2 ( 5 ) = 3 raz de l i
t ve . Na za dnje damo na k u p č e k po dve kr ogl t , pr e ostal i dve pa
na k v e č j e m u dva kupčka: ' 2 = 2 , 2 = 1+1 . Vid imo , da i mamo na -
zad nje še 2 = r 2(8 -6) možnost i: 8 4+2+ 1 i n 8 3+3 +2.
Vs eh r a zdeli t ev j e tore j r 3 (8 ) = 5 + 3 + 2 = 10
če bi s edaj v zgor nj o zvezo vs t av i l i zapo redom a vs e i zr aze , ki
ve ljajo za r 2( n ) , r 2 (n-3) i t d , bi do b i l i kon čno form ulo za
št ev i lo razde l itev r 3( n) . Ker pa je pot do končne ob like do-
kaj zamudna, j o r aje kar zapišimo, spodaj pa bomo po kaza l i, ke
ko to f ormulo lah ko dok a žemo s popolno indukcijo
r 3( n) = (n 2+6 n+5 +3D(2, n)+4D(3, n))/ 12
če si ogledam o zvez o med št evilom porazdelitev na kvečje mu 3
dele i n med števi li porazde litev na k v e č j e m u 2 de la, opaz imo,
da i mam o 3 raz l)čne s ituacije g l~ d e na t o , kakš en osta nek dob!
mo, č e števi lo n de limo s 3 . Zato l o či m o t ri možnosti: n = 3s,
n = 3s+ 1 in n = 3s+2 . For mul a za r3 (n ) ima tedaj tr i ob li ke
15
r 3(3 8} ~
r 3 ( 38+ 1)
r 3(3 8+2 }
( 3 8 ~+ 6 8 + 3 +0 ( 2, 3 8 } } / 4
( 38 2+88+4+0(2 ,3 8+1}}/4
( 38 2+108+7+0( 2 ,3 8+2 }}/ 4
kj e r s mo izr az e š e ok raj šali s 3 . Vs ako od t e h f or mul bi bil o
t r e ba do ka za t i z ind ukci j o. Oa ve l j ajo vse tr i pr i 8 ~ 1 , se
z l a hka p rep r i č amo : r3 ( 3 ) ~ 3 , r 3(4} ~ 4 i n r 3( 5} ~ 5 . Ko t vg
mo (glej Pre se k V/ 2) pr i popo l ni in du kci ji pr edp ost av imo š e ,
da f or mu l a ve l j a pri š t ev il u 8 in od t od dok aže mo ve l j av nos t
for mu l e za 8+1 . Ogle j mo s i do kaz pri prvi f ormul i . I z zve ze
med r 3(38 +3} i n r2 ( 38+3- 3i } dobi mo na jp r ej
r 2( 38 +3 } + r o( 38 } + r 2( 38 - 3} + . ..
+ r2( 3 } + r2 ( O}
ka r pomeni : r 3(3 8+3} ~ r2 (38 +3 } + r 3 (38 } . Upošteva jmo form u-
l o za r 2 ( 38+3} i n f or mulo za r 3( 38 } , ki po pr edp ostavki vg
1j a
r 3( 38+3} ( 38+4+0( 2 , 38+3 }}/ 2 +
+ (38 2+68 +3+0 ( 2 , 38 }}/ 4
Ke r j e natan ko e no od š t ev i l 38 i n 38+3 del jiv o z 2, j e
O( 2 , 38+3) + O( 2 , 38} ~ 1 , od t od pa s l ed i zve za 20 ( 2 ,38 +3 } +
+ O(2, 38 } ~ 1 + O( 2 , 38+3 } . č e to zve zo upoš t e vamo zgor a j in
i zraz mal o ur edimo , d obi mo
r 3( 38 +3} ~ (3 (8 +1 }2+6(8 +1}+3+0 (2 , 38+3 ) }/ 4
ka r j e r avno prv a od zg ornji h t reh f ormul pr i 8+1 . Na podo-
be n nač in d oka že mo t udi dr ug i dve f or muli .
For mul o za r 3 (n } tako do kaž emo za n ~3 , 4 , . . . , ka j hi t r o pa
se lah ko prepr i čamo , da ve l ja tud i za n ~ 0 , 1 i n 2 . Oa pa s e
ta f or mul a pi sa t i v kr ajši obl i ki, č e vpe l j e mo še e n s imbo l .
Na j pr e j l ah ko piš emo r 3(n} ~ ((n+ 3 } 2+p } / 12 , kj er j e p ~
: 30 (2 , n }+40( 3, n} -4 . če s i ogl eda mo vse tri s ituac ije , ko j e
š te v i l o n de l j i vo a li ne z 2 a li s 3, dobi mo za p nas lednje
gt ir i mo žn osti p~3 , p~ O , p ~ - l a l i p ~ - 4 . Ker pa mor a bi t i š tg
16
vil o (n+3 ) 2+p deljiv o z 12 , lah ko r e č e m o , da je treba k šte-
vilu (n+3) 2 pois kati najbli žji več kratnik štev ila 12 (p r t š t e
jemo O ali 3, a l i od š tejemo 1 ali 4) . O zn ač im o z {S }1 2 k št ~
v ilu s na jb ližji ve č kratni k št evi l a 12, pot em zgo r nj o f ormulo
la hko pi šemo v ob liki
Ker je vedno p F 6 , je š t evi lo {s} 12 ved no e noličn o določe­
no. Za zgl ed izra čunajmo P3(8 ) = {11 2 }1 2/12 = 120/1 2 = 10 .
Na prav podobe n na č in bi iz pe lj a l i fo r mu lo pri večjem k . Za
P4(n) bi najprej dobili zvez o
kj er doda j amo č le n e tako dolgo, dokle r so i zra zi v okle paj ih
še nenegativni . Naj brez do kaza zapi šemo ko nč n o fo rmulo , ki jo
dobimo iz zgo rnje in prejšnjih zvez
P4( n) = (n 3+15 n 2+63n+49+9( n+3)D ( 2, n) +32D(3, n) +
+16D(3, n)+ 36D(4 , n))/144
še mnogo da lj še so formu le z a p s (n ) , P6(n) itd .
Povrnimo se sedaj k številu razde litev n enakih predmetov na k
nep raznih k u p č k o v . Označimo š t e v i l o teh razdelitev z Pk(n ) .
Ker sedaj nobede n od k k u p č k o v ne sme biti prazen, damo naj-
pre j na vsa kega po en predmet, preo stalih n- k pa ra zdelimo
na k v e č j em u k k u p čk o v . Tako dobi mo zvez o
k =1 ,2 , 3, ... n ~ k
V posebn ih pr imerih tor ej imam o f ormule
pi (n )
pž (n )
r3 ( n )
1
p2( n- 2)
P3 (>; - 3 )
(n - 1+D(2 ,n j ) / 2
{n2 h 2 / 12
Upoš t eva l i smo zve zo D(2, n - 2) = D(2, n) . Za p omara n če Dedka
Mra za na primer dob imo : p ~(10 ) = {10 2}12/1 2 = 9611 2 = 8 .
17