Viisnurkarvude teoreem

Vali arv n ja leht loetleb kõik viisid selle esitamiseks erinevate positiivsete täisarvude summana. Need punktidiagrammid on Franklini käiguga paari pandud: paarisarvu osadega diagramm kõrvuti paarituarvulisega. Üle jääb kõige enam üks ja sedagi vaid juhul, kui n on viisnurkarv. Allpool on korrutis (1 − x)(1 − x²)… sulgude kaupa lahti korrutatud ja selle kordajad räägivad sama loo.

Näidisarvutus — Viisnurkarvude teoreem

Paarisarv osi	7
Paaritu arv osi	8
Paaris miinus paaritu	−1
p(12), Euleri seosega	77
p(100)	190 569 292

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Viisnurkarvude teoreem

Euleri viisnurkarvude teoreem: (1 − x)(1 − x²)(1 − x³)… = 1 − x − x² + x⁵ + x⁷ − x¹² − x¹⁵ + …, summa üle iga positiivse, negatiivse või nulliga võrduva täisarvu k, kujul (−1)ᵏ x^(k(3k − 1)/2). Astendajad on üldistatud viisnurkarvud ja iga kordaja on 0, +1 või −1.

Mida iga sümbol tähendab

p(n): arvu n lahutuste arv: viisid kirjutada see positiivsete täisarvude summana, kus järjekord pole oluline
D₊(n), D₋(n): arvu n lahutused erinevateks osadeks, millel on vastavalt paaris ja paaritu arv osi
k(3k ∓ 1)/2: üldistatud viisnurkarvud 1, 2, 5, 7, 12, 15, 22, 26, …

Kust valem tuleb

Miks on iga kordaja paaris- ja paarituarvuliste valikute vahe. Avaldise (1 − x)(1 − x²)(1 − x³)… lahtikorrutamisel valime igast sulust kas 1 või −xᵏ. Valides mingitest sulgudest −xᵏ, saame x-i, mille astendaja on nende k-de summa. Iga niisugune valik annab kaasa ühe miinusmärgi. Nii lisandub xⁿ kordajale +1 iga võimaluse eest kirjutada n erinevate positiivsete täisarvude summana, kus on paarisarv liidetavaid. Paaritu arvu liidetavate korral lisandub −1. Teoreem väidabki, et see vahe on alati null. Erandiks on viisnurkarvud, kus see on (−1)ᵏ.
Miks Franklini käik need paari paneb. Olgu erinevate pikkustega ridadest koosnevas diagrammis s vähim osa ja g kallak: mitu rida ülevalt lugedes allapoole minnes täpselt ühe võrra lühenevad. Kui s ≤ g, võta alumine rida ja lisa igale s ülemisele reale lõppu üks punkt. Kui s > g, võta iga g ülemise rea lõpust üks punkt ja tee neist uus g pikkusega alumine rida. Mõlemal juhul jäävad read erinevaks, kogusumma n ei muutu ja ridade arv muutub ühe võrra. Paaris ja paaritu vahetavad kohad ning käigu uuesti tegemine tühistab algse käigu. See on blokeeritud vaid siis, kui alumine rida ja kallak jagavad punkti ning s = g või s = g + 1. Need diagrammid on k + (k + 1) + … + (2k − 1) ning (k + 1) + … + 2k, mille summad on k(3k − 1)/2 ja k(3k + 1)/2.
Teoreemist p(n) juurde. Iga n lahutust, kus kordused on lubatud, loendab Σ p(n) xⁿ = 1/((1 − x)(1 − x²)(1 − x³)…). Korruta mõlemad pooled korrutisega, mis on viisnurkarvude rida: (1 − x − x² + x⁵ + x⁷ − x¹² − …) × Σ p(n) xⁿ = 1. Kui n ≥ 1, on xⁿ kordaja paremal poolel 0, seega p(n) − p(n − 1) − p(n − 2) + p(n − 5) + p(n − 7) − … = 0. See ongi Euleri rekurrentseos ja selle liikmete arv kasvab vaid ligikaudu nagu √n.

Kakssada sulgu ning esimesest 201 kordajast säilib vaid 23 🖖

Korruta lahti (1 − x)(1 − x²) ja saad 1 − x − x² + x³. Jätka tulpdiagrammi all oleva liuguriga ühe sulu kaupa: kordajad kasvavad, jõudes poolel teel väärtuseni 31, ja siis taanduvad. 200 sulu järel pole esimesest 201 kordajast nullid vaid 23. Neist igaüks on +1 või −1 ja nad asuvad kohtadel 0, 1, 2, 5, 7, 12, 15, 22, 26, … Need on viisnurkarvud k(3k − 1)/2 ja k(3k + 1)/2 ning Euler leidis selle mustri just korrutist lahti korrutades.

Vastavus tõestab seda: arvu 12 juures jääb üle täpselt üks lahutus 🖖

Vajuta n = 9. Kaheksa viisi kirjutada 9 erinevate positiivsete täisarvude summana jagunevad nii, et neljal on paarisarv osi ja neljal paaritu arv. Franklini käik paneb iga paarisarvulise paari paarituarvulisega. Vajuta n = 12: 7 paaris vastu 8 paaritut, ning ühel lahutusel pole paarilist. See on 5 + 4 + 3, mille summa 12 on viisnurkarv. Klõpsa seda ja leht näitab, miks käik on seal blokeeritud. x¹² kordaja on paaris miinus paaritu, ehk −1, ja vastavusse seadmine ongi kogu tõestus. Sylvester'i üliõpilane Franklin Johns Hopkinsist avaldas selle 1881. aastal.

p(1000) nõuab 50 otsingut 🖖

Pööra teoreem ümber ja see loendab lahutusi p(n), mis on kordusi lubavad suvalises järjekorras summad. Euleri rekurrentseos kasutab vaid varasemaid väärtusi, mis asuvad viisnurkarvude kaugusel: p(12) = p(11) + p(10) − p(7) − p(5) + p(0) = 77. Arvu p(1000) puhul, mis on 32 numbrit pikk, teeb see 50 liiget. Terve tabeli p(1) kuni p(1000) arvutamine nõuab 33 475 otsingut, võrreldes 500 500 liitmisega tavalisel viisil. Vajuta p(200) ja saad 3 972 999 029 388, mis on MacMahoni tabeli viimane kirje Hardy ja Ramanujani jaoks. Nende kuulsa valemi esimene liige on n = 1000 juures endiselt 1,42% üle.

Ülesanne täielikult lahendatud

Euleri „erakordne seadus“: jagajate summad samadest märkidest 4 sammu
Märgid, mis ehitavad p(n), loovad ka arvu n jagajate summa. Euler nimetas seda ülimalt erakordseks seaduseks. Kasuta seda σ(12) ehk arvu 12 jagajate summa leidmiseks. Rekurrentseoses on üks muudatus: kohas, kus muidu oleks vaja σ(0), kasuta arvu n ennast.

Ava see ülesanne tööriistas
1. Lehe rekurrentseos p(12) jaoks, mida mustrina kopeerida:
  
  $p (12) = p (11) + p (10) - p (7) - p (5) + p (0) = 56 + 42 - 15 - 7 + 1 = 77$
2. Samad nihked ja märgid σ(12) jaoks. Viimane nihe on 12 ise, seega σ(0) muutub arvuks 12:
  
  $σ (12) = σ (11) + σ (10) - σ (7) - σ (5) + σ (0) \to 12$
3. Võttes σ(11) = 12, σ(10) = 18, σ(7) = 8 ja σ(5) = 6:
  
  $σ (12) = 12 + 18 - 8 - 6 + 12 = 28$
4. Kontrolli, liites jagajad otse:
  
  $1 + 2 + 3 + 4 + 6 + 12 = 28$
Vastus

σ(12) = 28. Euler pani selle kirja 1747. aastal ja see kehtib iga n korral. Lehe enda aritmeetika kontrollib seda kuni n = 500.

$σ (12) = 28; σ (n) = \sum_{k} (- 1)^{k + 1} σ (n - \frac{k ( 3 k \mp 1 )}{2}), σ (0) \to n$

Õpitee

Tõestusmeetodid

Allikad (3)

Franklin's involution as stated on this page (compare the smallest part with the slope; move one onto the other; blocked only at the pentagonal diagrams), with Franklin's 1881 paper and his place as Sylvester's student at Johns Hopkins: I. Pak, "Partition bijections, a survey", The Ramanujan Journal 12, 5–75 (2006); preprint, §5.2.
Euler's paper on the sum of divisors, where the pentagonal signs that give p(n) give σ(n) too, the worked problem: L. Euler, "Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs", Bibliothèque impartiale 3, 10–31 (written 1747, published 1751); Eneström number E175, The Euler Archive.
The partition numbers, Euler's recurrence over the generalised pentagonal numbers, Hardy and Ramanujan's asymptotic formula, and MacMahon's table of p(n) up to 200: OEIS Foundation, "A000041: a(n) = number of partitions of n" and "A001318: Generalized pentagonal numbers", The On-Line Encyclopedia of Integer Sequences.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.