i
i
“1601-Mlakar-ZBarvanjem” — 2010/8/31 — 11:15 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 32 (2004/2005)
Številka 5
Strani 10–11
Matej Mlakar:
Z BARVANJEM HIŠK DO FORMUL ZA VSOTO POTENC
Ključne besede: matematika, teorija števil, Pascalov trikotnik, binomski simboli, števila barvanja
hišk.
Elektronska verzija: http://www.presek.si/32/1601-Mlakar.pdf
c© 2005 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 po-
prejšnjega dovoljenja založnika ni dovoljeno.
10
Z barvanjem 
hišk do formul 
za vsoto potenc
MATEMATIKA
V zgodovini matematike so bile formule 
     
  
 1+2+3+···+n =
 
n2
2 +
n
2
 12+22+32+···+n2 =
 
n3
3 +
n2
2 +
n
6
 13+23+33+···+n3 =
 
n4
4 +
n3
2 +
n2
4
sprva namenjene izračunu ploščin ter prostornin, 
kasneje pa so jih uporabljali za razvoj pravil za 
integracijo polinomov. 
Dokazovanje formul za vsote oblike 1d+2d+···+ nd,
kjer je d naravno število, ponavadi temelji na in-
dukciji, vendar si s to metodo ne moramo pomaga-
ti pri iskanju pravila, ki ga dejansko potrebujemo. 
Ena izmed metod za iskanje teh formul izhaja iz 
Kitajske ter Indije. Poznali so jo že arabski mate-
matiki v Bagdadu in Kairu med leti 1200 in 1400. 
Temeljila je na lastnostih binomskih koeficientov v 
Pascalovem trikotniku. 
      
 
 
                                                  1
                                            1            1                                   
                                    1            2            1                              
                              1           3            3           1           
                        1          4            6            4          1       
                  1          5          10          10          5          1
            1          6         15          20          15         6          1
      1          7         21         35          35         21         7          1 
1          8         28        56          70          56        28         8          1
Če zapišemo Pascalov trikotnik, opazimo, da ve-
lja 1+5+15+35=56. To daje slutiti na 
       
d
d +
d+1
d +
d+2
d +·· ·+
n
d =
n+1
d+1 .
 
(1)
Ker binomski simbol nd  pomeni tudi število pod-
množic z d elementi v množici z n elementi, lahko 
definiramo nd =0 za d>n. Tako lahko 
vsoto (1) zapišemo tudi kot 
      
  
∑
n
x=1
x
d =
n+1
d+1 ,
 
(2)
kar lahko zlahka dokažemo z indukci-
jo po n. Vsak binomski koeficient xd  je 
polinom spremenljivke x stopnje d, re-
cimo 
      
 
x
 1 =x ,
x
 2 =
x(x–1)
2
x2
2=
x
2– ,
x
 3 =
x(x–1)(x–2)
6
x3
6=
x2
2–
x
3+ ,
x
 4 =
x(x–1)(x–2)(x–3)
24 =
x4
24=
x3
4–
11x2
24+
x
4– .
Izrazimo potence spremenljivke x s po-
močjo binomskih koeficientov. Tako je 
      
 
x
x2
x3
= x 1
x
 2=2 +
x
 1
x
 3=6 +
x
 1
x
 2+6 .
Če zgornje enakosti povežemo z (2), 
dobimo 
 
(3)      
 
∑
n
x=1
= n+12x ∑
n
x=1
x
 1 =
∑
n
x=1
=x2 ∑
n
x=1
x
 2 +2
x
 1 = ∑
n
x=1
x
 2 +
x
 12 ∑
n
x=1
= n+132
n+1
2+
      
 
∑
n
x=1
=x3 ∑
n
x=1
x
 3 +6
x
 1
x
 26 +
∑
n
x=1
x
 36 ∑
n
x=1
x
 26+
x
 1∑
n
x=1
+
= n+146
n+1
2+
=
n+1
36 +
=
=
Obstoj formule za 
       
 
∑
n
x=1
xd
sledi iz dejstva, da so x0 , x1 ,..., xd  po-
linomi različne stopnje, zato tvorijo 
bazo prostora polinomov stopnje ≤d. 
Kaže, da se splošni rezultat izraža z 
binomskimi simboli v obliki 
      
 
∑
n
x=1
xd = ad,d
n+1
d+1 +ad,d –1
n+1
d +···
ad,1
n+1
2+ . (6)
Poskusimo dokazati splošni rezultat. 
Povezavo med koeficienti ad,j , kjer sta 
d,j! , poiščimo s pomočjo kombina-
toričnega razmisleka v navidez popol-
noma drugačnih nalogah. 
(4)
(5)
1 Posamezna hiška se pobarva 
le z eno barvo
2 Števila H(d,j ) so bolj znana 
kot števila barvanja hiške, 
angl. »house-painting 
numbers«
.
Presek 5-revija-9.indd   10 4/11/2005   13:24:31
Process Cyan Process Magenta Process Yellow Process Black PANTONE Process Magenta CVC PANTONE 130 CVC PANTONE 312 CVC
11
MATEMATIKA
 Prvi problem barvanja hišk. 
 Na koliko načinov lahko pobarvamo 
d hišk z natanko j barvami1 ? 
Označimo s H(d,j ), kjer sta d in j na-
ravni števili, število barvanj d hišk z na-
tanko j barvami.2 Očitno je H(d,j )=0, 
če je j>d. V primeru, da imamo d hišk 
in eno barvo, pobarvamo vse hiške z 
enako barvo; torej je H(d,1)=1 za vsak 
d ! . Če imamo enako število hišk in 
in barv, gre dejansko za število vseh 
bijektivnih preslikav med dvema mno-
žicama. Vseh bijektivnih preslikav med 
končnima množicama z močjo d je d!, 
velja H(d,d )=d!. V splošnem imamo 
na voljo d hišk. Izberemo eno in jo po-
barvamo z eno od j barv. Ostane nam 
d –1 hišk. Izbrano barvo lahko uporabi-
mo naprej ali pa ne, kar lahko zapišemo 
z rekurzivno zvezo 
       H(d,j )=j(H(d–1,j)+H(d –1,j–1)).
Če nekaj vrednosti H(d,j ) zapišemo 
v tabeli, hitro ugotovimo, da so se že 
pojavile v razvoju vsote potenc xd za 
d!{1,2,3,4}. 
izberemo eno barvo izmed j barv, nakar 
pobarvamo d hišk z natanko eno barvo. 
Število načinov je  j1 ·H(d,1). Na podoben 
način ugotovimo število vse možnih barvanj 
z dvema barvama, ki ju izberemo izmed 
j barv. Teh je  j2 ·H(d,2). Tako pridemo do 
vseh možnosti, ki jih strnemo v 
       
j
d H(d,d )+
j
d–1 H(d,d–1)+
j
 1 H(d,1).
Na vsoto (7) pa lahko pogledamo tudi 
drugače. Označimo množico barv B=
{b1,b2,...,bj}. Na koliko načinov lahko iz 
znakov iz množice B sestavimo niz dolži-
ne d, kjer je ponavljanje znakov dovoljeno? 
Gre za število variacij s ponavljanjem j ele-
mentov reda d, vseh je torej jd. Zato je 
      
 
j
d H(d,d )+
j
d–1 H(d,d–1)+···
j
 1 H(d,1).
jd=
+
Ko uporabimo zgornjo enakost za izračun 
vsote in upoštevamo še (2), dobimo željeno 
zvezo 
     ∑
x=1
xd ∑
x=1
= H(d,d ) xd ∑
x=1
+ H(d,d–1)
=H(d,d ) n+1d+1 +H(d,d–1)
n+1
 d +
+∑
n
x=1
H(d,1) x 1
+···+H(d,1) n+12
x
d–1 +···
n n n
\ Naloge
1. Na koliko načinov lahko pobarvamo 
šest hišk z natanko štirimi barvami? 
2. Na koliko načinov lahko pobarvamo 
šest hišk z največ štirimi barvami? 
3. Zapiši formulo za 15+25+···+n 5 s po-
močjo binomskih koeficientov.
\ Vir
1. Vsak koeficient H(d,j) izračunamo s pomočjo 
tabele. Če upoštevamo rekurzivno zvezo H(d,j)=
j(H(d–1,j)+H(d–1,j–1)), dobimo določeni koefi-
cient tako, da izračunamo vsoto koeficienta, ki je 
v istem stolpcu prejšnje vrstice, ter koeficienta, 
ki je v prejšnji vrstici levo od njega. Dobljeno vso-
to pomnožimo s številko stolpca. Tako je 
        H(6,4)=4(H(5,4)+H(5,3))=
 4(150+240)=1560.
Opomba. Slabost tega načina je, da moramo do-
polniti tabelo do vključno pete vrstice. To pa že 
kliče po zapisu računalniškega algoritma, ki bi 
generiral H(d,j). Oglejmo si primer funkcijskega 
podprograma v pascalu. 
         function H(d,j: integer): real;  
  begin  
    if (j>d) then H:=0  
    else begin  
      if (j=1) or (d=1) then H:=1  
      else  
        H:=j*(H(d–1,j)+H(d-1,j-1));  
    end;  
  end; 
2. Rezultat dobimo lahko na dva načina, saj velja 
       46=4
6H(6,6)+4
5H(6,5)+4
4H(6,4)+···
=0=0
+4
1H(6,1)=4096.
3. S pomočjo končnega rezultata pridemo do zveze 
       
 
∑
n
x=1
x5=∑
5
x=1
H(6,6)x
5+∑
n
x=1
H(5,4)x
4+···
+∑
n
x=1
H(5,1)x
 1
=H(5,5)n+1
6+H(5,4)n+1
5+···
+H(5,1)n+1
2.
Če bi zadnjo vrstico poenostavljali še naprej, bi 
dobili eksplicitno formulo 
       
 ∑
n
x=1
x5=n6
6
–3
2
n5+245
12
n4–30n3–241
12
n2+32n.
Z drugačnim razmislekom pokažimo 
pomen števil barvanja hišk H(d,j) in 
veljavnost v (6).
 Drugi problem barvanja hišk. 
 Na koliko načinov lahko pobarvamo 
d hišk, če želimo uporabiti največ j 
barv? 
Če imamo na voljo več barv, kot je hišk, 
lahko uporabimo največ d barv. Če po-
barvamo d hišk z natanko eno barvo, 
d \ j 1 2 3 4 5 6
1 1
2 1 2
3 1 6 6
4 1 14 36 24
\ Rešitve
 http://www.macalester.edu/˜bressoud/
talks/APNC2004/FTC.pdf 
Prevedel in priredil Matej Mlakar
(7)
Presek 5-revija-9.indd   11 4/11/2005   13:24:33
Process Cyan Process Magenta Process Yellow Process Black PANTONE Process Magenta CVC PANTONE 130 CVC PANTONE 312 CVC