Četrta lekcija: Razbitja množic in razčlenitve števil

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Četrta lekcija: Razbitja množic in razčlenitve števil

Avtor: Primož Potočnik

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega sklada za regionalni razvoj in Ministrstva za visoko šolstvo, znanost in tehnologijo. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Društvo matematikov, fizikov in astronomov Slovenije ter DMFA-založništvo.

3 Razbitja množic in razčlenitve števil

V tem poglavju bomo preštevali razbitja dane $n$ -elementne množice na $k$ nepraznih podmnožic. Pojasnimo najprej natančno, kaj s tem mislimo.

Definicija 3.1
Razbitje množice $A$ je družina $\mathcal{R}=\{A_1,...,A_k\}$ nepraznih, paroma disjunktnih podmnožic množice $A$ , katerih unija je enaka množici $A$ . Množicam $A_i$ rečemo tudi deli razbitja.

Na primer, če je $A =\{a,b,c,d\}$ , je $\mathcal{R} =\{\{a\},\{b,c,d\}\}$ razbitje množice $A$ na $2$ neprazni množici. Poleg razbitja $\mathcal{R}$ , množica $A$ premore še šest drugih razbitij na $2$ neprazni množici. Najprej še tri, kjer je eden od delov moči $1$ (in drugi moči $3$ ), nato paše tri takšna, kjer je sta oba dela razbitja moči $2$ .
Poleg običajnih razbitij množice, pa bomo obravnavali tudi tako imenovana urejena razbitja, kjer elemente vsakega dela razbitja uredimo. Kaj natanko s tem mislimo, bomo pojasnili v nadaljevanju.

3.1 Stirlingova števila druge vrste

Številu vseh razbitij $n$ -elementne množice $A$ na $k$ nepraznih podmnožic rečemo Stirlingovo število druge vrste in ga označimo z $S(n,k)$ . Množico teh razbitij označimo z $S(A,k)$ . Očitno velja naslednje:

$S(n,k) = 0$ za $k > n$ , $S(n,n) = 1$ in $S(n,1) = 1.$ (*)

Dodatno definiramo še $S(n,0) = 0$ za vsak $n \ge 1$ in $S(0,0) = 1.$
Ostala števila $S(n,k)$ pa najenostavneje računamo s pomočjo naslednje rekurzivne formule.

Trditev 3.2
Za vsak par $n,k \in \mathbb{N}, 1 \le k \le n$ , velja

$S(n,k) = S(n-1,k-1) + kS(n-1,k).$

Dokaz

Naj bo $\mathcal{N} =\{x_1,...,x_n\}$ poljubna $n$ -elementna množica, $\mathcal{R}$ množica vseh razbitij množice $\mathcal{N}$ na $k$ nepraznih podmnožic, $\mathcal{R}_0$ množica tistih razbitij iz $\mathcal{R}$ , v katerih nastopa podmnožica $\{x_n\}$ in $\mathcal{R}_1 = \mathcal{R}\setminus \mathcal{R}_0$ .
Vzemimo poljubno razbitje $R = \{A_1,...,A_k\} \in \mathcal{R}$ . Mislimo si, da element $x_n$ iz množice $\mathcal{N}$ izrežemo. Tedaj razbitje $R$ preide v razbitje $R' = \{A_1\setminus\{x_n\},...,A_k\setminus\{x_n\}\}$ množice $\mathcal{N}\setminus\{x_n\}$ .
Če razbitje $R$ sodi v skupino $\mathcal{R}_0$ , tedaj je ena od množic razbitja $R'$ prazna in mislimo si lahko, da jo iz $R'$ odstanimo. Tako dobimo razbitje $(n-1)$ -elementne množice $\mathcal{N}\setminus\{x_n\}$ na $k-1$ nepraznih podmnožic. Obratno, vsako razbitje $T = {A'_1,...,A'_{k-1}}$ množice $\mathcal{N} \setminus\{x_n\}$ na $k -1$ nepraznih podmnožic lahko z vključitvijo množice $\{x_n\}$ dopolnimo do razbitja $R = \{{x_n},A'_1...,A'_{k-1}\}$ množice $\mathcal{N}$ . Ni težko videti, da je $R$ edino razbitje iz $\mathcal{R}_0$ , za katero je $R' = T$ . S tem smo dokazali, da je preslikava $R \mapsto R'$ bijekcija med množicama $\mathcal{R}_0$ in množico $S(\mathcal{N} \setminus\{x_n\},k -1)$ nepraznih podmnožic. Po načelu enakosti sledi $|\mathcal{R}_0| = S(n-1,k-1)$ .
Če pa razbitje $R$ sodi v skupino $\mathcal{R}_1$ , tedaj nobena od množic razbitja $R'$ ni prazna, kar pomeni, da je $R'$ razbitje množice $\mathcal{N} \setminus \{x_n\}$ na $k$ nepraznih podmnožic. Če vzamemo poljubno razbitje $T = {A'_1,...,A'_k}$ množice $\mathcal{N} \setminus\{x_n\}$ na $k$ nepraznih podmnožic, lahko z vključitvijo elementa $\{x_n\}$ v katero koli od $k$ množic $A'_i$ dobimo razbitje $R$ iz skupine $R_1$ , za katerega je $R' = T$ . Tako dobljena razbitja $R$ so hkrati edina, za katera je $R' = T$ , kar pomeni, da je vseh razbitij iz skupine $R_1$ natanko $k$ -krat toliko, kot je razbitij $(n-1)$ -elementne množice $\mathcal{N} \setminus\{x_n\}$ na $k$ -nepraznih podmnožic, torej $kS(n-1,k)$ .
Trditev sedaj z lahkoto sledi, saj je $|\mathcal{R}| =|\mathcal{R}_0|+|\mathcal{R}_1| = S(n-1,k-1)+ kS(n-1,k)$ .

Rekurzivna formula nam omogoča, da Stirlingova števila 2. vrste računamo podobno kot binomske koeficiente. Sestavimo tabelo, v kateri na presečišču $n$ -te vrstice in $k$ -tega stolpca stoji število $S(n,k)$ :

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	3	1	0	0	0	0
4	0	1	7	6	1	0	0	0
5	0	1	15	25	10	1	0	0
6	0	1	31	90	65	15	1	0
7	0	1	63	301	350	140	21	1

Iz začetnih pogojev sledi, da so nad glavno diagonalo same ničle, po diagonali same enke, v prvem stolpcu pa, razen pri prvem elementu, zopet same ničle. Število $S(n,k)$ v tabeli dobimo tako, da seštejemo število, ki stoji diagonalno levo nad njim in $k$ -kratnik števila neposredno nad njim. Število $65$ , ki leži v vrstici $6$ in stolpcu $4$ , smo torej dobili tako, da smo sešteli $25$ (levo zgoraj) in $4 \cdot 10$ (smo v stolpcu $4$ , nad iskanim številom pa stoji $10$ ).

Stirlingova števila 2. vrste imajo zanimivo interpretacijo tudi pri problemih preštevanja funkcij med dvema končnima množicama.

Trditev 3.3
Naj bosta $N$ in $K$ poljubni končni množici moči $n$ in $k$ . Tedaj je število vseh surjektivnih preslikav iz množice $N$ v množico $K$ enako

$k!S(n,k).$

Dokaz

S pomočjo trditve 3.3, rekurzivne formule in načela vključitev in izključitev lahko dokažemo naslednjo zanimivo formulo.

Trditev 3.4
Za poljubni naravni števili $n$ , $k$ , $k \le n$ , velja

$S(n,k) = \frac{1}{k!} \sum^k_{i=1}{k \choose i}(-1)^{k-i}i^n.$

Dokaz

Naj bodo $b_1,...,b_k$ elementi množice $K$ in $f: N \to K$ poljubna surjektivna preslikava. Za vsak $i \in \{1,...,k\}$ definirajmo množico

$N_i = f^{-1}(b_i) = {x \in N :f(x) = b_i}.$

Tedaj družina $\{N_1,...,N_k\}$ tvori razbitje množice $N$ na $k$ nepraznih delov. Na ta način smo definirali preslikavo $\Phi$ iz množice vseh surjektivnih funkcij iz $N$ v $K$ ter množico $S(N,k)$ .
Pri tem opazimo, da za razbitje $\mathcal{R}=\{N_1,...,N_k\} \in S(N,k)$ in surjektivno preslikavo $f: N \to K$ velja $\Phi(f) = \mathcal{R}$ , če in samo če je $f$ definirana s predpisom

$f(x) = b_i \iff x \in N_{\pi(i)},$

za neko permutacijo $\pi$ množice indeksov $\{1,...,k\}$ . Od tod sledi, da se v vsako razbitje iz $S(N,k)$ preslika natanko $k!$ različnih surjektivnih preslikav iz $N$ v $K$ . Zato je takšnih surjektivnih preslikavo natanko $k!|S(N,k)| = k!S(n,k)$ .

Dokaz

Naj bosta $N$ in $K$ , $|N| = n$ , $|K| = k$ , poljubni množici in naj $A$ označuje množico vseh preslikav iz $N$ v $K$ , ki niso surjektivne. Ker je vseh preslikav iz $N$ v $K$ natanko $k^n$ , je moč množice $A$ enaka $k^n - k!S(n,k)$ .
Zdaj pa preštejmo elemente množice $A$ še na drug način. Naj bodo $b_1,...,b_k$ elementi množice $K$ in za vsak $i \in \{1,...,k\}$ naj $A_i$ predstavlja množico vseh tistih funkcij iz $N$ v $K$ , ki elementa $b_i$ nimajo v svoji sliki. Tedaj je množica $A$ očitno unija množic $A_i$ .
Vzemimo poljubno $i$ -elementno podmnožico $\mathcal{J} = \{b_{j_1},...,b_{j_i}\}$ množice $\{1,...,k\}$ . Tedaj presek $\cap_{j \in \mathcal{J}}A_j$ vsebuje natanko vse funkcije iz množice $N$ v množico $K \setminus \{b_{j_1},...,b_{j_i}\}$ in zato premore natanko $(k-i)^n$ elementov.
Vsota $S_i$ moči presekov $\cap_{j \in \mathcal{J}}A_j$ po vseh $i$ -elementnih podmnožicah $\mathcal{J}$ množice $\{1,...,k\}$ zato znaša

${k \choose i}(k-i)^n.$

Trditev sedaj sledi neposredno iz načela vključitev in izključitev.

3.2 Lahova števila

Lahovo število $L(n,k)$ je definirano kot število linearno urejenih razbitij $n$ -elementne množice na $k$ nepraznih podmnožic. Neformalno lahko linearno urejeno razbitje množice $A=\{a_1,...,a_n\}$ opišemo kot običajno razbitje, pri čemer vsako množico razbitja linearno uredimo. Dve razbitji na iste množice se pri tem razlikujeta, če se razlikujeta vrstna reda elementov v kateri od množic razbitja.
Razliko med običajnimi in linearno urejenimi razbitji si oglejmo na naslednjem primeru. Naj bo $A = \{a,b,c,d\}$ in poiščimo vsa (običajna) razbitja na množice $A$ na dve podmnožici. Le-ta so

$\{\{a,b\},\{c,d\}\}, \{\{a,c\},\{b,d\}\}, \{\{a,d\},\{b,c\}\},$ $\{\{a\},\{b,c,d\}\}, \{\{b\},\{a,c,d\}\}, \{\{c\},\{a,b,d\}\}, \{\{d\},\{a,b,c\}\}.$

Razbitje $\{\{a,b\},\{c,d\}\}$ porodi štiri različna linearno urejena razbitja:

$\{(a,b),(c,d)\}, \{(b,a),(c,d)\}, \{(a,b),(d,c)\}, \{(b,a),(d,c)\}.$

Podobno velja za ostala razbitja na dve enako močni množici. Po drugi strani pa razbitje $\{\{a\},\{b,c,d\}\}$ porodi $3!= 6$ različnih linearno urejenih razbitij – za vsako linearno ureditev elementov $\{b,c,d\}$ po eno. Zato je

$L(4,2) = 4 \cdot 3 + 6 \cdot 4 = 36.$

Za skrajne vrednosti Lahovih števil očitno velja naslednje:

$L(n,k) = 0$ za $k > n$ , $L(n,n) = 1$ in $L(n,1) =n!$ .

Dodatno definiramo še $L(n,0) = 0$ za vsak $n \ge 1$ in $L(0,0) = 1$ .
Podobno kot pri Stirlingovih številih 2. vrste lahko tudi za Lahova števila izpeljemo rekurzivno zvezo. Izpeljava se razlikuje zgolj v tem, da tu pri štetju razbitij iz skupine $\mathcal{R}_1$ iz danega razbitja $T = \{A'_1,...,A'_k\}$ množice $\mathcal{N} \setminus \{x_n\}$ lahko najdemo $n-1+k$ razbitij $R$ iz skupine $\mathcal{R}_1$ , za katera je $R' = T$ ; izbrisani element $x_n$ lahko namreč vrinemo v katero koli množico $A'_i$ na eno od $|A'_i|+1$ razpoložljivih mest (za vse elemente množice $A'_i$ ali pa pred kakega od $|A'_i|$ elementov množice $A$ ). Element $x_n$ lahko torej vrinemo v razbitje na $(|A_1|+1)+(|A_2|+1)+...+(|A_k|+1)$ načinov, kar znese $n-1+k$ . Od tod seldi naslednja trditev.

Trditev 3.5
Za $1 \le k \le n$ velja

$L(n,k) =L(n-1,k-1)+(n+k-1)L(n-1,k).$

Z indukcijo na število $n$ in z uporabo rekurzivne formule iz trditve 3.5 lahko izpeljemo tudi eksplicitno formulo, ki Lahova števila izrazi s pomočjo binomskih simbolov.

Trditev 3.6
Za $1 \le k \le n$ velja

$L(n,k) = {n-1 \choose k-1} \frac{n!}{k!} = {n \choose k} \frac{(n-1)!}{(k-1)!}.$

Podobno kot pri binomskih simbolih in Strilingovih številih 2. vrste, lahko tudi Lahova števila računamo s pomočjo sheme, ki izhaja iz rekurzivne zveze. V spodnji tabeli na presečišču $n$ -te vrstice in $k$ -tega stolpca stoji število $L(n,k)$ , ki ga dobimo tako, da seštejemo število, ki stoji diagonalno levo nad njim in $(n+k-1)$ -kratnik števila neposredno nad njim. Število $240$ , ki leži v vrstici $5$ in stolpcu $2$ , smo torej dobili tako, da smo sešteli $24$ (levo zgoraj) in $6 \cdot 36$ .

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	2	1	0	0	0	0	0
3	0	6	6	1	0	0	0	0
4	0	24	36	12	1	0	0	0
5	0	120	240	120	20	1	0	0
6	0	720	1800	1200	300	30	1	0
7	0	5040	15120	12600	4200	630	42	1

Poleg običajnih Lahovih števil se v literaturi pojavljajo tudi predznačena Lahova števila, definirana s formulo

$L'(n,k) = (-1)^{n}L(n,k).$

3.3 Stirlingova števila prve vrste

Stirlingovo število prve vrste $s(n,k)$ štejeje razbitja $n$ -elementne množice na $k$ nepraznih ciklično urejenih množic. Pri tem pojem “ciklično urejena množica” pomeni množico, denimo $A=\{a,b,c,d\}$ , skupaj s cikličnim vrstnim redom elementov, denimo

$[a,b,c,d] =[b,c,d,a] =[c,d,a,b] =[d,a,b,c].$

Hiter premislek pokaže, da lahko vsako $m$ -elementno množico ciklično uredimo na $(m-1)!$ načinov, saj si lahko ciklično ureditev predstavljamo kot linearno ureditev množice, pri čemer $m$ linearnih ureditev, ki se razlikujejo zgolj za ciklični pomik, štejemo kot isto ciklično ureditev. Ker je linearnih ureditev $m$ -elemente množice $m!$ , je zato cikličnih ureditev $\frac{m!}{m} = (m-1)!$ .
Stirligova števila za mejne pare števil $n$ in $k$ zadoščajo enakostim

$s(n,k) = 0$ za $k > n$ , $s(n,n) = 1$ in $s(n,1) =(n-1)!$ .

Dodatno definiramo še $s(n,0) = 0$ za vsak $n \ge 1$ in $s(0,0) = 1$ .
Na zelo podoben način kot pri Stirlingovih številih druge vrste in Lahovih številih, lahko tudi tu izpeljemo naslednjo rekurzivno formulo.

$s(n,k) = s(n-1,k-1)+(n-1)s(n-1,k).$

V tabeli Stirlingovih števil 1. vrste, v kateri na presečišču $n$ -te vrstice in $k$ -tega stolpca stoji število $s(n,k)$ ,ležijo nad glavno diagonalo same ničle, po diagonali same enke, v prvem stolpcu pa, razen prvega elementa, spet same ničle. V skladu z rekurzivno formulo izračunamo število $s(n,k)$ v tabeli tako, da seštejemo število, ki stoji levo zgoraj nad njim, in $(n-1)$ -kratnik števila, ki stoji neposredno nad njim. Na primer, na presečišču vrstice $5$ in stolpca $3$ dobimo vsoto števila $11$ (levo zgoraj) in števila $(5-1) \cdot 6 = 24$ , torej $35$ .

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	2	3	1	0	0	0	0
4	0	6	11	6	1	0	0	0
5	0	24	50	35	10	1	0	0
6	0	120	274	225	85	15	1	0
7	0	720	1764	1624	735	175	21	1

V literaturi srečamo tudi predznačena Stirlingova števila prve vrste, ki so definirana s formulo

$s'(n,k) = (-1)^{n-k}s(n,k).$

3.4 Število razčelnitev naravnega števila

Zaporedju (neničelnih) naravnih števil $m_1 \le m_2 \le ... \le m_k$ , katerih vsota je enaka $n$ , rečemo razčlenitev naravnegaštevila $n$ na $k$ členov. Število vseh takšnih razčlenitev označimo s $p_k(n)$ . Očitno je

$p_k(n) = 0$ za $k > n$ .

Dodatno definiramo $p_0(0) = 1$ in $p_0(n) = 0$ za $n > 0$ .

Trditev 3.7
Za vsak par naravnih števil $n$ , $k$ velja

$p_k(n) = p_{k-1}(n-1) + p_k(n-k).$

Dokaz

Združimo tiste razčlenitve $(m_1,...,m_k)$ , za katera je $m_1 = 1$ v množico $\mathcal{R}_0$ , tiste, za katera pa je $m_1 > 1$ , pa v množico $\mathcal{R}_1$ . Če razčlenitvi iz množice $\mathcal{R}_0$ odvzamemo prvi element $m_1 = 1$ , dobimo razčlenitev števila $n-1$ na $k -1$ sumandov. Obratno, če razčlenitvi števila $n-1$ na $k -1$ sumandov dodamo na začetek enico, dobimo razčlenitev iz $\mathcal{R}_0$ . Zato je $|R_0| = p_{k-1}(n-1)$ .
Razčlenitev $(m_1,...,m_k) \in \mathcal{R}_1$ lahko spremenimo v razčlenitev števila $n-k$ na $k$ sumandov, če vsak $m_i$ zmanjšamo za $1$ . Ker vsako razčlenitev števila $n - k$ na $k$ sumandov dobimo na takšen način natanko enkrat, je $|\mathcal{R}_1| = p_k(n - k)$ . Od tod dobimo $p_k(n) = |\mathcal{R}_0| + |\mathcal{R}_1| = p_{k-1}(n - 1) + p_k(n-k)$ .

Računanje števil $p_k(n)$ si olajšamo, če sestavimo tabelo, v kateri na presečišču $n$ -te vrstice in $k$ -tega stolpca stoji število $p_k(n)$ . Začetni pogoji in rekurzivna formula pravijo, da so nad glavno diagonalo same ničle, po diagonali same enke, v prvem stolpcu pa, razen prvega elementa, spet same ničle. Število $p_k(n)$ v tabeli dobimo tako, da seštejemo število, ki stoji levo zgoraj nad njim, in število, ki stoji $k$ vrstic nad iskanim številom. Na primer, na presečišču vrstice $7$ in stolpca $3$ dobimo vsoto števila $3$ (levo zgoraj) in števila $1$ (tri vrstice višje).

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	1	1	0	0	0	0
4	0	1	2	1	1	0	0	0
5	0	1	2	2	1	1	0	0
6	0	1	3	3	2	1	1	0
7	0	1	3	4	3	2	1	1

3.5 Prostori polinomov in Stirlingova ter Lahova števila

Za konec razdelka predstavimo presenetljivo interpretacijo Stirlingovih in Lahovih števil v teoriji polinomskih kolobarjev. Naj $\mathbb{Q}[x]$ označuje kolobar polinomov z racionalnimi koeficienti v nedoločenki $x$ . Na kolobar $\mathbb{Q}[x]$ lahko pogledamo tudi kot na neskončno razsežen vektorski prostor nad obsegom $\mathbb{Q}$ . Poleg standardne baze

$\Sigma = \{1,x,x^2,x^3,...\}$

prostora $\mathbb{Q}[x]$ definirajmo še bazi

$\Sigma_p = \{1,x,x^\underline{2},x^\underline{3},...\} = \{1,x,x(x-1),x(x-1)(x-2),...\},$ $\Sigma_n = \{1,x,x^\bar{2},x^\bar{3},...\} = \{1,x,x(x+1),x(x+1)(x+2),...\}.$

Ker so vse tri zgoraj naštete množice baze prostora $\mathbb{Q}[x]$ , lahko vsak polinom vsake od njih zapišemo kot linearno kombinatocijo polinomov iz vsake druge od njih. Koeficienti takšnih razvojev so tesno povezani s Stirlingovimi ter Lahovimi števili.
Dokažimo najprej trditev, ki podaja razvoj standardnih baznih polinomov iz $\Sigma$ po polinomih iz $\Sigma_p$ .

Trditev 3.8
Naj bo $n$ poljubno nenegativno celo število. Tedaj v kolobarju polinomov $\mathbb{Q}[x]$ velja naslednja enakost

$x^n = \sum^n_{k=0}S(n,k)x^\underline{k}.$

Dokaz

Zgornjo trditev lahko pogojno razumemo tako: Prehodna matrika med bazama $\Sigma$ in $\Sigma_p$ je ravno matrika Stirlingovih števil.

Podobne formule, v katerih nastopajo Stirlingova števila 1. vrste in Lahova števila lahko izpeljemo tudi za prehode med preostalimi urejenimi pari baz $\Sigma$ , $\Sigma_p$ in $\Sigma_n$ .

Dokaz

Trditev lahko dokažemo s pomočjo indukcije na naravno število $n$ in rekurzivne formule za $S(n,k)$ povsem računsko. Mi pa bomo raje navedli kombinatorični dokaz.
Naj bo $m$ poljubno naravno število in $A = \{a_1,...,a_m\}$ poljubna $m$ -elementna množica. Kot vemo, je moč množice $A^n$ vseh urejenih $n$ -teric elementov iz $A$ enaka $m^n$ . Pa preštejmo število elementov množice $A^n$ še na drug način.
Za poljuben element $(x_1,...,x_n) \in A^n$ definirajmo ekvivalenčno relacijo $\sim$ na množici $\mathbb{N}_n =\{1,2,...,n\}$ s pravilom: $i \sim j$ , če in samo če $x_i = x_j$ . Ekvivalenčni razredi te relacije tvorijo razbitje množice $\mathbb{N}_n$ na nekaj (vsaj eno in ne več kot $n$ ) nepraznih podmnožic. Pa naj $X_k, k \in \{1,2,...,n\}$ , predstavlja množico vseh tistih elementov iz $A^n$ , ki na tak način porodijo razbitje z natanko $k$ deli.
Dokazati želimo, da je moč množice $X_k$ enaka $S(n,k)m^\underline{k}$ . To storimo tako, da najdemo bijekcijo med $X_k$ in množico $S(\mathbb{N}_n,k) \times \mathcal{V}(A,k)$ . Ena od takšnih bijekcij je na primer preslikava, ki vsaki $m$ -terici iz $X_k$ priredi par $(\mathcal{R},(y_1,...,y_k))$ , kjer je $\mathcal{R}$ razbitje množice $\mathbb{N}_n$ porojeno na zgoraj opisani način z elementi množice $X_k$ , $y_i$ $k$ -terica, ki jo dobimo iz $m$ -terice $(x_1,...,x_m)$ , če pregledujoč z leve proti desni odstranjujemo vse ponovitve elementov, ki smo jih srečali že prej.
Ker je $A_n$ disjunktna unija množic $X_k$ za $k = 1,...,n$ , od tod sledi

$m^n = \sum^n_{k=1}|X_k| = \sum^n_{k=0}S(m,k)m^\underline{k}.$

Ker je $S(m,0) = 1$ za $m \ge 1$ , lahko k vsoti na desni dodamo še člen s $k = 0$ .
Tako smo dokazali, da se polinoma na levi in desni strani enakosti iz trditve ujemata pri neskončno mnogo vrednostih spremenljivke $x$ . Ker pa je vsak polinom iz $\mathbb{Q}[x]$ stopnje $n$ enolično določen že z $n+1$ vrednosti v $n+1$ točkah, to pomeni, da sta polinoma iz trditve resnično enaka.

Kazalo

3 Razbitja množic in razčlenitve števil
3.1 Stirlingova števila druge vrste
3.2 Lahova števila
3.3 Stirlingova števila prve vrste
3.4 Število razčelnitev naravnega števila
3.5 Prostori polinomov in Stirlingova ter Lahova števila

Nazaj

Zapri

Pomoč
Komentarji
Velikost črk
Zapiski
Za učitelja
Natisni

Natisni trenutno prosojnico
Natisni celotno gradivo

Naprej

Četrta lekcija: Razbitja množic in razčlenitve števil

Vaš brskalnik je zastarel

Pritisnite F11

Četrta lekcija: Razbitja množic in razčlenitve števil

Avtor: Primož Potočnik

Sodelujoče organizacije

Hvala za ogled gradiva!

Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.

Sodelujoče organizacije

Dokaz

Dokaz

Dokaz

Dokaz

Dokaz

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	3	1	0	0	0	0
4	0	1	7	6	1	0	0	0
5	0	1	15	25	10	1	0	0
6	0	1	31	90	65	15	1	0
7	0	1	63	301	350	140	21	1

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	1	1	0	0	0	0
4	0	1	2	1	1	0	0	0
5	0	1	2	2	1	1	0	0
6	0	1	3	3	2	1	1	0
7	0	1	3	4	3	2	1	1

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	3	1	0	0	0	0
4	0	1	7	6	1	0	0	0
5	0	1	15	25	10	1	0	0
6	0	1	31	90	65	15	1	0
7	0	1	63	301	350	140	21	1

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	1	1	0	0	0	0
4	0	1	2	1	1	0	0	0
5	0	1	2	2	1	1	0	0
6	0	1	3	3	2	1	1	0
7	0	1	3	4	3	2	1	1

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	3	1	0	0	0	0
4	0	1	7	6	1	0	0	0
5	0	1	15	25	10	1	0	0
6	0	1	31	90	65	15	1	0
7	0	1	63	301	350	140	21	1

n/k	0	1	2	3	4	5	6	7
0	1	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
2	0	1	1	0	0	0	0	0
3	0	1	1	1	0	0	0	0
4	0	1	2	1	1	0	0	0
5	0	1	2	2	1	1	0	0
6	0	1	3	3	2	1	1	0
7	0	1	3	4	3	2	1	1