Generuojančiosios funkcijos ir kombinatorinės struktūros

Trys juostos ar du pasirinkimai: ką skaičiuojate?

3 ilgio juostą galite užpildyti 1 ir 2 ilgio plytelėmis. Skaitant iš kairės į dešinę, galimi variantai yra (1,1,1), (1,2) ir (2,1): trys dengimo būdai. Jei vietoj to pasirenkate nesutvarkytą šių ilgių rinkinį, kurio bendra suma yra 3, yra tik du pasirinkimai: trys vienetai arba vienas vienetas ir vienas dvejetas. Antrojoje ir trečiojoje juostose naudojamas tas pats rinkinys, tačiau jo plytelės išdėstomos skirtinga tvarka.

Generuojančioji funkcija visus šiuos skaičius saugo viename indeksuotame įraše. Jos koeficientas prie 3 laipsnio bus 3, kai skaičiuojami dengimo būdai atsižvelgiant į plytelių tvarką, ir 2, kai skaičiuojami nesutvarkyti pasirinkimai. Prieš pasirinkdami formulę, apibrėžkite, kas yra vienas objektas, kaip matuojamas jo dydis ir kada du objektai laikomi skirtingais.

Pravartu mokėti sutraukti panašiuosius narius dauginant daugianarius, skaityti laipsnius ir taikyti taisyklę numeruotai sekai. Susietos paskelbtos pamokos suteikia šių algebros ir dėsningumų žinių pagrindą. Formaliosios eilutės, koeficientų išskyrimas, poros, kartotinumų vektoriai, skaidiniai ir rekurentiniai sąryšiai apibrėžiami čia; vėlesni skaičiavimo straipsniai nėra būtini.

Skaitydami pirmą kartą, sekite koeficientų pavyzdžius, dviejų daugiklių lentelę, sutvarkytų ir nesutvarkytų konstrukcijų palyginimą bei trijų vienetų ilgio juostos dengimo būdus. Prie formaliojo atvirkštinio elemento įrodymo ir begalinės skaidinių sandaugos grįžkite tada, kai galėsite paaiškinti, kodėl vieną pasirinktą koeficientą veikia tik baigtinis skaičius narių. Skaičiavimo formulėms nereikia nei ribų, nei analizinio konvergavimo.

Koeficiento vieta nurodo dydį

Kai n = 0,1,2,…, tegu aₙ žymi n dydžio objektų skaičių, o kiekvieno dydžio objektų yra baigtinis skaičius. Paprastoji generuojančioji funkcija yra A(x) = a₀+a₁x+a₂x²+⋯. „Paprastoji“ reiškia, kad koeficientas yra pats aₙ, be faktorialo vardiklyje. Eksponentinių generuojančiųjų funkcijų čia nenaudosime.

Žymuo [xⁿ]A(x) reiškia koeficientą aₙ. Kai A(x) = 1+2x², gauname [x⁰]A = 1, [x¹]A = 0 ir [x²]A = 2. Praleisto nario koeficientas lygus nuliui; tai nereiškia, kad galima pastumti vėlesnius indeksus. Jei šis reiškinys žymi baigtinį daugianarį, visi aukštesnių laipsnių koeficientai taip pat lygūs nuliui.

Nulinio laipsnio koeficientas nusako nulinio dydžio objektų skaičių. Klasės, kurioje yra tik vienas tuščias objektas, eilutė yra 1. Klasės, kurioje nėra jokio dydžio objektų, eilutė yra nulinė eilutė 0. Tai skirtingos klasės: vienoje yra nulinio dydžio objektas, o kitoje jo nėra.

Visoje šioje pamokoje dydžiai yra neneigiami sveikieji skaičiai. Objektų skaičiai taip pat yra neneigiami sveikieji skaičiai, tačiau formaliojoje algebroje galima naudoti ir koeficientus su ženklu: (1−x)(1+x) = 1−x². Koeficientas −1 yra naudingas algebroje, bet nėra objektų skaičius. Koeficientų sąrašas tampa skaičiavimo modeliu tik tada, kai apibrėžiami jo objektai ir jų dydžio nustatymo taisyklė.

Formalioji eilutė – seka, nepriskiriant x skaitinės reikšmės

Formalioji laipsninė eilutė su sveikaisiais koeficientais yra sveikųjų skaičių seka, užrašoma A(x) = Σₙ₌₀^∞ aₙxⁿ. Čia x yra pagalbinis apskaitos simbolis. Lygybė reiškia, kad sutampa visi atitinkami koeficientai. Sudedama pagal koeficientus: [xⁿ](A+B) = aₙ+bₙ. Daugybai taikysime toliau pateiktą baigtinę taisyklę. Išraiška, kuri atrodo begalinė, yra leistina tik tada, kai kiekvieną reikiamą koeficientą galima apskaičiuoti baigtiniu ir vienareikšmiškai apibrėžtu būdu.

Šis aiškinimas skiriasi nuo analizinės laipsninės eilutės aiškinimo: ten x yra skaičius, o skaitinė eilutė turi konverguoti, kad būtų galima gauti jos reikšmę. Formalioji tapatybė 1+x+x²+⋯ = 1/(1−x) neleidžia į kairiąją pusę įstatyti x = 1 ar x = 2 ir laikyti ją konverguojančia realiųjų skaičių suma. Analiziniu požiūriu geometrinė eilutė konverguoja, kai |x| < 1; formaliuoju požiūriu jokia tokia skaitinė x reikšmė nepasirenkama.

Rašome A(x) ≡ B(x) moduliu x^(N+1), kai jų koeficientai sutampa nuo 0 iki N laipsnio, kur N yra neneigiamas sveikasis skaičius. Tai teiginys apie baigtinę pradinę sekos dalį, o ne visiška lygybė. Diagramose horizontalioji koordinatė yra laipsnis n, o ne skaitinė x reikšmė. Septynių stulpelių vaizdas pats savaime negali įrodyti, kad tapatybė galioja kiekvienam laipsniui.

Daugyba pagal visas indeksų poras su ta pačia suma

Tegu A(x) = Σᵢ₌₀^∞ aᵢxⁱ ir B(x) = Σⱼ₌₀^∞ bⱼxʲ. Jų Koši sandaugos koeficientas yra cₙ = Σᵢ₌₀^n aᵢbₙ₋ᵢ. Tinklelyje kiekviena sandauga aᵢbⱼ priskiriama laipsniui i+j, nes xⁱxʲ = x^(i+j). Prie n laipsnio koeficiento gali prisidėti tiksliai n+1 indeksų porų: (0,n),(1,n−1),…,(n,0).

Taip daugyba apibrėžiama net tada, kai abi eilutės yra begalinės: vienam fiksuotam n skirta suma turi baigtinį sandaugų skaičių. Jos negali paveikti nei aukštesnio nei n laipsnio koeficientas, nei neigiamas indeksas. Baigtinių daugianarių atveju visus koeficientus po paskutinio nario laikykite nuliais.

Sandaugoje (1+2x)(1+x) pirmojo laipsnio nariai yra 1×1 ir 2×1, todėl c₁ = 3. Nulinio ir antrojo laipsnio narių koeficientai yra 1 ir 2. Sandauga yra 1+3x+2x². Sandaugoje (1−x)(1+x) du pirmojo laipsnio nariai panaikina vienas kitą, todėl gauname 1−x²; praleidę antrąjį tinklelio langelį, gautume neteisingą koeficientą.

Skaičiuodami pasirinkime sutvarkytą porą (a,b), sudarytą iš vieno A klasės objekto ir vieno B klasės objekto, ir priskirkime jai dydį size(a)+size(b). Kai bendras dydis yra n, pirmiausia išskirkime nesikertančius atvejus pagal size(a)=i. Tokiu atveju yra aᵢbₙ₋ᵢ porų. Kiekvienos poros pirmojo objekto dydis yra vienintelis, todėl sudėdami šių atvejų porų skaičius kiekvieną porą suskaičiuojame lygiai vieną kartą. Taip įrodoma sandaugos formulė, kai dydžiai sudedami; kitai dydžio nustatymo taisyklei reikia atskiro pagrindimo.

Baigtinis nukirtimas gali duoti tikslų atsakymą į baigtinį klausimą

Norėdami rasti koeficientus iki N laipsnio imtinai, kiekviename dauginamajame palikite koeficientus nuo 0 iki N laipsnio. Koši sandaugos naryje, kuriame i+j = n ≤ N, nei i, nei j neviršija N. Todėl pašalinus visus aukštesnio laipsnio narius, visi reikalingi koeficientai lieka nepakitę. Tas pats argumentas tinka baigtiniam dauginamųjų skaičiui, taikant indukciją pagal daugybos veiksmų skaičių.

Dauginant iš xᵏ, kai k yra sveikasis skaičius ir k ≥ 0, kiekvienas koeficientas pasislenka per k vietų į dešinę: [xⁿ](xᵏA) yra aₙ₋ₖ, kai n ≥ k, o kitais atvejais yra 0. Reiškinio x²(1+2x+x²) trečiojo laipsnio nario koeficientas yra 2. Palikite nulinius nulinio ir pirmojo laipsnio narių koeficientus, užuot pernumeravę rezultato indeksus.

Šios garantijos galioja tik tada, kai laipsnių rodikliai yra neneigiami. Jei būtų leidžiami neigiami laipsniai, atmestas aukšto teigiamo laipsnio narys galėtų būti padaugintas iš neigiamo laipsnio nario ir duoti norimo žemo laipsnio narį. Tokie Lorano eilučių klausimai nepatenka į šios pamokos apimtį. Taip pat nukirstos koeficientų lentelės negalima pateikti kaip viso daugianario, nebent visi tolesni koeficientai iš tiesų yra lygūs nuliui.

Sąrašams su tvarka naudojamos kartotinės sandaugos

Tarkime, turimų elementų tipų svoriai yra teigiami sveikieji skaičiai. Kiekvieno svorio tipų yra baigtinis skaičius; aⱼ žymėkime tipų, kurių svoris j, skaičių. Tuomet eilutėje A(x) = Σⱼ₌₁^∞ aⱼxʲ turime a₀ = 0. Sąraše išsaugoma, kokio tipo yra pirmasis, antrasis ir kiekvienas tolesnis elementas. Jo svoris yra jų svorių suma. Skirtingi tipai lieka skirtingi, net jei jų svoris vienodas.

Sąrašų, turinčių lygiai k elementų, eilutė yra A(x)^k pagal pakartotinai taikomą sutvarkytų porų sandaugos taisyklę. Tuščio sąrašo svoris lygus nuliui, o jo indėlis yra A(x)^0 = 1. Todėl visų baigtinių sąrašų eilutė yra L(x) = 1+A+A²+⋯. Norimam laipsniui n sąrašas gali turėti ne daugiau kaip n elementų, nes kiekvieno elemento svoris yra bent 1. Prisidėti gali tik k ≤ n, o kiekvieno svorio iki n tipų yra baigtinis skaičius, todėl šis koeficientas yra baigtinis sąrašų skaičius.

Patikrinkite Koši sandaugą po vieną koeficientą: (1−A)(1+A+A²+⋯) = 1. Kiekvienam fiksuotam laipsniui nariai panaikina vienas kitą tarp baigtinio skaičiaus reikšmingų laipsnių; jokia skaitinė riba čia nenaudojama. Taigi L(x) = 1/(1−A(x)), kur trupmena reiškia vienintelį formalųjį 1−A atvirkštinį elementą daugybos atžvilgiu. Jo pastovusis koeficientas yra 1, todėl sveikuosius koeficientus galima rasti paeiliui: l₀ = 1 ir lₙ = Σⱼ₌₁^n aⱼlₙ₋ⱼ, kai n ≥ 1.

Sąlyga a₀ = 0 yra svarbi. Jei vieno tipo elementus būtų galima kartoti ir jų svoris būtų lygus nuliui, iš jų sudaryti kiek norima ilgi sąrašai visi turėtų nulinį svorį, taigi gautume be galo daug nulinio dydžio objektų. Geometrinė sąrašų konstrukcija tam laipsniui neapibrėžtų baigtinio koeficiento. Neteigiame, kad kiekviena eilutė su nenuliniu pastoviuoju nariu neturi atvirkštinio elemento; būtent šios neriboto ilgio sąrašų sumos skaičiavimo interpretacijai reikia teigiamų svorių.

Kai yra vienas tipas, kurio svoris 1, ir vienas tipas, kurio svoris 2, A = x+x². Tuomet L = 1/(1−x−x²), o šios eilutės trečiojo laipsnio nario koeficientas yra 3. Kai yra du skirtingi tipai, kurių svoris 1, ir vienas tipas, kurio svoris 2, A = 2x+x². Trečiąjį laipsnį atitinka aštuoni sąrašai iš trijų vienetinio svorio elementų; dar keturiuose yra vienas vienetinio svorio elementas ir elementas, kurio svoris du. Iš viso yra 12.

Multiaibėje pasirenkamas kiekvieno tipo kartotinumas

Pasirenkant multiaibę, kiekvienam galimam įvardytam tipui j nurodomas neneigiamas sveikasis kartotinumas kⱼ. Tvarka nefiksuojama. Jei tipų sąrašas baigtinis, o jų svoriai w₁,…,wᵣ teigiami, bendras svoris yra Σⱼ₌₁^r wⱼkⱼ. Vektorius (k₁,…,kᵣ) visiškai apibrėžia objektą. Kai tipų sąrašas tuščias, yra vienas tuščias vektorius, kurio bendras svoris lygus nuliui.

Vieno tipo, kurio svoris w ≥ 1, leistini kartotinumai 0,1,2,… duoda eilutę 1+xʷ+x^(2w)+⋯ = 1/(1−xʷ). Skirtingų tipų pasirinkimai derinami sudedant svorius, todėl multiaibių eilutė yra M(x) = ∏ⱼ₌₁^r 1/(1−x^(wⱼ)). Kiekvienas koeficientas yra baigtinis, nes, kai bendras svoris yra n, kiekvienam kⱼ galioja kⱼ ≤ n/wⱼ. Kiekvienas vektorius pasirenkamas vieną kartą; sukeitus pasirinktų elementų tvarką, kitas vektorius neatsiranda.

Kai svoriai yra 1 ir 2, M = 1/((1−x)(1−x²)). Norint gauti bendrą svorį 3, reikia išspręsti k₁+2k₂ = 3: sprendiniai yra (3,0) ir (1,1). Koeficientas yra 2, o sutvarkytų sąrašų koeficientas – 3. Šis skirtumas paaiškina du nesutvarkytus pasirinkimus įvadiniame pavyzdyje.

Jei dviejų įvardytų tipų svoris yra 1, palikite du atskirus daugiklius (1−x)⁻¹. Pridėjus vieną tipą, kurio svoris du, bendras svoris 3 gaunamas, kai k₀+k₁+2k₂ = 3. Kai k₂ = 0, yra keturios poros (k₀,k₁); kai k₂ = 1, yra dvi. Koeficientas yra 6, taigi jis vis tiek skiriasi nuo sutvarkytų sąrašų skaičiaus 12. Jei tie du tipai būtų fiziškai neatskiriami, juos sujungus pasikeistų klasė ir jos formulė.

Sumos sudarymo monetomis uždavinyje paprastai neatsižvelgiama į monetų tvarką, todėl tinka po vieną daugiklį kiekvienam nominalui. Sutvarkytas monetų nominalų sąrašas yra kitoks uždavinys, kuriam taikoma sąrašų formulė. Kai nominalai yra 2 ir 3, o norima suma yra 5, po vieną kiekvieno nominalo monetą sudaro vieną multiaibę, bet du sutvarkytus sąrašus: (2,3) ir (3,2). Nurodykite susitarimą, užuot sprendę apie jį iš žodžio „grąža“.

Sveikųjų skaičių skaidiniuose kiekvienam dėmens dydžiui skiriamas vienas tipas

Sveikojo skaičiaus n ≥ 0 skaidinys yra nesutvarkytas teigiamų sveikųjų skaičių rinkinys, kurių suma lygi n. Lygiavertiškai tai yra nedidėjantis teigiamų dėmenų sąrašas arba kartotinumų vektorius: mⱼ nurodo, kiek dėmenų lygu j. Tuščiasis skaidinys yra vienintelis skaičiaus 0 skaidinys. Kai n > 0, galimi tik dėmenų dydžiai j ≤ n.

Kai didžiausias leistinas dėmens dydis yra k ≥ 1, generuojančioji eilutė yra Pₖ(x) = ∏ⱼ₌₁^k 1/(1−xʲ). Jos n-ojo laipsnio koeficientas nurodo lygties m₁+2m₂+⋯+kmₖ = n neneigiamų sprendinių skaičių. Tai būtent multiaibės konstravimas, kai kiekvienam leistinam dėmens dydžiui skiriamas vienas tipas. Kai nėra leistinų dėmenų, apibrėžkite P₀ = 1, taigi nulinio laipsnio koeficientas yra 1, o kiekvieno teigiamo laipsnio – 0.

Kai k = 3 ir n = 4, keturi skaidiniai yra 3+1, 2+2, 2+1+1 ir 1+1+1+1. Skaidinys 4 neįtraukiamas, nes jo dėmuo didesnis už 3. Taigi [x⁴]P₃ = 4, o skaidinių be apribojimų skaičius p(4) yra 5.

Formalioji eilutė be apribojimų yra P(x) = ∏ⱼ₌₁^∞ 1/(1−xʲ). Ši begalinė sandauga apibrėžiama kiekvienam koeficientui atskirai: iki N-ojo laipsnio imtinai kiekvienas daugiklis, kurio j > N, prisideda tik savo pastoviuoju nariu 1. Todėl P ir baigtinės sandaugos P_N koeficientai sutampa iki N-ojo laipsnio imtinai. Visi koeficientai yra baigtiniai, ir nereikia jokio teiginio apie analizinį konvergavimą. Nulinio dydžio dėmuo sugriautų šį samprotavimą; čia skaidinių dėmenys yra griežtai teigiami.

Pašalinus pirmąją plytelę gaunamas rekurentinis sąryšis

Tegu tₙ yra būdų iškloti juostą, kurios ilgis yra sveikasis skaičius n ≥ 0, naudojant 1 ir 2 ilgio plyteles ir išlaikant jų tvarką iš kairės į dešinę, skaičius. Yra vienas tuščias išklojimas, todėl t₀ = 1. Juostą, kurios ilgis 1, galima iškloti tik viena vienetinio ilgio plytele, todėl t₁ = 1. Kai n ≥ 2, suskirstykime išklojimus pagal pirmąją plytelę. Pašalinus pirmąją 1 ilgio plytelę, lieka n−1 ilgio juostos išklojimas, o pašalinus 2 ilgio plytelę, lieka n−2 ilgio juostos išklojimas.

Šie du atvejai nesikerta, o pašalinimo veiksmas yra grįžtamasis: pridėjus pašalintą plytelę pradžioje, atkuriamas tiksliai vienas pradinis išklojimas. Todėl tₙ = tₙ₋₁+tₙ₋₂, kai n ≥ 2. Pirmieji koeficientai yra 1,1,2,3,5,8,13. Tuščias išklojimas būtinas tiek vienos dvejetinio ilgio plytelės atvejui, kai n = 2, tiek eilutės laisvajam nariui.

Tegu T(x) = Σₙ₌₀^∞ tₙxⁿ. Tuomet T−1−x = x(T−1)+x²T, nes kiekviena suma su pastumtais indeksais prasideda nuo tinkamo pradinio indekso. Pertvarkę gauname (1−x−x²)T = 1, taigi T = 1/(1−x−x²). Tai sutampa su rezultatu, gaunamu taikant sutvarkytųjų sąrašų konstrukciją elementų eilutei x+x².

Pasirinkus F₀ = 0, F₁ = 1 ir Fₙ = Fₙ₋₁+Fₙ₋₂, kai n ≥ 2, šių išklojimų skaičiai yra tₙ = Fₙ₊₁. O Fibonačio eilutės Σₙ₌₀^∞ Fₙxⁿ skaitiklis yra x: x/(1−x−x²). Atsižvelgdami į pradinius narius išvengiame indekso poslinkio per vienetą klaidos. Paveiksle parodyti visi aštuoni penkių vienetų ilgio juostos išklojimai, tačiau argumentas, grindžiamas pirmąja plytele, įrodo rekurentinę priklausomybę kiekvienam n ≥ 2.

Prieš imdamiesi algebros, patikrinkite objektus

Naudokite sumą nesikertančioms alternatyvoms, sandaugą sutvarkytam kortežui, kurio elementų dydžiai sudedami, geometrinę sąrašo formulę bet kokio ilgio sutvarkytiems teigiamo svorio elementų sąrašams ir po vieną kartotinumo daugiklį kiekvienam tipui, kai pasirenkama nepaisant tvarkos. Skaidinių sandauga yra specialus multiaibės modelis, kuriame kiekvieną teigiamą sveikąjį dydį atitinka vienas tipas. Šie aprašymai paaiškina formules, o ne leidžia simbolius vartoti pakaitomis.

Norėdami rasti reikiamą koeficientą, pirmiausia užrašykite objekto ir jo dydžio apibrėžimus. Patikrinkite tuščią objektą, kartojamų elementų svorių teigiamumą ir baigtinumą ties kiekvienu laipsniu. Tada pasirinkite konstrukciją, palikite pakankamai narių ir palyginkite nedidelį rankiniu būdu suskaičiuotą atvejį su apskaičiuotu koeficientu. Skaitinis sutapimas naudingas klaidoms tikrinti, tačiau formulę bendruoju atveju pagrindžia grįžtamasis skaičiavimo argumentas.

Tyrinėjimo įrankis naudoja tikslius nedidelių sveikųjų skaičių duomenis iki 6 laipsnio; ten, kur nurodyta, rodomas kiekvienas pasirinktas sąsūkos narys ir kiekvienas trumpas sąrašas ar kartotinumų vektorius. Baigtinė įvestis ir išvardijimo ribos padeda išlaikyti sąveiką aiškią. Jos neriboja formaliųjų eilučių matematikos, o rodoma pradinė dalis neįrodo visos begalinės tapatybės.

Išnagrinėti pavyzdžiai

Pabandykite patys

1. Klasėje yra vienas tuščias objektas ir nėra teigiamo dydžio objektų. Ar jos eilutė yra 0, ar 1? Kuo skiriasi klasė, kurioje nėra jokių objektų?

   Rodyti atsakymą ir paaiškinimą

   Jos eilutė yra 1. Klasės, kurioje nėra jokių objektų, eilutė yra 0.

   Laisvojo nario koeficientas nurodo nulinio dydžio objektų skaičių. Vienas tuščias objektas prideda vienetą, o tuščia klasė – nulį. Tai, kad nėra teigiamo dydžio objektų, nenulemia laisvojo nario koeficiento.

2. Raskite [x²](1−2x+x²)(1+x). Ar kiekvieną šių dauginamųjų koeficientą galima interpretuoti kaip objektų skaičių?

   Rodyti atsakymą ir paaiškinimą

   Antrojo laipsnio nario koeficientas yra −1. Ne: neigiami koeficientai yra algebrinės vertės, o ne objektų skaičiai.

   Antrojo laipsnio įstrižainėje esančios sandaugos yra 1×0, (−2)×1 ir 1×1. Jų suma yra −1. Formalus dauginimas tinka sveikiesiems koeficientams net tada, kai tiesioginė skaičiavimo interpretacija negalima.

3. Raskite x³(2+x+4x²+⋯) eilutės 2 ir 4 laipsnio narių koeficientus. Ar kuris nors neparodytas aukštesnio nei antrojo laipsnio vidinės eilutės narys galėtų juos pakeisti?

   Rodyti atsakymą ir paaiškinimą

   Jie yra 0 ir 1. Vėlesni vidinės eilutės nariai negali pakeisti nė vieno iš šių koeficientų.

   Dėl poslinkio visų žemesnio nei trečiojo laipsnio narių koeficientai yra lygūs nuliui, o ketvirtojo laipsnio nario koeficientas paimamas iš vidinės eilutės pirmojo laipsnio nario. Kai laipsnių rodikliai neneigiami, aukštesnio laipsnio vidinis narys pasislenka į dar aukštesnį bendrą laipsnį; jis negali grįžti į šiuos ieškomus laipsnius.

4. Naudodami vieną 2 svorio elementų tipą ir vieną 3 svorio elementų tipą, palyginkite sutvarkytų sąrašų ir rinkinių, kuriuose tvarka nesvarbi, koeficientus prie 5 laipsnio narių. Užrašykite abi eilutes.

   Rodyti atsakymą ir paaiškinimą

   Sutvarkytų sąrašų atveju gauname 2, o eilutė yra 1/(1−x²−x³). Multiaibių atveju gauname 1, o eilutė yra 1/((1−x²)(1−x³)).

   Sutvarkyti sąrašai yra (2,3) ir (3,2). Vienintelis kartotinumo vektorius yra (1,1). Abi konstrukcijos leidžia tuščią nulinio svorio objektą, o teigiami elementų svoriai užtikrina, kad kiekvienas ieškomas koeficientas yra baigtinis.

5. Kodėl vieno neribotai kartojamo nulinio svorio elementų tipo negalima įtraukti į neriboto ilgio sąrašų skaičiavimo formulę taip, tarsi tai būtų įprastas teigiamo svorio elementų tipas?

   Rodyti atsakymą ir paaiškinimą

   Būtų be galo daug sutvarkytų sąrašų, kurių bendras svoris lygus nuliui: po vieną kiekvienam ilgiui. Todėl pastovusis koeficientas nebūtų baigtinis objektų skaičius.

   Teigiamų svorių atveju įrodyme elementų skaičių ribojo siekiamas svoris. Nulinio svorio elementas šią ribą panaikina. Šis prieštaravimas susijęs su sąrašų konstrukcija; juo neteigiama, kad kiekviena eilutė su nenuliniu pastoviuoju nariu neturi formaliosios atvirkštinės eilutės.

6. Jei nėra jokių galimų elementų tipų, kiek sutvarkytų sąrašų ir kartotinumo vektorių turi nulinį svorį? Kiek jų turi svorį 4?

   Rodyti atsakymą ir paaiškinimą

   Kiekviena konstrukcija turi vieną tuščią nulinio svorio objektą ir nė vieno 4 svorio objekto. Abi eilutės yra 1.

   Tuščia seka ir tuščias vektorius yra vienareikšmiškai apibrėžti pavieniai objektai. Be elementų neįmanoma gauti teigiamo bendro svorio. Tai skiriasi nuo nulinės eilutės, kurios objektų klasėje nėra net nulinio dydžio objektų.

7. Išvardykite skaičiaus 5 skaidinius, kurių dėmenys neviršija 2, ir užrašykite jų generuojančiąją eilutę.

   Rodyti atsakymą ir paaiškinimą

   Jie yra 2+2+1, 2+1+1+1 ir 1+1+1+1+1. Jų eilutė yra 1/((1−x)(1−x²)), taigi koeficientas prie penktojo laipsnio nario yra 3.

   Spręsdami m₁+2m₂ = 5, gauname m₂ = 0,1,2 ir atitinkamai nustatome m₁ reikšmes 5,3,1. Skirtinga tų pačių dėmenų tvarka nesukuria naujų skaidinių.

8. Kodėl skaidinių dalių daugikliai 1/(1−xʲ), kai j > 6, neturi įtakos p(6)? Ar pradinių narių fragmentas įrodo analizinę konvergenciją, kai x = 1?

   Rodyti atsakymą ir paaiškinimą

   Jų pirmųjų nepastoviųjų narių laipsniai yra didesni už 6, todėl iki šio laipsnio jie veikia kaip 1. Iš to neišplaukia analizinė konvergencija, kai x = 1.

   Sandaugose naudojami tik neneigiami laipsniai. Dėmens, kuriame yra vienas iš šių nepastoviųjų narių, laipsnis jau viršija tikslinį laipsnį, net jei kiti pasirinkti nariai yra pastovieji. Taip formalusis koeficientas apibrėžiamas baigtine suma; begalinės eilutės skaitinė vertė neapskaičiuojama.

9. Kokios yra t₀, t₁ ir t₄ vertės, kai juosta klojama vieno ir dviejų ilgio plytelėmis? Jei F₀ = 0 ir F₁ = 1, ar t₄ = F₄, ar t₄ = F₅?

   Rodyti atsakymą ir paaiškinimą

   t₀ = 1, t₁ = 1 ir t₄ = 5. Teisingas sąryšis yra t₄ = F₅, o bendruoju atveju tₙ = Fₙ₊₁.

   Tuščia juosta turi vieną klojimo būdą. Rekurentinis sąryšis klojimo būdų skaičiui duoda 1,1,2,3,5, o Fibonačio seka prasideda 0,1,1,2,3,5. Jų formaliųjų eilučių vardikliai vienodi, tačiau skaitikliai yra atitinkamai 1 ir x.

10. Paaiškinkite, kodėl (1−x)(1+x+x²+⋯) = 1 galioja formaliai, tačiau įstačius x = 2 kairėje negaunama konverguojanti realiųjų skaičių suma.

    Rodyti atsakymą ir paaiškinimą

    Prie kiekvieno teigiamo laipsnio du formalieji dėmenys panaikina vienas kitą, o pastovusis koeficientas yra 1. Kai x = 2, skaitiniai nariai 1,2,4,… net neartėja prie nulio.

    Formaliai dauginant kiekvienas koeficientas tikrinamas atskirai, ir jam apskaičiuoti reikia tik baigtinio skaičiaus veiksmų. Skaitinė konvergencija yra kitas reikalavimas; analizinė geometrinės eilutės formulė galioja, kai |x| < 1, bet ne šiai įstatytai vertei.

Ką verta įsidėmėti

• Įprastieji koeficientai fiksuoja dydžius, pradedant nuliniu laipsniu. Trūkstamo nario koeficientas yra nulis; tuščiam objektui skirta eilutė 1 skiriasi nuo nulinės eilutės.
• Formaliosios eilutės yra koeficientų sekos. Lygybė prie kiekvieno laipsnio yra stipresnė už pateiktą pradinių narių fragmentą, o formaliosios tapatybės savaime neleidžia įstatyti skaitinių verčių.
• Koši sandaugos n-asis koeficientas yra visų aᵢbₙ₋ᵢ suma, kai i = 0,…,n. Dėl neneigiamų laipsnio rodiklių eilutės nukirpimas ties tiksliniu laipsniu išlaiko tikslų rezultatą.
• Sutvarkyti sąrašai iš teigiamo svorio elementų duoda 1/(1−A), kai A₀ = 0. Multiaibėms vietoj to naudojama po vieną atvirkštinį daugiklį kiekvienam įvardytam tipui.
• Skaidinius į teigiamas dalis aprašo begalinė sandauga, baigtinė kiekvieno koeficiento atžvilgiu. Denginių vieno ir dviejų vienetų ilgio plytelėmis pradinės reikšmės yra 1,1, o eilutė – 1/(1−x−x²).