DIPLOMSKO DELO

(1)

UNIVERZA V LJUBLJANI PEDAGOŠKA FAKULTETA

BARBARA LIKOZAR

PORAZDELITVE

DIPLOMSKO DELO

Ljubljana, 2015

(2)

(3)

Univerza v Ljubljani Pedagoška fakulteta

Univerzitetni študijski program 1. stopnje: Dvopredmetni učitelj Smer: Matematika - Računalništvo

BARBARA LIKOZAR Mentor : doc. dr. Primož Šparl

PORAZDELITVE

DIPLOMSKO DELO

Ljubljana, 2015

(4)

(5)

Družini, fantu in prijateljem

Hvala za vso podporo, spodbudo, pomoč in razumevanje v času študija.

Mentorju doc. dr. Primožu Šparlu

Hvala za strokovno pomoč, usmerjanje in dragocene nasvete pri nastajanju diplomskega dela.

(6)

(7)

Povzetek

Porazdelitve sodijo na področje kombinatorike, v osnovi pa gre za štetje načinov, na katere lahko določen nabor označenih ali neoznačenih predmetov razporedimo v določen nabor označenih ali neoznačenih predalčkov, pri čemer so predalčki lahko prazni ali pa tudi ne.

V diplomskem delu so predstavljene vse vrste porazdelitev, večji poudarek pa je na porazdelitvah, kjer ne razlikujemo ne predmetov ne predalčkov.

Namen pričuječega diplomskega dela je razumljivo in logično predstaviti vrste porazdelitev in izračun njihovega števila. Števila porazdelitev neoznačenih predmetov v neoznačene predalčke so v delu bolj natančno opredeljena, predstavljenih je več načinov njihovega izračuna, kakor tudi korespondenca med obravnavanimi porazdelitvenimi števili in Youn- govimi diagrami.

Za števila porazdelitev neoznačenih predmetov v neoznačene neprazne predalčke je izraču- nana eksplicitna formula za primere, ko imamo na voljo največ tri predalčke. Predstavljeni so tudi tabelarni način zapisovanja teh števil in zanimivosti, ki smo jih odkrili med opazovanjem tabele. S pomočjo opazovanja in študija porazdelitvenih števil je predstavljenih in dokazanih tudi nekaj porazdelitvenih identitet, s katerimi prikažemo, kako iz porazdelitev enega tipa dobimo porazdelitve drugega tipa in obratno. Dokazi so večinoma izpeljani s pomočjo konjugiranih parov porazdelitev.

Ključne besede: diskretna matematika, porazdelitve, teorija števil, kombinatorika, porazdelitvena števila, porazdelitvene identitete.

Klasifikacija MSC (2010): 05A17, 11P81.

(8)

(9)

Abstract

Partitions and partition numbers belong to the mathematical field of combinatorics. Par- tition numbers basically represent the number of ways in which we can arrange a specific set of marked or unmarked items into a sets of marked or unmarked boxes where the boxes can be either empty or not. This thesis contains presentations of all types of partition numbers but the focus is on the partition numbers where neither items nor boxes are distinguishable.

The purpose of this thesis is to present the various types of partitions and the calcu- lation of their number in an understandable way. Partitions of unmarked items into unmarked boxes are studied in more detail and several ways of calculating their number are presented. The thesis also explains the correspondence between partitions and the so called Young diagrams.

An explicit closed formula for the number of partitions of unmarked items into unmarked non-empty boxes for cases where the number of boxes is less than or equal to three is obtained. A presentation of partition numbers in a matrix form is given and several inter- esting observations, that can be made from the corresponding matrix, are presented and proved. Some so called partition identities are presented and proved. They establish a correspondence between partitions of two different types. They are mainly proved using the notation of so called conjugate partitions.

Key words: discrete mathematics, partitions, number theory, combinatorics, partition numbers, partition identities.

MSC (2010) Classification: 05A17, 11P81.

(10)

(11)

Kazalo

1 Uvod 1

2 Vrste porazdelitev 3

2.1 Ločimo predmete, ne ločimo predalčkov . . . 4

2.2 Ločimo predmete, ločimo predalčke . . . 6

2.3 Ne ločimo predmetov, ločimo predalčke . . . 6

2.4 Ne ločimo predmetov, ne ločimo predalčkov . . . 7

3 Število porazdelitev na določeno število delov 9 3.1 Youngov in Ferrersov diagram . . . 9

3.2 Rekurzivna zveza za števila p_k(n) . . . 10

3.3 Števila p_k(n) zak ≤3 . . . 14

3.4 Trikotniški tabelarni zapis . . . 17

4 Porazdelitveno število p(n) 21 4.1 Število urejenih razdelitev števila n . . . 21

4.2 Alternativna definicija porazdelitvenega števila . . . 23

4.3 Konjugirani pari . . . 24

4.4 Porazdelitvene identitete . . . 26

5 Sklep 35

Literatura 37

(12)

(13)

Slike

3.1 Predstavitev porazdelitve 4 + 2 + 1 s Ferrersovim (levo) in Youngovim

(desno) diagramom. . . 10

3.2 Korespondenca med porazdelitvijo(4,3,3,2,1)in pripadajočim Youngovim diagramom. . . 11

3.3 Slikovna predstavitev dokaza 3.2 . . . 12

3.4 Slikovna predstavitev števil pk(n). . . 13

4.1 Predstavitev različnih porazdelitev vagonov oziroma p(7). . . . 23

4.2 Konjugiran par porazdelitev ponazorjen s Youngovima diagramoma . . . . 25

4.3 Konjugirani pari za p(7), prikazani z Youngovimi diagrami . . . . 26

4.4 Grafična ponazoritev trditve 4.5 . . . 29

4.5 Grafična ponazoritev izreka. . . 33

(14)

(15)

Tabele

2.1 Vrste porazdelitev. Pri številu porazdelitev je zapis za primer zn predmeti in k predalčki. . . 8 3.1 Tabela števil p_k(n) do vključno n= 24. . . 18 4.1 Števila urejenih razdelitev g(n). . . . 22

(16)

(17)

Poglavje 1 Uvod

Beseda porazdelitev oziroma porazdeljevanje se do neke mere že sama predstavi in bralcu pove, o čem bo govora v diplomskem delu. Ponavadi pod tem pojmom razumemo, da neko celoto, na primer skupino ljudi ali množico predmetov, razdelimo na manjše dele.

Matematična obravnava porazdelitev, kar je osrednja tema tega diplomskega dela, pa naj bi imela že precej dolgo zgodovino. Andrews navaja [2], da prvi zapisi, ki so jih znanstveniki našli in jih povezujemo s porazdelitvenim številom, segajo celo v kameno dobo. Bolj poglobljeno ukvarjanje s porazdelitvami in njihovim številom se je pričelo šele v 18. stoletju, ko jih je raziskoval priznani matematik Leonhard Euler.

Za začetek bomo predstavili sam pojem porazdelitve in si ogledali, kje v matematiki jih lahko zasledimo. Porazdelitve so tema, ki smo jo tekom dodiplomskega izobraževanja, sicer zgolj površinsko, obravnavali pri predmetu Diskretna matematika. Uvrščamo jih med principe preštevanja, ki v matematiki sodijo na področje Kombinatorike. Pripada- joča števila porazdelitev so v angleški literaturi znana pod imenom Partition numbers, posamezne porazdelitve na celoštevilske dele pa Integer partitions. Beseda partition nas spominja na poslovenjeno besedo particija, ki jo običajno povežemo z računalniškimi diski.

Particija diska je del diska, sami pa se odločimo, koliko “particij” bo imel naš disk in s katerimi vsebinami oziroma datotečnimi sistemi bomo zapolnili določeno particijo. Denimo, da imamo nov disk (ali da formatiramo starega) in želimo nanj naložiti nek operacijski sistem. Računalnik nas v obeh primerih vpraša, koliko različnih particij želimo, torej na koliko (neodvisnih) delov želimo razdeliti naš trdi disk. Sami torej lahko izbiramo, kako bomo prostor na disku razdelili oziroma koliko delov želimo in koliko prostora bomo na- menili posameznemu delu. To našo določitev lahko razumemo kot neke vrste porazdelitev.

1

(18)

2 Poglavje 1. Uvod V 2. poglavju bomo najprej predstavili vse skupine porazdelitev in jih na kratko opisali ter navedli primere. V nadaljevanju diplomskega dela, torej v poglavjih 3 in 4, se bomo osredotočili le na eno skupino porazdelitev, in sicer na tiste, pri katerih ne razlikujemo niti predmetov niti predalčkov. Glede na to. ali zahtevamo, da so predalčki neprazni ali ne, pri- padajoče število imenujemoŠtevilo porazdelitev na določeno število delovinPorazdelitveno število. Porazdelitvena števila so matematikom ena najbolj zanimivih števil; najbrž tudi zato, ker ne poznamo lepe zaključene formule za izračun poljubnega porazdelitvenega števila. Predstavili bomo, kako lahko ta števila izračunamo rekurzivno, si ogledali grafično predstavitev teh števil, trikotniški tabelarni zapis, lastnosti obeh vrst števil in izpeljali tudi dokaze osnovnih trditev, ki smo jih odkrili tekom študija porazdelitvenih števil.

(19)

Poglavje 2

Vrste porazdelitev

S problematiko porazdeljevanja se srečujemo pogosto v našem vsakdanu, vendar se ga običajno lotimo spontano in ne razmišljamo o vseh možnih načinih porazdeljevanja, še posebej, kjer je število predmetov in/ali predalčkov veliko. Včasih, ko obravnavamo kakšne specifične probleme, pa je kljub vsemu potrebno vedeti, koliko je vseh možnih porazdelitev. Podobno kot pri sorodni temi iz osnovnih principov preštevanja, izborih, tudi pri porazdelitvah razlikujemo različne primere, kjer delimo bodisi enake ali različne predmete v enake ali različne enote/predalčke, pri čemer so predalčki lahko prazni ali pa ne. Za začetek definirajmo, kaj porazdelitve sploh so.

Poglavje je povzeto predvsem po viru [6].

Definicija 2.1. Matematična porazdelitev je razdelitev oziroma razmestitev dolo- čenih predmetov (označenih ali neoznačenih) po predalčkih (označenih ali ne).

Pri porazdelitvah, podobno kot pri izborih, nas običajno še najbolj zanima število porazdelitev določenega tipa. Bistvenega pomena pri računanju števila porazdelitev je torej razlikovanje primerov, kjer obravnavane predmete med seboj razlikujemo ali kjer jih ne, predalčke med seboj razlikujemo ali ne in ali smejo biti razpoložljivi predalčki prazni ali ne. Razlikovanje teh karakteristik nam da skupaj osem različnih možnosti.

V nadaljevanju tega poglavja bodo te možnosti predstavljene skozi štiri razdelke, in sicer glede na označenost/neoznačenost predmetov in označenost/neoznačenost predalčkov, vsak razdelek pa bo obravnaval tako možnosti, kjer so predalčki lahko prazni, kot možnosti, kjer predalčki ne smejo biti prazni. Preden se lotimo opisovanja možnosti in predstavitve različnih porazdelitev, si oglejmo še osnovna kombinatorična principa, ki ju imenujemo pravilo vsote in pravilo produkta in ju bomo potrebovali v nadaljevanju diplomskega dela.

3

(20)

4 Poglavje 2. Vrste porazdelitev Izrek 2.2. Naj bodo A1, A2, . . . , An poljubne neprazne končne množice. Če so te množice paroma disjunktne, velja

|A₁∪A₂∪ · · · ∪A_n|=|A₁|+|A₂|+...+|A_n|.

Pravilo vsote torej pravi, da kardinalnost množice A, ki smo jo razbili nan nepraznih kosov, lahko določimo tako, da posebej določimo kardinalnosti posameznih kosov in jih potem seštejemo. Porazdelitve lahko tako ločimo glede na nek dejavnik, določimo število porazdelitev posameznega tipa, potem pa dobljena števila seštejemo.

Izrek 2.3. Naj bodo A₁, A₂, . . . , A_n poljubne neprazne končne množice. Tedaj velja

|A₁×A₂× · · · ×An|=|A₁| · |A₂| · · · |An|.

Nekoliko poenostavljeno, pravilo produkta pove naslednje: če lahko elemente množice, na primer porazdelitve, opišemo tako, da se za vsak posamezen element oziroma porazdelitev v n korakih odločamo med fiksnim številom možnosti (na primer ki na i-tem koraku), in velja, da je odločitev na i-tem koraku neodvisna od odločitev na ostalih ko- rakih, potem ima množica k₁k₂· · ·k_n elementov.

2.1 Ločimo predmete, ne ločimo predalčkov

Že sam naslov podrazdelka pove, da bo opisoval možnosti, kjer predmete med seboj razlikujemo, predalčkov pa ne. V resnici gre za razbitja dane množice na njene podmnožice.

Število razbitij dane množice velikostinnaknepraznih podmnožic imenujemoStirlingovo število druge vrste in ga običajno označujemo bodisi z ⁿⁿ_k^o ali s S(n, k). V nadaljevanju bomo uporabili oznakoⁿⁿ_k^o.

Izrek 2.4. Za Stirlingova števila druge vrste veljajo naslednje trditve:

1. ⁿⁿ₀ô= 0; za n >0 2. ⁿⁿ_kô= 0; za n < k 3. ⁿⁿ₁ô= 1; za n ≥1 4. ⁿⁿ_nô= 1; za n ≥0

5. ⁿⁿ_kô=k·ⁿⁿ⁻¹_k ô+ⁿⁿ⁻¹_k−1ô; 1< k < n

Dokaz. Prve štiri trditve izhajajo neposredno iz definicije (spomnimo se, da morajo biti predalčki neprazni), peto trditev pa dokažemo po pravilu vsote. Ker so predmeti različni, jih lahko oštevilčimo. Opazimo, da lahko porazdelitve ločimo na dva bistveno različna tipa, in sicer:

(21)

2.1. Ločimo predmete, ne ločimo predalčkov 5

• predmet številka 1 je sam v svojem predalčku;

• v predalčku, ki vsebuje predmet številka 1, sta vsaj dva predmeta.

Porazdelitve prvega tipa si lahko predstavljamo tako, da predmet številka 1 damo v poljuben predalček, preostalih n −1 predmetov pa moramo porazdeliti med k−1 preostalih nepraznih predalčkov, kar lahko storimo na ⁿⁿ⁻¹_k−1^o načinov. Pri porazdelitvah drugega tipa, kjer predmet številka 1 v predalčku ni sam, zopet porazdeljujemo preostalih n−1 predmetov, tokrat poljubno v k enakih nepraznih predalčkov. Za predmet številka 1 imamo potem na voljo k predalčkov (ki so sedaj že neprazni in zato različni

med seboj). Torej je teh porazdelitevk·ⁿⁿ⁻¹_k ^o.

Primer. Viktor je velik zbiratelj različnih znamk iz vsega sveta. Za svoje znamke ima na voljo k enakih zbirateljskih albumov. Na koliko različnih načinov lahko Viktor porazdeli svoje znamke v albume, če mora v vsakega od albumov vložiti vsaj eno znamko?

Pri tem nas ne zanima, v kakšnem vrstnem redu bo znamke za posamezni album vložil v album, temveč samo katere znamke gredo v isti album.

Lotimo se še obravnave porazdelitev, kjer ločimo predmete, predalčkov ne razlikujemo in predalčki lahko ostanejo prazni. Ponovno lahko uporabimo pravilo vsote in seštejemo porazdelitve, pri katerih ni praznih predalčkov, porazdelitve, kjer je prazen en predalček, in tako naprej seštevamo vse dokler nimamo na voljo le še enega predalčka. Tako je vseh porazdelitevn različnih predmetov v k enakih, ne nujno nepraznih predalčkov,

k

X

i=1

(n i

)

.

V primeru, da je k ≥ n (ker so predalčki lahko prazni, računamo tudi možnosti, kjer je predalčkov enako ali več kot predmetov), dobimo t. i. Bellovo število B_n = ^Pⁿ_i=1ⁿⁿ_i^o. Bellovo število torej določa število razbitij dane množice znelementi, kar je ravno število vseh ekvivalenčnih relacij na množici z n elementi.

Primer. Nika si je v trgovini v nakupovalno košaro nabrala n različnih izdelkov in se odpravila k samopostrežni blagajni. Ko izbrane izdelke skenira, jih lahko razdeli v k enakih vreč. Na koliko možnih načinov lahko Nika razdeli izdelke v nakupovalne vreče, če so le-te lahko prazne?

(22)

6 Poglavje 2. Vrste porazdelitev

2.2 Ločimo predmete, ločimo predalčke

Možnost, kjer razlikujemo tako predmete kot predalčke in so predalčki lahko prazni, je preprosta. Pri vsakem predmetu se neodvisno od drugih predmetov odločimo, v kateri predalček ga bomo dali, in tako dobimo pri n predmetih ink predalčkih kⁿ možnosti.

Primer. Na likovni delavnici za otroke imamo na voljo tempere različnih barv. Na koliko načinov si lahko otroci med seboj razdelijo tempere (upoštevamo tudi možnosti, ko kak otrok ostane brez tempere)?

Izračun možnosti, kjer mora biti v vsakem od k predalčkov vsaj po en element, je bolj netrivialen. Reševanja tega problema se lotimo tako, da najprej pogledamo, kako bi predmete razporedili v predalčke, ki jih med seboj ne razlikujemo, torej koliko različnih porazdelitev bi dobili, če bi različne predmete razdelili v enake neprazne predalčke. Rešitev nam je znana že iz prejšnjega podrazdelka. Gre za Stirlingova števila druge vrste. Ker pa nismo upoštevali, da predalčke med seboj razlikujemo, se je potrebno sedaj odločiti še, kako bomo predalčke označili. Prvi predalček lahko označimo na k načinov, drugega na k −1 načinov, itd. Zato ⁿⁿ_k^o po pravilu produkta pomnožimo s k!. Iskano število porazdelitev n različnih predmetov v k različnih nepraznih predalčkov je torej k!ⁿⁿ_k^o.

Primer. Odpravimo se v poletno kolonijo zn otroki. Pripravljenih imamok različnih delavnic in otroke razdelimo v skupine, in sicer tako, da se vsake delavnice udeleži vsaj en od otrok. Na koliko različnih možnosti lahko otroke porazdelimo po skupinah?

2.3 Ne ločimo predmetov, ločimo predalčke

V primeru, kjer ne ločimo predmetov, predalčke pa in so le-ti lahko prazni, se je potrebno odločiti le, koliko predmetov bomo dali v posamezen predalček. Rešitev si lahko predstavljamo tako, da gre v i-ti predalčekn_i ∈N predmetov in da veljan₁+n₂+. . .+n_k =n. V resnici se sprašujemo, koliko nenegativnih celoštevilskih rešitev ima ta enačba. Zamislimo si, da za n₁ enakimi predmeti postavimo mejo in tako nadaljujemo vse do n_k−1 enakih predmetov (od zadnje meje nam ostane šenk predmetov). Očitno vsako tako porazdelitev lahko določimo, če povemo, na katerih izmed n+k−1 mest stoji k−1 t. i. mej. Tako je vseh porazdelitev

n+k−1 k−1

!

= n+k−1 n

!

.

(23)

2.4. Ne ločimo predmetov, ne ločimo predalčkov 7

Primer. Za veliko noč se odločimo prebarvatin jajc (jajc pred barvanjem ne razlikujemo) s k različnimi barvami. Na koliko možnih načinov lahko pobarvamo pirhe, če ni nujno, da uporabimo vse razpoložljive barve?

Izračuna možnosti, kjer ne ločimo predmetov, ločimo pa predalčke, ki morajo biti neprazni, se lotimo na podoben način, kot v zgornjem primeru. Pri tem mora seveda zaradi nepraznosti predalčkov veljatin≥k. Nepraznost dosežemo tako, da najprej v vsak predalček damo po en predmet, preostalihn−k predmetov pa poljubno porazdelimo. Po zgornjem je torej možnih porazdelitev

k+ (n−k)−1 n−k

!

= n−1 n−k

!

= n−1

n−1−(n−k)

!

= n−1 k−1

!

.

Primer. Božiček mora zavitinenakih daril, na voljo pa imakrazličnih vrst darilnega papirja. Na koliko različnih načinov lahko Božiček zavije darila, če mora vsakega od darilnih papirjev uporabiti pri vsaj enem od daril?

2.4 Ne ločimo predmetov, ne ločimo predalčkov

Zadnja skupina porazdelitev in hkrati skupina, kateri se bomo posvetili v nadaljevanju diplomskega dela, so particije naravnih števil. V tem primeru ne razlikujemo niti med predmeti niti med predalčki. Particije naravnih števil jih imenujemo zato, ker se sprašu- jemo le o tem, na koliko različnih načinov lahko zapišemo število n kot vsoto k nenegativnih celih števil. Pri tem vrstni red sumandov ni pomemben. Števila, kjer morajo biti predalčki neprazni, označujemo sp_k(n) ali p_n,k (v nadaljevanju bomo uporabljali oznako p_k(n)). Več o številih p_k(n) sledi v naslednjem poglavju.

Število porazdelitev n enakih predmetov v k enakih, ne nujno nepraznih predalčkov, je podobno kot zgoraj

k

X

i=1

p_i(n).

V primeru, ko je k ≥ n, gre za računanje števila, ki ga bomo podrobneje opisali v 4.

poglavju, izračuna pa se ga pa kot

n

X

i=1

p_i(n) = p(n).

(24)

8 Poglavje 2. Vrste porazdelitev Vse možnosti porazdelitev so še dodatno strnjene v pregledni tabeli 2.1: [4]

Predmeti označeni Predalčki označeni Predalčki lahko prazni Število porazdelitev

DA DA DA kⁿ

NE k!ⁿⁿ_k^o

DA NE DA ^P^k_i=1ⁿⁿ_i^o

NE ⁿⁿ_k^o

NE DA DA ^k+n−1_n

NE ⁿ⁻¹_k−1

NE NE DA ^P^k_i=1p_i(n)

NE pk(n)

Tabela 2.1: Vrste porazdelitev. Pri številu porazdelitev je zapis za primer z n predmeti in k predalčki.

(25)

Poglavje 3

Število porazdelitev na določeno število delov

Najprej se bomo posvetili porazdelitvam enakih predmetov na enake neprazne predalčke.

Kot smo se dogovorili že v prejšnjem poglavju, število takih porazdelitev, kjer imamo n predmetov in k predalčkov, označimo s p_k(n). To število torej predstavlja tudi število bistevno različnih celoštevilskih zapisov števila n kot vsote k naravnih števil. Pri tem z “bistveno različnih” ciljamo na to, da vrstni red sumandov ni pomemben. Na primer, p₃(5) = 2, saj sta edini možnosti3 + 1 + 1 in2 + 2 + 1(ostalih možnosti, ki bi dale enako rešitev, 1 + 3 + 1,1 + 1 + 3,2 + 1 + 2 in 1 + 2 + 2, ne upoštevamo). Za lažjo predstavo številp_k(n) si zamislimo igro, kjer sestavljamo stolpe iz n enakih kock, pri čemer na tla najprej položimok kock, ostalihn−kkock pa zlagamo na te kocke. Pri tem upoštevamo, da gradimo stolpce v višino in da morajo biti ti stolpci urejeni po velikosti.

V kolikor ni navedeno drugače, je snov tega poglavja povzeta po virih [7] in [3].

3.1 Youngov in Ferrersov diagram

Za vsako porazdelitev enakih predmetov v enake predalčke obstaja tudi ustrezen grafični prikaz z diagramom. Gre za t. i. Youngove oziroma Ferrersove diagrame, ki jih bomo uporabili tudi pri dokazovanju izrekov in trditev v nadaljevanju. Norman Macleod Fer- rers je prvi zasnoval diagram, ki nam olajša obravnavo porazdelitvenih števil. Ferrersov diagram je predstavljen s pikami, precej podobno notacijo pa je predstavil tudi Alfred Young, ki je namesto pik uporabil kvadratke. Velja omeniti tudi, da različni viri navajajo različne notacije Ferrersovega in Youngovega diagrama. Ponekod avtorji navajajo, da naj

9

(26)

10 Poglavje 3. Število pk(n) bi bili elementi nanizani vzdolž vrstic, ponekod pa vzdolž stolpcev ipd. Na sliki 3.1 je prikazana ena izmed notacij porazdelitve 4 + 2 + 1 števila 7 s Ferrersovim in Youngovim diagramom.

Slika 3.1: Predstavitev porazdelitve4 + 2 + 1 s Ferrersovim (levo) in Youngovim (desno) diagramom.

Z obema diagramoma prikazujemo grafičen zapis porazdelitev, in ker različni viri navajajo različne načine zapisa diagrama, bomo v nadaljevanju obravnavane diagrame vedno imenovali Youngovi diagrami, zapisovali pa jih bomo s kvadratki.

Definicija 3.1. Naj bosta n in k naravni števili in naj bodo n₁ ≥ n₂ ≥ . . . ≥ n_k nar- avna števila, tako da je n = n₁ +n₂+. . .+n_k . Tedaj je Youngov diagram porazdelitve n =n₁+n₂+. . .+n_k diagram n kvadratkov, urejenih vzdolž v levo poravnane vrstice, pri čemer je v i-ti vrstici n_i kvadratkov.

Dogovorimo se, da bomo v nadaljevanju porazdelitev n =n₁+n₂+. . .+nk, kjer je n₁ ≥n₂ ≥. . .≥n_k, krajše označili kar z (n₁, n₂, . . . , n_k). Definicija diagrama nam pove, da je vsaka vrstica enake ali krajše dolžine kot predhodna vrstica in da so vse vrstice levo poravnane. Opazimo, da obstaja povratno enolična korespondenca med Youngovimi diagrami in porazdelitvami, pri čemer vsaka vrstica Youngovega diagrama ustreza enemu predalčku. Na sliki 3.2 je prikazana porazdelitev (4,3,3,2,1) števila 13 z Youngovim diagramom. Za lažjo predstavo korespondence med porazdelitvami in diagrami so tokrat ob diagramu zapisane še dolžine posameznih vrstic in število vseh kvadratkov v diagramu.

(27)

3.2. Rekurzivna zveza za števila pk(n) 11

Slika 3.2: Korespondenca med porazdelitvijo (4,3,3,2,1) in pripadajočim Youngovim diagramom.

3.2 Rekurzivna zveza za števila p

_k

(n)

V tem razdelku bomo predstavili in dokazali rekurzivno zvezo med števili p_k(n), ki nam bo v razdelku 3.4 omogočila izračun vseh teh števil don = 24.

Izrek 3.2. Naj bo n > k. Tedaj velja:

pk(n) =

k

X

s=1

ps(n−k) (3.1)

Dokaz. Izrek lahko dokažemo s pomočjo Youngovih diagramov. Vemo, da bomo v prvo vrstico vedno zapisali toliko kvadratkov, kot je elementov v prvem predalčku. V vsaki naslednji vrstici pa je toliko elementov, kot jih je v naslednjih predalčkih. Torej je število predalčkovk enako številu kvadratkov v prvem stolpcu. Preostalihn−k kvadratkov nato poljubno zapisujemo v stolpce desno od prvega v Youngov diagram. Edina omejitev je, da diagram ne sme presegati dolžine prvega stolpca. Diagramom tako lahko prvi stolpec tudi odstranimo, a se pri novem Youngovem diagramu z n −k kvadratki moramo zavedati, da “nov” prvi stolpec ne sme presegati k kvadratkov. S tem dobimo nove Youngove diagrame za particijo zapisa p_s(n−k), kjer je s ≤ k. Slika 3.3 prikazuje porazdelitev (4,3,3,3,2,1)števila 16, ki je ena izmed 35. porazdelitev p₆(16). Porazdelitveno število je po definiciji enako^P⁶_s=1p_s(10) =p₁(10) +p₂(10) +p₃(10) +p₄(10) +p₅(10) +p₆(10) = 1 + 5 + 8 + 9 + 7 + 5 = 35. Opazimo, da ima dobljeni Youngov diagram na drugi strani res 10 kvadratkov - porazdelitev(3,2,2,2,1) in število kvadratkov v stolpcih ne presega 6 (kar je ponazorjeno z rdečo vodoravno črto črto).

(28)

12 Poglavje 3. Število pk(n)

Slika 3.3: Slikovna predstavitev dokaza 3.2

Trditev 3.3. [6] Naj bosta n in k naravni števili. Tedaj velja enakost p_k(n) = p_k−1(n−1) +p_k(n−k)

in sledeči robni pogoji:

1. p_k(n) = 0; za k > n.

2. p_n(n) = 1; za n ≥0.

3. p₀(n) = 0; za n >0.

4. p₁(n) = 1; za n >0.

Dokaz. Število porazdelitev p_k(n) lahko po pravilu vsote dobimo kot vsoto števila porazdelitev dveh tipov, in sicer tistih,

• kjer ima vsaj eden izmed predalčkov samo en predmet;

• kjer ima vsak predalček vsaj dva predmeta.

Pri prvem tipu je takšnih porazdelitev očitno p_k−1(n−1), kajti v poljuben predalček damo en predmet, ostalih n−1predmetov pa porazdelimo v preostalih k−1predalčkov.

Pri drugem tipu porazdelitev pa najprej zagotovimo, da je v vsakem od predalčkov vsaj

(29)

3.2. Rekurzivna zveza za števila pk(n) 13 en predmet, preostalih n−k predmetov pa poljubno razdelimo v k predalčkov tako, da damo v vsakega po vsaj en predmet. Torej je možnosti p_k(n −k). Po pravilu vsote je torej res p_k(n) =pk−1(n−1) +p_k(n−k). Po definiciji s številom p_k(n) povemo, na koliko bistveno različnih načinov lahko razporedimon predmetov v natanko k predalčkov, s čimer je določitev robnega pogoja 1 jasna (ne moremo imeti več predalčkov kot predmetov, kajti v nasportnem primeru ne moremo zagotoviti nepraznosti le-teh). Če je število predmetov enako številu predalčkov, je tudi jasno, da je možna ena sama porazdelitev, in sicer tista, pri kateri je vsak predmet v svojem predalčku, s čimer obvelja robni pogoj 2. Robni pogoj 3 določa, da predmetov ne moremo porazdeljevati, če nimamo na voljo nobenega predalčka, robni pogoj 4 pa pravi, da lahkon predmetov porazdelimo v en sam

predalček le na en način.

Na sliki 3.4 si lahko ogledamo prikaz porazdelitev in pripadajočih števil p_k(n) z Youngovimi diagrami do vključno 7 (v vrsticah so predstavljena števila n = 1, . . . ,7 ,v stopcih pa k = 1, . . .7, za n ≥ k). ¹ Na sliki je zapisano tudi število p(n), ki smo ga v prejšnjem poglavju 2 definirali kot ^Pⁿ_i=1pi(n) =p(n).

Slika 3.4: Slikovna predstavitev števil p_k(n).

1Kvadratki so ne glede na različne barve enaki. Različne barve kvadratkov ponazarjajo različne ve- likostik.

(30)

3.3 Števila p

_k

(n) za k ≤ 3

S pomočjo rekurzivne zveze iz trditve 3.3 lahko izračunamo eksplicitne formule za števila p_k(n)za prvih nekajk. Da veljap₁(n) = 1, smo ugotovili že v trditvi 3.3. Izračunap₂(n)se lahko lotimo neposredno s pomočjo Youngovega diagrama. Ker je diagram levo poravnan, mora biti v prvih dveh vrsticah vsaj po en element. Po definiciji Youngovega diagrama število kvadratkov v drugi vrstici ne sme presegati števila kvadratkov prve vrstice (torej je dolžina druge vrstice kvečjemu enaka ali manjša od prve). Ko sta si vrstici enaki, je v vsaki od vrstic natanko ⁿ₂ predmetov (pri sodih n). Lahko zapišemo kar p₂(n) = bⁿ₂c (pri sodih številih je teh možnosti natanko ⁿ₂, pri lihih številih pa količnik zaokrožimo navzdol).

Računanje eksplicitnih formul vseh nadaljnjih števil p_k(n) je vedno težje. Pomagajmo si s trditvijo 3.3, da dobimo vsaj še formulo za števila p₃(n). Dobimo p₃(n) =p₂(n−1) + p3(n−3). Takoj opazimo, da za število p2(n−1) lahko uporabljamo zgornjo formulo.

Ostane nam še število p₃(n−3). Število lahko ponovno razbijemo po enakosti iz trditve 3.3 in dobimo p₃(n) =p₂(n−1) +p₂(n−4) +p₃(n−6). Tako lahko nadaljujemo, dokler ne dobimo končne vsote

p₃(n) =

z−1

X

i=0

p₂(n−1−3i),

kjer je n = 3z +o, o ∈ {0,1,2}. Kot smo že omenili, znamo člene vsote eksplicitno izračunati, ker znamo neposredno izračunati p₂(j) za vse j.

Število n smo zapisali kot n = 3z +o in tako si lahko zamislimo, da bomo ločili 6 različnih primerov glede na to, ali jez liho ali sodo število in glede na o ∈ {0,1,2}.

Pa si kar oglejmo vseh šest primerov (ker je p₃(n) = 0 za n <3, bomo privzeli, da je n ≥3).

1. z liho in o = 0. To velja za skupino n ∈ {3,9,15, ...,3 + 6j};j ∈ N⁰. 3 je torej najmanjše obravnavano število. Za vsa števila p₂(n−1−3i) v zgornji vsoti uporabimo dobljeno formulo, pa dobimo p₃(n) =^P^z−1_i=0bⁿ⁻³ⁱ⁻¹₂ c. Razmislimo sedaj, kaj to pomeni v našem primeru. Razvijemo vrsto

z−1

X

i=0

n−3i−1 2

=

n−1 2

+

n−4 2

+· · ·+

5 2

+

2 2

.

Ker vemo, da jen liho število, je števec prvega člena vsoten−1sodo število. Tako dobimo sledečo vsoto:

n−1

2 +n−5

2 + n−7

2 +n−11

2 +· · ·+ 4 2+ 2

2,

(31)

3.3. Števila pk(n) za k ≤3 15 kar pa lahko zapišemo tudi kot

n−3 6

X

i=0

n−6i−1

2 +

n−3 6 −1

X

i=0

n−6i−5

2 =

n+ 3 6

n−1 2

−3

(ⁿ⁻³₆ )(ⁿ⁺³₆ ) 2

+

n−3 6

n−5 2

−3

(ⁿ⁻³₆ )(ⁿ⁻⁹₆ ) 2

= n²+ 3

12 .

2. z liho in o = 1, kar velja za skupino n ∈ {4,10,16, ...,4 + 6j};j ∈ N0. Ponovno razvijemo vrsto

z−1

X

i=0

n−3i−1 2

=

n−1 2

+

n−4 2

+· · ·+

6 2

+

3 2

.

Ker vemo, da je n sodo število, je števec prvega člena vsote n−1 liho število. Tako dobimo sledečo vsoto:

n−2

2 + n−4

2 +n−8

2 + n−10

2 +· · ·+6 2 +2

2, kar pa lahko zapišemo tudi kot

n−4 6

X

i=0

n−6i−2

2 +

n−4 6 −1

X

i=0

n−6i−4

2 =

n+ 2 6

n−2 2

−3

(ⁿ⁻⁴₆ )(ⁿ⁺²₆ ) 2

+

n−4 6

n−4 2

−3

(ⁿ⁻⁴₆ )(ⁿ⁻¹⁰₆ ) 2

= n²−4

12 .

3. z je liho, o = 2; n∈ {5,11,17, ...,5 + 6j};j ∈N. Razvijemo vrsto:

z−1

X

i=0

n−3i−1 2

=

n−1 2

+

n−4 2

+· · ·+

7 2

+

4 2

.

Ker je število v števcu prvega člena vsote sodo, dobimo sledečo vsoto:

n−1

2 + n−5

2 +n−7

2 + n−11

2 +· · ·+6 2 +4

n−5 6

X

i=0

n−6i−1

2 +

n−5 6 −1

X

i=0

n−6i−5

2 =

(32)

n+ 1 6

n−1 2

−3

(ⁿ⁻⁵₆ )(ⁿ⁺¹₆ ) 2

+

n−5 6

n−5 2

−3

(ⁿ⁻⁵₆ )(ⁿ⁻¹¹₆ ) 2

= n²−1

12 .

4. z je sodo,o = 0; n∈ {6,12,18, ...,6 + 6j};j ∈N. Razvijemo vrsto

z−1

X

i=0

n−3i−1 2

=

n−1 2

+

n−4 2

+· · ·+

5 2

+

2 2

.

Ker je število v števcu prvega člena vsote liho, dobimo sledečo vsoto:

n−2

2 +n−4

2 + n−8

2 +n−10

2 +· · ·+ 4 2+ 2

n−6 6

X

i=0

n−6i−2

2 +

n−6 6

X

i=0

n−6i−4

2 =

n 6

n−2 2

−3

(ⁿ⁻⁶₆ )(ⁿ₆) 2

+

n 6

n−4 2

−3

(ⁿ⁻⁶₆ )(ⁿ₆) 2

= n²

12.

5. z je sodo,o = 1; n∈ {7,13,19, ...,7 + 6j};j ∈N. Razvijemo vrsto:

z−1

X

i=0

n−3i−1 2

=

n−1 2

+

n−4 2

+· · ·+

6 2

+

3 2

.

Ker je število v števcu prvega člena vsote sodo, dobimo sledečo vsoto:

n−1

2 +n−5

2 + n−7

2 +n−11

2 +· · ·+ 6 2+ 2

n−7 6

X

i=0

n−6i−1

2 +

n−7 6

X

i=0

n−6i−5

2 =

n−1 6

n−1 2

−3

(ⁿ⁻⁷₆ )(ⁿ⁻¹₆ ) 2

+

n−1 6

n−5 2

−3

(ⁿ⁻⁷₆ )(ⁿ⁻¹₆ ) 2

= n²−1

12 .

(33)

3.4. Trikotniški tabelarni zapis 17 6. z je sodo, o= 2;n ∈ {8,14,20, ...,5 + 6j};j ∈N: Razvijemo vrsto

z−1

X

i=0

n−3i−1 2

=

n−1 2

+

n−4 2

+· · ·+

7 2

+

4 2

.

Ker je število v števcu prvega člena vsote liho, dobimo sledečo vsoto:

n−2

2 + n−4

2 +n−8

2 + n−10

2 +· · ·+6 2 +4

n−8 6

X

i=0

n−6i−2

2 +

n−8 6

X

i=0

n−6i−4

2 =

n−2 6

n−2 2

−3

(ⁿ⁻⁸₆ )(ⁿ⁻²₆ ) 2

+

n−2 6

n−4 2

−3

(ⁿ⁻⁸₆ )(ⁿ⁻²₆ ) 2

= n²−4

12 . Tako smo ugotovili, da zan ≥3velja

p₃(n) =











n²

12; za n≡0 (mod 6)

n²−1

12 ; za n≡ ±1 (mod 6)

n²−4

12 ; za n≡ ±2 (mod 6)

n²+3

12 ; za n≡3 (mod 6).

Ni težko videti, da gre v vseh štirih primerih ravno za naravno število, ki je najbližje številu n²/12. Tako lahko lahko končno ugotovimo, da je p₃(n)∼ ⁿ₁₂² (število zaokroženo na najbližje naravno število). Na podoben način bi se sedaj lahko lotili iskanja eksplicitne formule za števila p4(n) (in vsa nadaljna pk(n) števila), vendar pa smo že pri p3(n) videli, da je iskanje eksplicitne formule zelo zahtevno in dolgotrajno, zato v okviru tega diplomskega dela s tem ne bomo nadaljevali.

3.4 Trikotniški tabelarni zapis

Kot smo že omenili, nam trditev 3.3 omogoča, da rekurzivno zgradimo tabelo vseh števil p_k(n) do neke postavljene meje za k in n. Ker je p(n) = ^Pⁿ_i=1p_i(n), lahko na rob tabele zapišemo še ustezno particijsko število p(n). Tabela vseh števil p_k(n), kjer je 0≤k ≤n≤24, je predstavljena v tabeli 3.1.

(34)

n/k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 p(n)

1 1 1

2 1 1 2

3 1 1 1 3

4 1 2 1 1 5

5 1 2 2 1 1 7

6 1 3 3 2 1 1 11

7 1 3 4 3 2 1 1 15

8 1 4 5 5 3 2 1 1 22

9 1 4 7 6 5 3 2 1 1 30

10 1 5 8 9 7 5 3 2 1 1 42

11 1 5 10 11 10 7 5 3 2 1 1 56

12 1 6 12 15 13 11 7 5 3 2 1 1 77

13 1 6 14 18 18 14 11 7 5 3 2 1 1 101

14 1 7 16 23 23 20 15 11 7 5 3 2 1 1 135

15 1 7 19 27 30 26 21 15 11 7 5 3 2 1 1 176

16 1 8 21 34 37 35 28 22 15 11 7 5 3 2 1 1 231

17 1 8 24 39 47 44 38 29 22 15 11 7 5 3 2 1 1 297

18 1 9 27 47 57 58 49 40 30 22 15 11 7 5 3 2 1 1 385

19 1 9 30 54 70 71 65 52 41 30 22 15 11 7 5 3 2 1 1 490

20 1 10 33 64 84 90 82 70 54 42 30 22 15 11 7 5 3 2 1 1 627

21 1 10 37 72 101 110 105 89 73 55 42 30 22 15 11 7 5 3 2 1 1 792

22 1 11 40 84 119 136 131 116 94 75 56 42 30 22 15 11 7 5 3 2 1 1 1002

23 1 11 44 94 141 163 164 146 123 97 76 56 42 30 22 15 11 7 5 3 2 1 1 1255

24 1 12 48 108 164 199 201 186 157 128 99 77 56 42 30 22 15 11 7 5 3 2 1 1 1575

Tabela 3.1: Tabela števil p_k(n) do vključno n = 24.

(35)

3.4. Trikotniški tabelarni zapis 19 Pogled na dobljeno tabelo razkriva nekaj zanimivosti. Zbrane so v naslednji trditvi.

Trditev 3.4. Veljajo naslednje enakosti:

1. p_k(2k) =p(k) za vse k≥1

2. p_k+i(2k+i) =p(k) za vsa nenegativna cela števila i in k, kjer je i < k

3. p_k+i(2k) =p_k(2k−i) = p(k−i) za vsa nenegativna cela števila i in k, kjer je i < k 4.

p_k(n) =











0; n < k

1; n=k

p(n−k); k+ 1 ≤n≤2k.

Dokaz. Dokaz 1. enakosti sledi neposredno iz trditve 3.3 in sicer:

p_k(2k) =pk−1(2k−1)+p_k(k) =pk−2(2k−2)+pk−1(k)+p_k(k) = pk−3(2k−3)+pk−2(k)+pk−1(k)+p_k(k) =

=. . .=p₁(k) +p₂(k) +· · ·+pk−2(k) +pk−1(k) +p_k(k) =p(k).

Dokaz 2. enakosti dobimo s pomočjo zgornje ugotovitve in trditve 3.3:

pk+i(2k+i) = pk+i−1(2k+i−1) +pk+i(2k+i−(k+i))

| {z }

0

=· · ·=

=p_k(2k) +p_k+1(2k+ 1−(k+ 1))

| {z }

0

=p(k), kar trdi 1. enakost.

Tudi dokaz 3. enakosti sledi neprosredno iz trditve 3.3 in sicer:

p_k+i(2k) = pk+i−1(2k−1) +p_k+i(2k−(k+i))

| {z }

0

=· · ·=

=p_k(2k−i) +p_k+1(2k−(k+ 1))

| {z }

0

=p_k(2k−i),

(36)

20 Poglavje 3. Število p_k(n) kar pa je enako p(k−i), saj je po 2. enakosti p_k+i(2k) =pk−i+2i(2(k−i) + 2i) =p(k−i).

Da 4. enakost velja v primeru, ko je n ≤ k, sledi že iz trditve 3.3. V primeru, ko je k + 1 ≤ n ≤ 2k, lahko zapišemo n = 2k −i. Sledi, da je i < k, torej je po 3. enakosti

p_k(n) =p_k(2k−i) =p(k−i) =p(n−k).

(37)

Poglavje 4

Porazdelitveno število p(n)

Pri porazdelitvah naravnega števila gre v splošnem za štetje bistveno različnih zapisov danega naravnega števila kot vsote naravnih števil. S tem želimo povedati, da vrstni red sumandov ni pomemben¹, zato se lahko tudi dogovorimo, da bomo števila urejali kar po velikosti od največ- jega do najmanjšega.

Naredimo hiter prelet že znanega. Kot je bilo omenjeno že v uvodu, v angleški literaturi za te porazdelitve uporabljajo izraz integer partition, kar bi v prevodu pomenilo razbitje celega števila. V drugem poglavju smo jih definirali kot porazdeljevanje neoznačenih predmetov v neoznačene predalčke, pri čemer so predalčki lahko tudi prazni, poleg tega pa je predalčkov vsaj toliko, kot je predmetov. Število p(n) zato lahko izrazimo tudi s števili, ki smo jih obravnavali v prejšnjem poglavju. Kot smo videli, namreč velja p(n) = ^Pⁿ_i=1p_k(n), pri čemer se lahko dogovorimo še za robne pogoje p(0) = 1 in p(n) = 0za negativne n. Snov poglavja je povzeta po virih [2], [1], [7], [3], [8] in [9].

4.1 Število urejenih razdelitev števila n

Zaključene formule za številap(n)ne poznamo, kar je najbrž tudi eden izmed razlogov, zakaj so ta števila v preteklosti vzbudila toliko zanimanja. Tudi ko poznamo vrednostip(i), kjer jei < n, število p(n) težko neposredno določimo. Enega izmed bolj znanih izračunov tega števila na ta

1Načina4 + 1in 1 + 4štejemo kot en sam način zapisa števila 5 kot vsote naravnih števil

21

(38)

22 Porazdelitveno število p(n) način je odkril matematik Leonhard Euler, ki je bil eden prvih, ki se je lotil iskanja formule za p(n). Njegov izrek števila p(n) poveže s t. i. petkotniški števili. Več o petkotniških številih si lahko preberete v [5]. Porazdelitvena številap(n)so za matematike zelo zanimiva tudi zato, ker je naraščanje pripadajoče funkcije precej nenavadno. Za primerjavo si najprej oglejmo število urejenih razdelitev števila n. To število nam pove kolikšno je število vseh možnih razdelitev števila n oziroma vse možnosti zapisov naravnega števila n kot vsote naravnih števil, kjer pa je vrstni red pomemben². V tabeli 4.1 je prikazan vzorec teh števil, iz katerega pa lahko dokaj hitro ugotovimo splošno formulo za ta števila. Da je formula prava, tudi sicer zlahka ugotovimo, saj si lahko zamislimo, da je medn predmeti lahkon−1pregrad in pri vsaki od teh pregrad se odločimo, ali jo postavimo med dva enaka predmeta, ali ne. Hitro lahko zapišemo tabelo 4.1, števila urejenih razdelitev g(n).

n Urejene razdelitveg(n)

1 1

2 2

3 4

4 8

5 16

6 32

7 64

8 128

n 2ⁿ⁻¹

Tabela 4.1: Števila urejenih razdelitev g(n).

Pri urejenih razdelitvah je torej formula dokaj preprosta in se glasi g(n) = 2ⁿ⁻¹. Pri številu p(n) pa je potrebno od tega števila odšteti število vseh tistih porazdelitev, ki se ponavljajo, če vrstnega reda zapisa ne upoštevamo. Izkaže se [3], da številap(n)naraščajo počasneje kot vsaka eksponentna funkcija g(n) = cⁿ, za katero velja c >1, hkrati pa hitreje kot vsaka polinomska funkcija f(n) = ^P^k_i=0a_inⁱ.

2Število 3 ima tako 4 možne porazdelitve, kjer je vrstni red pomemben in sicer3 = 2 + 1 = 1 + 2 = 1 + 1 + 1.

(39)

Alternativna definicija porazdelitvenega števila 23

4.2 Alternativna definicija porazdelitvenega števila

Porazdelitveno število p(n) lahko obravnavamo skozi različne igre. Zamislimo si, da imamo na voljon enakih vagonov in premislimo, na koliko bistveno različnih načinov jih lahko pripnemo na največ n enakih lokomotiv. Na sliki 4.1 so ponazorjene vse možnosti priklapljanja sedmih enakih vagonov na največ sedem enakih lokomotiv³. Enačba p(n) = ^Pⁿ_i=1p_i(n) nam pove, koliko različnih porazdelitev vagonov imamo pri točno določenem številu lokomotiv p(7) =

P7

i=1p_i(7) =p₁(7) +p₂(7) +p₃(7) +p₄(7) +p₅(7) +p₆(7) +p₇(7) = 1 + 3 + 4 + 3 + 2 + 1 + 1 = 15, kar je zapisano na levi strani slike. Na desni strani slike so nanizane vse možnosti porazdelitev vagonov.

Slika 4.1: Predstavitev različnih porazdelitev vagonov oziromap(7).

Na sliki 4.1 je torej ponazorjeno, da p(7) = 15, kar pomeni, da število 7 lahko zapišemo kot vsoto naravnih števil na 15 bistveno različnih načinov.

3Vagoni se med seboj ne razlikujejo, obarvani so glede na število vagonov, ki so pripeti skupaj.

(40)

24 Porazdelitveno število p(n) Sicer smo število p(n) vpeljali preko števil p_k(n) že v prejšnjih poglavjih, a za vsak primer zapišimo definicijo številp(n)še na malce drugačen način formalno.

Definicija 4.1. Naj bon poljubno nenegativno celo število. Številop(n)je število rešitev enačbe n=x₁+x₂+x₃+. . .+x_n;

(x1 ≥x2 ≥x3 ≥. . .≥xn ≥0); x1, x2, . . . xn∈Z.

V zgoraj navedenem primeru so x_n posamezni sumandi porazdelitve (notacija, ki jo lahko opazimo na desni strani slike 4.1). Zapis n=x₁+x₂+x₃+. . .+x_n lahko preoblikujemo tudi v zapis n =y1+ 2y₂+. . .+nyn; za yi ≥ 0 in 1≤ i ≤ n. Število yi označuje število števil xj

v zgornjem zapisu, ki so enaki i. S številom y_i torej označujemo število predalčkov, v katerih je natanko i predmetov. Na levi strani slike 4.1 je zabeležena tudi ta notacija, in sicer nam v obravnavanem primeru pove število lokomotiv, na katere je pripetih ivagonov, v posamezni porazdelitvi.

Primer: Zapis števila14 = 5+4+3+1+1lahko pretvorimo v zapis14 = 1·5+1·4+1·3+2·1 (y₁ = 2, y₃ =y₄ =y₅ = 1, y₂ = 0 in y_i = 0 zai≥6.)

4.3 Konjugirani pari

V razdelku 3.1 smo predstavili in definirali Youngove diagrame. Z opazovanjem teh diagramov zlahka opazimo, da lahko iz prikaza neke particije števila n dobimo prikaz še ene particije is- tega števila. To dobimo tako, da celoten diagram prevrnemo preko diagonale levo zgoraj-desno spodaj oziroma SZ-JV, kot je prikazano na sliki 4.2. S tem pretvarjanjem stolpcev v vrstice in vrstic v stolpce dobimo še en ustrezen diagram, ki ponazarja še eno porazdelitev števila n v obliki diagrama. V prejšnjem poglavju smo definirali Youngove diagrame. Trdimo, da je transformiran diagram ponovno Youngov diagram. Po definiciji 3.1 je število kvadratkov v prvi vrstici največje, v vsaki naslednji vrstici pa je vzdolž celotnega diagrama kvečjemu enako ali manj kvadratkov. Ker je Youngov diagram levo poravnan, velja tudi, da je v prvem stolpcu največ kvadratkov, v vsakem naslednjem pa kvečjemu enako ali manj. Ker pri transformaciji

(41)

Konjugirani pari 25 vrstice “prevrnemo” v stolpce, stolpce pa v vrstice, ponovno dobimo tak diagram, kot je defini- rano v 3.1. Paru takih dveh porazdelitev oziroma Youngovih diagramov rečemo konjugirani par porazdelitev .

Slika 4.2: Konjugiran par porazdelitev ponazorjen s Youngovima diagramoma

Obravnavajmo sedaj konjugirane pare za porazdelitveno število p(7) (na sliki 4.3 tudi ponazoritev z Youngovimi diagrami.)

Konjugirani pari so sledeči:

• 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1

• 6 + 1 = 2 + 1 + 1 + 1 + 1 + 1,

• 5 + 1 + 1 = 3 + 1 + 1 + 1 + 1,

• 5 + 2 = 2 + 2 + 1 + 1 + 1,

• 3 + 2 + 2 = 3 + 3 + 1,

• 4 + 2 + 1 = 3 + 2 + 1 + 1,

• 4 + 3 = 2 + 2 + 2 + 1.

Drugače pa je pri porazdelitvi 4 + 1 + 1 + 1, ki je konjugirana sama sebi (slika 4.3).

(42)

26 Porazdelitveno število p(n)

Slika 4.3: Konjugirani pari zap(7), prikazani z Youngovimi diagrami

4.4 Porazdelitvene identitete

S pomočjo snovi, obravnavane v prejšnjih razdelkih (predvsem 3.1 in 4.3), lahko dokažemo tudi nekaj trditev o porazdelitvenih številih, ki jih imenujemo porazdelitvene identitete. V večini primerov gre za identitete, ki povedo, da je število porazdelitev nekega posebnega tipa enako številu porazdelitev nekega drugega posebnega tipa.

(43)

Porazdelitvene identitete 27 Trditev 4.2. Naj bo p_min(n, k) oznaka za število porazdelitev naravnega števila n na najmanj k delov in p_vsaj(n, k) oznaka za število porazdelitev pozitivnega števila n na dele, pri katerih je vrednost največjega vsaj k. Tedaj za vse k ≤n velja p_min(n, k) =p_vsaj(n, k)

Dokaz. Dokaz te trditve oziroma odnosa med tema dvema vrstama porazdelitev lahko izvedemo s pomočjo Youngovih diagramov, natančneje s pomočjo konjugiranih parov (celice v vrsticah se transformirajo v celice v stolpcih). Očitno je namreč, da je konjugirani par porazdelitve števila n na najmanj k delov (ustrezni diagram bo torej vseboval vsaj k vrstic), porazdelitev števila n na dele, kjer ima največji vsaj k elementov (v prvi vrstici ustreznega diagrama je vsaj k elementov). Ker očitno velja tudi obrat, je s tem dokaz končan.

Primer. Veljap_min(6,4) = p_vsaj(6,4) = 4.

(3,1,1,1) ⇐⇒ (4,1,1) (2,2,1,1) ⇐⇒ (4,2) (2,1,1,1,1) ⇐⇒ (5,1)

(1,1,1,1,1,1) ⇐⇒ (6) Naslednja trditev je precej podobna prejšnji.

Trditev 4.3. Naj bo p_max(n, k) oznaka za število porazdelitev naravnega števila n na največ k delov inp_do(n, k)oznaka za število porazdelitev naravnega številan na dele, pri katerih vrednost največjega ne presega k. Tedaj za vse k ≤n velja pmax(n, k) = pdo(n, k).

Dokaz. S pomočjo Youngovega diagrama lahko dokažemo, da so si porazdelitve omenjenih dveh tipov paroma ravno konjugirani pari. Očitno je namreč, da je konjugirani par porazdelitve števila n na največ k delov (ustrezni diagram bo torej vseboval največ k vrstic), porazdelitev števila n na dele, pri katerih vrednost največjega ne presega k (v prvi vrstici ustreznega diagrama je največ k elementov). Ker očitno velja tudi obrat, je s tem dokaz končan.

Primer. Veljap_max(5,3) =p_do(5,3) = 5:

(5) ⇐⇒ (1,1,1,1,1) (4,1) ⇐⇒ (2,1,1,1)

(44)

28 Porazdelitveno število p(n)

(3,2) ⇐⇒ (2,2,1)

(3,1,1) ⇐⇒ (3,1,1)

(2,2,1) ⇐⇒ (3,2)

Trditev 4.4. Naj bo p2x(n) oznaka za število porazdelitev naravnega števila n na dele, kjer sta si največja dela enaka, in p_vsaj2(n) oznaka za število porazdelitev pozitivnega števila n na dele, velikosti vsaj 2. Tedaj za vse n velja p_2x(n) = p_vsaj2(n).

Dokaz. Tudi to trditev lahko dokažemo z Youngovimi diagrami, kajti konjugiran par porazdelitve števila n na dele, kjer sta si največja dela enaka (ustrezni diagram bo imel prvi dve vrstici enako dolgi), je ravno porazdelitev števila n na dele, velike vsaj 2 (ker sta prva dva stolpca enako dolga, sta v vsaki vrstici ustreznega diagrama vsaj dva elementa).

Primer. Veljap_2x(7) =p_vsaj2(7) = 4:

(3,3,1) ⇐⇒ (3,2,2) (2,2,2,1) ⇐⇒ (4,3) (2,2,1,1,1) ⇐⇒ (5,2) (1,1,1,1,1,1,1) ⇐⇒ (7)

Obstajo pa tudi konjugirani pari porazdelitev števil enega in drugega tipa, ki pa niso ravno očitni in jih je malce težje opaziti.

Trditev 4.5. Naj bodo števila a, b in c naravna števila, za katere velja a > b in a > c. Število porazdelitev števila a−c na b−1 delov, kjer noben del ne preseže velikosti c, je enako številu porazdelitev števila a−b na c−1 delov, kjer noben del ne preseže velikosti b.

Dokaz. Trditev lahko zopet dokažemo s pomočjo Youngovih diagramov. Na particiji enega od teh dveh tipov namreč lahko opravimo sledečo transformacijo: originalnemu diagramu na vrhu dodamo vrsticocoziromab. Na ta način dobimo neko particijo številaanabdelov, izmed katerih nobeden ne presega c (oziroma particija števila a na c delov, izmed katerih nobeden ne presega c). Nato izbrišemo prvi stolpec, ki je pred izbrisom dolžine b oziroma dolžine c.

Dobljeno nato konjugiramo (prikazano na sliki 4.4).

Opazimo, da ta kompozicijska transformacija porazdelitve enega tipa pretvori v porazdelitve drugega tipa in obratno. Precej očitno je tudi, da se po opravljenih obeh opisanih transforma- cijah vrnemo v prvotno stanje, kar pomeni, da sta si operaciji inverzni. S tem je izrek dokazan.

(45)

Porazdelitvene identitete 29

Slika 4.4: Grafična ponazoritev trditve 4.5

Primer. Denimo, da velja a = 21, b = 5, c = 7, in tako a−c= 14, a−b = 16, b−1 = 4 in c−1 = 6. V tem primeru bomo dobili 16 možnosti in sicer:

(7,5,1,1) ⇐⇒ (3,3,3,3,2,2) (7,4,2,1) ⇐⇒ (4,3,3,2,2,2) (7,3,3,1) ⇐⇒ (4,4,2,2,2,2) (7,3,2,2) ⇐⇒ (5,3,2,2,2,2) (6,6,1,1) ⇐⇒ (3,3,3,3,3,1) (6,5,2,1) ⇐⇒ (4,3,3,3,2,1) (6,4,3,1) ⇐⇒ (4,4,3,2,2,1) (6,4,2,2) ⇐⇒ (5,3,3,2,2,1) (6,3,3,2) ⇐⇒ (5,4,2,2,2,1) (5,5,3,1) ⇐⇒ (4,4,3,3,1,1) (5,5,2,2) ⇐⇒ (5,3,3,3,1,1) (5,4,4,1) ⇐⇒ (4,4,4,2,1,1)