Generating functions and their applications

Abstract

Üreteç fonksiyonlar matematiğin ve bilhassa istatistiğin bir çok sahasında kullanılan önemli araçlardır. Kabaca, dizilerin fonksiyonlar cinsinden ifadesi olarak düşünebileceğimiz bu fonksiyonlar dizilerin genel yapılarının ve asimtotik davranışlarının incelenmesinin yanısıra kombinatorik problemlerin çözümünde de etkinlikle kullanılan önemli araçlardır.Bu tezde, üreteç fonksiyonlara uygulanan dönüşümlerin, karşı gelen diziler üstündeki etkileri ve dizilerdeki değişimlerin de üreteç fonksiyonlar üzerindeki etkileri incelenmiştir. Bu bilgiler ışığında tam sayıların parçalanış sayıları, involusyon sayıları, Fibonacci sayıları, Catalan sayılarının bulunması gibi bazı temel kombinatorik problemlerin sonucu olan dizilerin üreteç fonksiyonları elde edilmiştir. Bunun yanısıra,bazı matematiksel özellikler üreteç fonksiyonlar kullanılarak ispatlanmıştır.Diziler, kriptografi alanındaki özellikle simetrik anahtarlı kriptosistemlerin yapı taşlarıdır. Doğrusal geribeslemeli ötemeli yazdırgaç (DGÖY) tabanlı akan şifrelerin teorik altyapısını teşkil eden sabit katsayılı doğrusal homojen indirgeme bağıntıları ile tanımlanan dizilerin doğrusal karmaşıklığı ve periyodlarının, üreteç fonksiyonlar kullanılarak hesaplanabileceği görülmüştür. Üreteç fonksiyonları incelemek bu konuların daha iyi anlaşılmasını sağlamaktadır. Bu nedenle, kombinatorik problemlerin yanısıra, bu tip bağıntılar incelenmiş ve elde edilen sonuçlar `daha iyi` akan şifreler tasarlamak amacıyla birden çok DGÖY'nin birleştirilmesiyle oluşan sistemlerin incelenmesinde kullanılmıştır.

Generating functions are important tools that are used in many areas of mathematics andespecially statistics. Besides analyzing the general structure of sequences and their asymptoticbehavior; these functions, which can be roughly thought as the transformation of sequencesinto functions, are also used efficiently to solve combinatorial problems.In this thesis, the effects of the transformations of generating functions on their correspondingsequences and the effects of the change in sequences on the generating functions are exam-ined. With these knowledge, the generating functions for the resulting sequence of somecombinatorial problems such as number of partitions, number of involutions, Fibonacci num-bers and Catalan numbers are found. Moreover, some mathematical identities are proved byusing generating functions.The sequences are the bases of especially symmetric key cryptosystems in cryptography. It isseen that by using generating functions, linear complexities and periods of sequences gener-ated by constant coefficient linear homogeneous recursions, which are used in linear feedbackshift register (LFSR) based stream ciphers, can be calculated. Hence studying generatingfunctions leads to have a better understanding in them. Therefore, besides combinatorialivproblems, such recursions are also examined and the results are used to observe the linearcomplexity and the period of LFSR?s combined in different ways to generate ?better? systemof stream cipher.