ISSN 0351-6652 Letnik 24 (1996/1997) Številka 6 Strani 346-351
Ivan Lisac:
O RAČUNOVODSKEM PRAVILU
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/24/1320-Lisac.pdf
© 1997 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
O RAČUNOVODSKEM PRAVILU
Dostikrat se znajdemo pred nalogo, kako sešteti podano končno vsoto. Vzemimo najprej naslednji vsoti in ju sestejmo brez dokazovanja:
1+2+... + „ = !*!+M,	(i)
i' + 2» + ... + n^"fr + 1>J2" + 1>. (2)
6
To sta znani formuli za vsoto prvih n naravnih števil in kvadratov prvih n naravnih Števil (glej tudi sestavek Vsota potenc naravnih števil v 1. Številki Preseka).
Vzemimo kak težji primer. Kolikšna je na primer vrednost, vsote
C)+<;')+-+»(;:)? »
Na prvi pogled je najbrž ne znamo preprosto ugnati. Včasih si pri podobnih nalogah pomagamo s primerno interpretacijo členov v dani vsoti. Poskusimo to storiti z vsoto (3).
Binomski simbol (£) je število i-elenientnih podmnožic množice z n elementi. V vsoti (3) nastopa ob binomskern simbolu število k. Kakšen pomen pa ima tu k? In produkt &(")? Premislimo. Gre za neki odnos med elementi in podmnožicami. Ker je vseh fc-elementnih podmnožic (£), nam produkt fc(^) pove, kolikokrat je resnična izjava 'element a pripada množici X ko preteče a osnovno množico z močjo n, X pa vse podmnožice z močjo k.
Vidimo torej, da gre tu za odnos 'pripada' (g) , Preden seštejemo vsoto (3), pa razmislek posplošimo.
Računovodsko pravi/o. Naj bosta A, B končni množici in R C AxB poljubna podmnožica kartezičnega produkta A x B. Podmnožici R pravimo tudi reliLcijn.
Če je R(a) = {6 e B \ a H b) in /i"l(f>) = {a e A | a R 6} in označujejo jijj, |/i(a)|, |R_1(6)| moči množic R, R(a) in R(b), potem je
oe/1	b£B
Kot običajno smo z znakom 4 [/č(a)| označili vsoto števil |R(a)|, ko a preteče množico A, in podobno v ostalih primerih.
Zgornjo trditev najlažje ilustriramo ob sliki 1. Zapišimo elemente množice A v skrajni levi stolpec, elemente množice B pa v zgornjo vrstico. Ce sta elementa o in b v relaciji R (a R b), zapišimo na križišče ustrezne vrstice in stolpca enico, sicer postavimo tja ničlo. Potem so tri števila iz enakosti (4) zaporedoma: skupno število enic, vsota enic, šteta po vrsticah, in vsota enic, šteta po stolpcih (2+1 + 1 + 2 = 2 + 3+1 =6). Ta tri števila so enaka, zato enakost (4) velja.
	h	¿2	b3	¿4	£
11	0	0	I	1	2
as	i	1	0	1	3
«3	i	0	0	0	1
£	2	1	1	2	C
Slika 1. fl(ai) = {a3,f»d},fi(ai) = h, b4}, Rfa) = {¡>i}.
Vrnimo se sedaj k uvodnemu problemu. Definirajmo množici A in B ter relacijo R takole:
A = {1, 2,..., n> B = V{A) =r A" C A} a R b <=> a € b.
Za tako definirane A, B in R bomo uporabili računovodsko pravilo.
Vzemimo a £ i in izračunajnio |/i(a)|! V množici R(a) so tiste množice iz B, ki vsebujejo element a. Koliko jih je? Ker so vse oblike X U {a}, kjer je X C A\{a} (zakaj?), jih je toliko kot podmnožic množice j4\{a}, teh pa je	Nato še za b £ B izračunajmo [R~1(b}|. Množica
b premore |6| elementov, zato je |Jt-1(A)| = |6|. Iz računovodskega pravila (4) sledi:
oEA	biB
Levo vsoto sestavlja n členov enakih 2"_1, v desni združimo člene glede na moč množice 6 in dobimo:
s*©-
n2r'
Vsoto (3) srno torej sešteli.
Osnovna ideja računovodskega pravila je, da preštejemo moč relacije R na dva načina, S primerno izbiro množic A, B in R lahko dobimo zanimive enakosti. Poiščimojih še nekaj.
•	Naj bo A = B = {1,2,.. „,ij} in a Rb a < b. Potem je med 1 in n takih števil, ki so manjša ali enaka a, ravno a; števil večjih od b, pa je n — b 4- 1. To vstavimo v (4) in dobimo
n	n
£«=£(„-6+1). fl—1 6=1
Ker tečeta a iri b v obeh vsotah po istih številih, lahko v drugi vsoti namesto b pišemo a, ga prenesemo na levo in izračunamo novo desno vsoto:
M	n
Ce enačbo (5) še delimo z 2, dobimo vsoto (1).
•	Naj bo tokrat
A = {1,2,.. .,rc} B =A x A a R (bl,b2) <=> a < in a < b2.
Elementi množice B so v tern primera pari števil. Parov (61,62), pri katerih sta obe komponenti večji ali enaki a, je (n — a + l)2 (zakaj?). Ce pa je dan par (i>i, 62)1 taka števila a, da velja a < b\ in a < 62, kar naštejmo: to so 1,2,če je b\ < b2i in 1,2,..62, če je b2 < 61.
V	splošnem jih je torej min(6i,62), kjer min(&j,&2) označuje manjše od števil 61 in 62. Sedaj dobimo iz (4):
n	n n
5>-o + l)2= £ £>in(*i,k).	(6)
a=l	6! = 1&3 = 1
Leva vsota v (6) je pravzaprav vsota kvadratov prvih n naravnih števil, torej leva stran enakosti (2). Poglejmo Še desno vsoto. Razstavimo jo takole:
Ti ti
J2 mineta) = £ 61+ £ £ ti-	(7)
(>i=l	61 <63	fca<i>i	61=63
V	(7) sta na desni strani prvi dve vsoti enaki, zato izračunajmo le eno:
Ž Ž = (8)
V	(8) seštevamo le še prvih n naravnih števil in kvadrate prvih n naravnih števil, zato iz (6), (7) in (8) sledi
3X>? = <2»+1)X>.	(9}
61=1 t>i=l
(z (9) in (1) pa z deljenjem s 3 sledi enakost (2).
• Za naravno število n označimo z D(n) množico vseh deiiteljev števila n. Definirajmo:
A = D(n) B = {l,2,...,n} aRb-^a\b.
Poglejmo, kaj dobimo v tem primeru. Naj bo a delitelj števila n. Vsa z a deljiva števila, ki ležijo med 1 in n, so:
TI
a, 2a, 3a,..., —a.	(10)
a
V	(10) je natančno ^ števil. Naj bo sedaj b število iz množice B, Koliko je deiiteljev števila n, ki delijo število 6? Deliteiji števila n, ki delijo tudi število 6, so skupni detitelji obeh števil. Vse skupne delitelje števil b in ?i borno dobili, če bomo opazovali delitelje največjega skupnega delitelja obeh števil, torej množico D(d(b,«)). Tu d(b, n) označuje največji skupni delitelj števil b in n. Uvedimo še dve oznaki: če je n naravno število, naj bo r(n) število njegovih deiiteljev, cr(n) pa vsota vseh deiiteljev števila n. Primer:
r(6) - |{1,2,3,6)|= 4, tr(6) = 1 + 2 + 3 + 6 = 12,
Sedaj lahko odgovorimo na gornje vprašanje. Deiiteljev Števila n, ki delijo tudi Število 6, je r(d(b, n)). Uporabimo (4):
n
E ^ =	(n)
a|n	6=1
Ker pa je
a|n	ajn
(deliteiji so v (12) samo našteti v obratnem vrstnem redu), dobimo iz (11) in (12)
6=1
Preskusimo enačbo za n = 6:
r(l) + r(2) + r(3) + r(2) + T{l) + r(6) =1 + 2 + 2 + 2+1+4 = 12 = cr(G). • Vzemimo sedaj
A= (1,2,...,«} B = A x A a R (bi, b2) <=> a = Ms-
Naj bo a £ A. Koliko takih parov (61,62) obstaja, da je a = 6162? Opazimo, da je par (61,62) določen že z izbiro delitelja 61, saj jc 62 = = Vseh parov je torej toliko, kot je deliteljev števila a, teh pa je r(a). Poglejmo še obratno. Za vsak par (61, bo) £ B obstaja le eno tako število a, da je a = ¿162, to je 6162. Toda produkt 6162 mora ležati v A, če naj bo 6162 R (61, 62) ■ Zato je
1 R-HihMm^l1' ^J1?2^'.
! Uit ¿111 | ge Je ^^ > n
Vstavimo zadnja dva rezultata v (-4). Dobimo:
±T(«)=it\i S^JiŠ"- (13)
,	1 , , l0' ce je 6162 > t)	v '
Ce v (13) fiksiramo 6j, potem zadoščajo neenačbi 62 < naslednja števila iz množice A:
1,2,...,	(14)
kjer smo z [xj označili največje celo število, ki je manjše ali enako številu x. Iz (14) sledi
I 1
n n / ,	, ^ r.	ni 61 J	n
EE Si Jl = EEi-El^ tw
Iz (13) in (15) dobimo
X>H = ŽlfJ	(16)
fl — 1 6t=l 1
To pot vsote nismo znali sešteti, smo jo pa preoblikovali. Navedimo še računski primer, zopet za n = 6. Leva stran v (16) postane:
r( 1) H- r( 2) -h r( 3) + r( 4) + r( 5) + r(6) = 1 + 2 + 2 + 3 + 2 + 4= 14,
desna stran pa
Lxj + L|j + I|j + Ljj + I^j + Ljj = « + 3 + 2 +1 + 1 +1 = 14.
Ker je za velike n računanje izraza r(n) zamudno, je vsoto (16) lažje računati po desni strani.
Ivan Lisac