     
P 47 (2019/2020) 34
Računovodsko pravilo 2
I L
Pred leti smo v Preseku [1] pisali o računovod-
skem pravilu, s katerim smo ugnali nekaj končnih
vsot. Obudimo tokrat pravilo v nekaj novih prime-
rih.
Računovodsko pravilo
Naj bosta A in B končni množici ter R poljubna pod-
množica kartezičnega produkta A × B. Podmnožici
R pravimo tudi relacija. Da sta elementa a ∈ A ter
b ∈ B v relaciji R zapišemo (a, b) ∈ R ali krajše aRb.
Za dani a ∈ A lahko zberemo vse b ∈ B, ki so v rela-
ciji R z a v množico
R(a) = {b ∈ B : aRb}.
Obratno lahko definiramo za dani b množico
R−1(b) = {a ∈ A : aRb}.
Moč končne množice X bomo označili z |X|. Potem
računovodsko pravilo pravi:
|R| =
∑
a∈A
|R(a)| =
∑
b∈B
|R−1(b)|. (1)
Z znakom
∑
a∈A |R(a)| smo označili vsoto števil
|R(a)|, ko a preteče množico A, podobno pojasnimo
znak
∑
v ostalih primerih. Zgornjo trditev (1) si naj-
lažje predočimo ob spodnji tabeli za poseben primer
relacije R ⊆ {a1, a2, a3} × {b1, b2, b3, b4}:
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
∑
2 1 1 2 6
a3 1 0 0 0 1
a2 1 1 0 1 3
a1 0 0 1 1 2
b1 b2 b3 b4
∑
Zapišimo elemente množice A v skrajni levi stol-
pec, elemente množice B pa v zgornjo vrstico. Če je
aRb, zapišimo na križišče ustrezne vrstice in stolpca
enico, sicer postavimo tja ničlo. Potem so tri šte-
vila iz enakosti (1) 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 (1) velja. Sedaj si oglejmo ne-
kaj primerov, kjer bomo izbirali množici A in B ter
relacijo R, in tako našli ali vsaj preoblikovali nekaj
končnih vsot.
Relacija ’deli’ (|)
Označimo množico prvihn naravnih števil z znakom
Nn = {1,2, . . . , n}. Vzemimo A = B = Nn in aRb⇔
a|b. Uvedimo še funkcijo celi del:
⌊x⌋ =max({n ∈ Z : n ≤ x}).
Potem je
|R(a)| = ⌊n
a
⌋,
saj a deli števila
a,2a, . . . , ⌊n
a
⌋a,
množica R−1(b) pa vsebuje delitelje števila b, tako
da dobimo
n∑
a=1
⌊n
a
⌋ =
n∑
b=1
τ(b). (2)
Tu je τ funkcija, ki šteje delitelje argumenta. Za npr.
n = 4 je leva stran
⌊4
1
⌋ + ⌊4
2
⌋ + ⌊4
3
⌋ + ⌊4
4
⌋ = 4+ 2+ 1+ 1 = 8,
desna pa
τ(1)+ τ(2)+ τ(3)+ τ(4) = 1+ 2+ 2+ 3 = 8.
     
P 47 (2019/2020) 3 5
Praštevilski kvocient
Vzemimo A = B = Nn in zahtevajmo za relacijo R še
to, da je kvocient b/a praštevilo: aRb⇔ a|b∧b/a ∈
P. Potem je za dani a
|{b ∈ B : pa = b,p ∈ P}| = |{p ∈ P : p ≤ ⌊n
a
⌋}|.
Moč množice R−1(b) pa je
|R−1(b)| = |{p ∈ P : p|b}| =ω(b),
kjer smo zω(b) označili število praštevilskih delite-
ljev števila b. Uvedimo še funkcijo π , ki šteje prašte-
vila do danega argumenta takole:
π(x) = |{p ∈ P : p ≤ x}|,
pa že dobimo naslednjo enakost:
n∑
a=1
π(⌊n
a
⌋) =
n∑
b=1
ω(b). (3)
Primer.
π
(
⌊4
1
⌋
)
+π
(
⌊4
2
⌋
)
+π
(
⌊4
3
⌋
)
+π
(
⌊4
4
⌋
)
=
= 2+ 1+ 0+ 0 = 3
in
ω(1)+ω(2)+ω(3)+ω(4) = 0+ 1+ 1+ 1 = 3.
Koreni
Vzemimo A = B = Nn in aRb ⇔ a2 ≤ b. Potem so
v R(a) števila
a2, a2 + 1, . . . , n,
ki jih je natanko (n − a2 + 1), če je le a2 ≤ n, ter 0
sicer. V množici R−1(b) pa so števila
1,2, . . . , ⌊
√
b⌋.
Prvo vsoto zapišimo samo do tistega največjega m,
pri katerem je n + 1 −m2 ≥ 0, tj. m = ⌊
√
n+ 1⌋,
potem je
m∑
a=1
(n+ 1− a2) =
n∑
b=1
⌊
√
b⌋ =
=m(n+ 1)−m(m+ 1)(2m+ 1)/6. (4)
Pri tem smo uporabili znano formulo za vsoto prvih
m kvadratov
12 + 22 + · · · +m2 =m(m+ 1)(2m+ 1)/6.
Za npr. n = 10 imamo m = 3 in
10∑
b=1
⌊
√
b⌋ = 3 · 11− 3 · 4 · 7/6 = 33− 14 = 19.
Negibne točke
Vzemimo A = Nn in B = AA množico preslikav f
iz množice A vase. Negibna točka a ∈ A funkcije
f zadošča enakosti f(a) = a. Postavimo aRf ⇔
f(a) = a in preštejmo negibne točke teh preslikav.
Najprej je
|R(a)| = |{f ∈ B : f(a) = a}| = nn−1,
saj preslikavi f predpišemo negibno točko a, iz osta-
lih n− 1 vrednosti izberemo poljubno iz množice A.
Množica R−1(f ) pa je množica negibnih točk presli-
kave f . Sledi
∑
a∈A
nn−1 = nn =
∑
f∈B
|R−1(f )|, (5)
kar pomeni, da ima naključno izbrana preslikava v
povprečju eno samo negibno točko. Podoben pre-
mislek lahko naredimo za množico bijektivnih pre-
slikav množice A vase in dobimo enak rezultat: na-
ključno izbrana permutacija ima v povprečju eno
samo negibno točko.
Potence dvojke
Vzemimo A = Nn in potenčno množico B = P(A).
Postavimo še aRB ⇔ a = min(B) za B 6= ∅. Potem
je leva stran
∑
a∈A
|R(a)| =
n∑
a=1
2n−a =
n−1∑
a=0
2a,
saj dobimo množice B z minimumom a tako, da iz-
beremo ali opustimo elemente iz množice {a+1, a+
2, . . . , n} moči (n−a), kar da skupaj 2n−a možnosti.
Desna stran pa je
∑
B∈B
|R−1(B)| =
∑
B∈B\{∅}
1 = 2n − 1, (6)
     
P 47 (2019/2020) 36
saj ima neprazna množica B natanko en minimum.
To je še en način seštevanja geometrijske vrste s ko-
eficientom 2.
Dvojke ponovno
Vzemimo A = {(m,M) : 1 ≤ m < M ≤ n} in po-
tenčno množico B = P(Nn). Postavimo tokrat
(m,M)RB⇔m = min(B)∧M = max(B).
Potem je |R((m,M))| = 2M−m−1, saj so za dana mini-
mumm in maksimumM v množici B prosti elementi
za izbiro le še tisti vmes (M−m−1 jih je). Kom inM
tečeta po množici A, zavzame izrazM−m vrednosti
od 1 do n−1. Vrednost 1 zavzame (n−1)-krat, vre-
dnost 2 zavzame (n−2)-krat, . . . in vrednost (n−1)
enkrat tako, da velja
∑
(m,M)∈A
2M−m−1 =
n−1∑
v=1
(n− v)2v−1.
Po drugi strani pa za vsako množico B z vsaj dvema
elementoma dobimo natanko en tak par (m,M) ∈ A,
da je m = min(B) in M = max(B), zato je
n−1∑
v=1
(n− v)2v−1 =
∑
B∈B′
1 = 2n −n− 1. (7)
V enakosti (7) smo se v drugi vsoti izognili enkrat
prazni množici in n-krat enoelementnim množicam.
Za npr. n = 6 dobimo
5 · 20 + 4 · 21 + 3 · 22 + 2 · 23 + 1 · 24 =
= 5+ 8+ 12+ 16+ 16 = 57 = 26 − 6− 1.
Ciklične grupe
Oglejmo si še najbolj zahteven primer v tem članku.
Definirajmo množico Zn ostankov pri deljenju z n.
Operacija na njej sešteva ostanke po modulu n in
iz nje napravi grupo. Vzemimo za primer grupo
Z12 = {1,2, . . . ,12}. Podobna je vsakdanjemu gleda-
nju na uro, kjer lahko seštevamo ure preko poldneva,
npr. 10+ 4 = 2(+12). Ostanek 12 je tu nevtralni ele-
ment. Vsakega od ostankov lahko dobimo že zgolj
s seštevanjem samih enic. Učeno pravimo, da osta-
nek 1 generira grupo Z12. Ni pa edini: družbo mu de-
lajo še taki ostankim, da številam,m+m,m+m+
m, . . . ,12m zasedejo vseh 12 ostankov, za kar za-
došča, da za nek naravni k ostanek km zasede tudi
enico oz. velja km ≡ 1( mod 12) oz. je m tuj mo-
dulu 12. Generatorji Z12 so tako še ostanki 5, 7 in
11.
Grupe, ki jih generira že en sam generator, so ci-
klične. Podmnožicam grupe, ki so zaprte za dano
operacijo (in njen inverz), pravimo podgrupe. Na-
štejmo vse podgrupe grupe Z12:
{1,2,3,4,5,6,7,8,9,10,11,12},
{2,4,6,8,10,12}, {3,6,9,12},
{4,8,12}, {6,12}, {12}.
Tu smo generatorje podgrup podčrtali. Iz teorije
grup si sedaj brez dokaza izposodimo tele trditve:
Podgrupe ciklične grupe so ciklične.
Za vsak delitelj d števila n obstaja natanko ena
podgrupa moči n/d z generatorjem d.
Vseh podgrup Zn je kot deliteljev števila n, tj.
τ(n).
Zn ima φ(n) generatorjev: to so ostanki, ki so tuji
n.
Tu je φ(n) Eulerjeva funkcija, ki vrača število proti
n tujih števil iz Zn. Sedaj vzemimo A = Zn in B =
{b ∈ Zn : b|n} ter aRb, če a in b generirata isto pod-
grupo. Potem je |R(a)| = 1, saj obstaja natanko en
tak generator b ∈ B, da je podgrupa generirana z a
enaka podgrupi generirani z b. Obratno pa dani b
generira ciklično podgrupo moči n/b, ki imaφ(n/b)
generatorjev. Zato dobimo
∑
a∈A
1 = n =
∑
b|n
φ(n/b) =
∑
b|n
φ(b). (8)
V enakosti (8) smo pri tretjem enačaju elemente n/b
samo našteli v obratnem vrstnem redu. Še primer:
za n = 12 imamo
φ(1)+φ(2)+φ(3)+φ(4)+φ(6)+φ(12) =
= 1+ 1+ 2+ 2+ 2+ 4 = 12.
Literatura
[1] I. Lisac, O računovodskem pravilu, Presek 24
(1997), 6, 346–351.
×××