Üreteç İşlevi

Matematikte üreteç işlevi (İng. generating function) verilen bir dizinin girdilerinin bilgisini katsayılarında tutan biçimsel bir güç serisidir.

Kullanım ve uygulama olanaklarına göre çeşitli üreteç işlevleri vardır. Örneğin verilen bir a_n dizisine karşılık gelen adi üreteç işlevi ,üstel üreteç işlevi, Lambert serisi, Bell serisi, ve Dirichlet serisigibi..her üreteç işlevi tipinin bir dizisi vardır, adi üreteç işlevi şöyle tanımlanır:

$G(a_n;x)=\sum_{n=0}^{\infty}a_nx^n.$

Bir a_n dizisi için üssel (eksponensiyel) üreteç işlevi ise şöyledir:

$G(a_n;x)=\sum_{n=0}^{\infty}\frac{a_n}{n!}x^n.$

Bir S örnek uzayı üzerinde negatif olmayan bir rassal değişken X için (yani her $s\in S$ için $X(s)\geq 0$)

$G_X(x)=\sum_{n=0}^{\infty} p(X(s)=n) x^n$

serisine olasılık üreteç işlevi denir. Burada p harfi olasılık dağılımıdır.

Bir üreteç işlevi, yalnızca biçimsel olarak bir güç serisi olduğundan, her x değeri için yakınsak olmak zorunda değildir. Üreteç işlevinin kullanıldığı bağlam ve örneğe göre kimi zaman uygun düşen x değerleri için yakınsaklığı araştırılabilir ve bu x değerleri için eşit olduğu işlev yazılabilir. Örneğin, $1,1,1,\ldots$ dizisine karşılık gelen

$\sum_{n=0}^{\infty}x^n$

üreteç işlevi, $|x|<1$ için $\frac{1}{1-x}$ işlevine eşittir.

Örnekler

sayıların karesi'dizisi için üreteç fonksiyonu a_n = n² dır:

basit üreteç fonksiyonu

$G(n^2;x)=\sum_{n=0}^{\infty}n^2x^n=\frac{x(x+1)}{(1-x)^3}$

Üstel üreteç fonksiyonu

$EG(n^2;x)=\sum _{n=0}^{\infty} \frac{n^2x^n}{n!}=x(x+1)e^x$

Bell serisi

$f_p(x)=\sum_{n=0}^\infty p^{2n}x^n=\frac{1}{1-p^2x}$

Dirichlet serisi üreteç fonksiyonu

$DG(n^2;s)=\sum_{n=1}^{\infty} \frac{n^2}{n^s}=\zeta(s-2)$

Çokdeğişkenli üreteç fonksiyonu

Çokdeğişkenli üreteç fonksiyonu sayılarının pratik hesabının sınır tablosu negatif olmayan tamsayılarla hazırlanmış özel satır ve sütunlara özgüdür. kolaylık olsun diye r satır ve c sütun; satır toplamı $t_1,\ldots t_r$ dır. sütun toplamı $s_1,\ldots s_c$.'dır.I. J. Good ,'ye göre $x_1^{t_1}\ldots x_r^{t_r}y_1^{s_1}\ldots y_c^{s_c}$ katsayılarının sayı tablosu

$\prod_{i=1}^{r}\prod_{j=1}^c\frac{1}{1-x_iy_j}.$

Uygulamalar

• verilen özyineleme'li bir dizi için kapalı formül bulma. Örneğin Fibonacci sayıları düşünülebilir.
• Diziler için özyineleme ilişkileri - Bir üreten fonksiyon şeklinde özyineleme formülü önerilebilir.
• Diziler arasında ilişkileri bulma - iki üreten fonksiyonlu dizi varsa , bu dizilerin muhtemelen ortak bir formu vardır.
• Dizilerinin asimtotik davranışı keşfetme.
• Kimlikler içeren dizileri kanıtlama.
• Kombinatorik içinde numaralandırma sorunlarını çözme ve çözümleri kodlama. Rook polinomları kombinatorikte uygulama için bir örnektir.
• Sonsuz toplamları değerlendme.

Benzer kavramlar

Polinomal öteleme,bir polinomu (katsayı 'sız) kabul eden değerleri bulmak. ;soyut bir durumda değişmeli cebir'deki Hilbert polinomu'dur

Bakınız

• Moment-üreten fonksiyon
• olasılık-üreten fonksiyon
• Stanley'in terslik teoremi
• bölüntü uygulamaları.
• kombinatorik'in prensipleri

Kaynakça

• Herbert S. Wilf, Generatingfunctionology (Second Edition) (1994) Academic Press. ISBN 0-12-751956-4.

• Donald E. Knuth, The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: Generating Functions, pp. 87–96.

• Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. A foundation for computer science (Second Edition) Addison-Wesley. ISBN 0-201-55802-5. Chapter 7: Generating Functions, pp. 320–380

Dış bağlantılar

• Generating Functions, Power Indices and Coin Change at cut-the-knot
• Generatingfunctionology PDF download page
• 1031 Generating Functions
• Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados, newsgroup es.ciencia.matematicas
• Frederick Lecue; Riedel, Marko, et al., Permutation, Les-Mathematiques.net, in French, title somewhat misleading.
• "Generating Functions" by Ed Pegg, Jr., Wolfram Demonstrations Project, 2007.