Generuojančios funkcijos

Generuojančios funkcijos

Kombinatorinių uždavinių, kuriuose reikia apskaičiuoti skaičių objektų, tenkinančių nurodytas s¹lygas, sprendinys dažnai būna seka , čia – ieškomų k “matavimų” objektų skaičius. Pavyzdžiui, jei ieškome skaičiaus n išskaidymo, tai yra skaičiaus n išskaidymo į k dėmenis variantų skaičius; jei nagrinėjame n-elementės aibės išskaidym¹ į poaibius, tai ir t.t. Šiais atvejais sekai patogu priskirti formali¹ eilutź

(3.6.1)

kuri vadinama ši¹ sek¹ generuojančia funkcija.

Pavadinimas “formalioji eilutė” reiškia, kad (3.6.1) eilutź traktuosime kaip sekos patogų užraš¹. Šiuo atveju nesvarbu, prie kokių x reikšmių ši eilutė konverguoja. Todėl mes niekada neskaičiuosime tos eilutės sumos prie konkrečios x reikšmės. Su šiomis eilutėmis mes vykdysime konkrečias operacijas ir palyginsime koeficientus prie tų pačių x laipsnių. Tarkime, turime dvi eilutes:

ir

Apibrėšime šių eilučių sum¹.

Apibrėšime sandaugos iš pastovaus skaičiaus operacij¹.

Apibrėšime šių eilučių sandaug¹.

čia

Jei , kai , tai (3.6.1) eilutź sutapatinsime su daugianariu:

Aptarsime, kaip laipsninė eilutė dalijama iš kitos laipsninės eilutės. Padalinź eilutź iš , gausime eilutź . Tada pagal dalybos veiksmo apibrėžim¹ galima parašyti

(3.6.2)

(3.6.2) formulėje palyginź koeficientus prie tų pačių x laipsnių, gausime:

(3.6.3)

Tos lygybės sudaro begalinź lygčių sistem¹, iš kurios reikia rasti koeficientus ir t.t. Iš (3.6.3) nesunku apskaičiuoti koeficientus c:

(3.6.4)

Iš matematinės analizės žinome, kad, jei eilutė kažkurioje nulio aplinkoje konverguoja, tai (3.6.1) eilutė yra funkcijos Makloreno eilutė. Šiuo atveju generuojanti funkcija yra matematinės funkcijos Makloreno eilutė. Todėl, šiuo atveju, atliekant operacijas, vietoje eilutės galima imti analitinź funkcij¹ .

Pavyzdžiui, galime rašyti:

(3.6.5)

ir t.t.

Apskaičiuokime kai kurių sekų generuojančias funkcijas.

Imkime sek¹ , čia , kai , yra lygus 0. Šios sekos generuojanti funkcija yra Niutono binomas, t.y.

(3.6.6)

Panagrinėkime (3.6.6) formulės fizinź prasmź. Kiekvien¹ daugiklį galima traktuoti kaip aibės atitikmenį, kuris nusako elemento pasirodymo skaičių X poaibyje: 0 kartų (dėmuo ) ir vien¹ kart¹ (dėmuo ). Aišku, kad kiekvienas aibės X poaibis vienareikšmiškai apibrėžiamas, nurodant, kiek kartų kiekvienas elementas pasirodo poaibyje, t.y. iš kiekvieno daugiklio išrenkant po vien¹ dėmenį. Vadinasi, šios sandaugos koeficientas prie x k-tojo laipsnio ir parodo aibės X k-elemenčių poaibių skaičių.

Aišku, kad šį nagrinėjim¹ galima apibendrinti nagrinėjant aibes su pasikartojančiais elementais. Pavyzdžiui, imsime aibź , ir simboliu pažymėsime šios aibės k-elemenčių poaibių skaičių. Apibendrinus aukščiau pateiktus samprotavimus, sekos generuojanti funkcija yra

Iš šios funkcijos matosi, kad skaičius poaibių, turinčių 5-is elementus, yra 22.

Nesunku suvokti, kad, atitinkamai parinkus i-¹jį daugiklį, galima įvesti įvairius apribojimus elementui a_i. Pavyzdžiui, jei šis daugiklis yra , tai reiškia, kad poaibyje elementas a_i gali pasirodyti 0, 3, arba 7 kartus; jei daugiklis yra , tai reiškia, kad elementas a_i poaibyje gali pasirodyti lyginį skaičių kartų.

Jei mes neįvedame jokio apribojimo elemento a_i, , pasirodymo skaičiui, tai generuojanti funkcija yra

Aišku, kad aukščiau pateiktiems pavyzdžiams galima suteikti ir kitoki¹ interpretacij¹. Pavyzdžiui, nagrinėkime lygtį

čia e₁, e₂, ir r – natūralieji skaičiai. Skaičiams e₁ ir e₂ gali būti įvesti apribojimai. Mus domina šios lygties sprendinių skaičius. Tarkime, e₁ gali būti arba 0, arba 1, arba 9, o e₂ tenkina nelygybź . Simboliu pažymėkime šios lygties sprendinių skaičių. Tada šios sekos generuojanti funkcija yra dėmenų e₁ ir e₂ apribojimus nusakančių funkcijų ir sandauga:

Šį pavyzdį galima apibendrinti imant lygtį: , e_i, r – natūralieji skaičiai. Norint sužinoti šios lygties sprendinių skaičių, kai e_i, , tenkina apribojimus , turime sudaryti generuojanči¹ funkcij¹: ir koeficientas prie duos atsakym¹.

Imkime sek¹ . Šios sekos generuojanti funkcija yra

(žr. (3.6.5) formulź).

Remiantis tuo, kad analitinź funkcij¹ galima panariui diferencijuoti, išveskime sekos , generuojanči¹ funkcij¹.

Žemiau pateikiame lentelź, kurioje surašytos kai kurių sekų generuojančios funkcijos.

10 lentelė. Generuojančios funkcijos