Search

It is well known that Pascal‟s triangle represents the binomial coefficients in binomial expansion. These numbers can also be interpreted as the numbers of (shortest) paths from the given position to top element of the triangle allowed to use two types of steps in these paths (left-up and right-up steps). The binomial coefficients show, in fact, the number of shortest paths in the square grid if only grid paths, i.e., paths on the grid lines (paths with cityblock distance), are allowed, and they also give the number of shortest paths in the hexagonal grid. When diagonal steps are also allowed in the square grid (paths with chessboard distance), the number of shortest paths can be described by trinomial coefficients. They can be obtained also in a triangle form by summing up three neighbour elements in the previous row. We consider also further generalisations of such triangles and their elements, quadrinomial and n-nomial coefficients. In this context, n-nomial coefficients of n-nomial expansions represent the numbers of paths from the position of the coefficient up to the top element of the triangle allowed to use n different types of steps, such that for trinomial coefficients, we use three types of steps, and quadrinomial coefficients we use four types of steps. We also present formulae to calculate trinomial, quadrinomial and n-nomial coefficients based on trinomial, quadrinomial and n-nomial expansions, where the power of the sum of more than two items is computed, respectively. Multinomial expansions are also related. We give also a comparison of those values known as various ways of generalisations of the binomial coefficients. The number of shortest paths between any point pairs of the square grid, based on weighted distances, is computed. We use an 8-adjacency square grid, that is, a first weight is associated to the horizontal and vertical movements, while a second weight (not necessarily different from the first) is assigned to the diagonal steps. The chamfer distance of two points depends on the numbers and weights of the steps in a „shortest path‟. In special cases, as we have already mentioned, the cityblock and the chessboard distances, the two most basic and widely used digital distances of the two-dimensional digital space occur. Although our combinatorial result is theoretical, it is closely connected to applications, such as communication networks, path counting in digital images, traces and trajectories in 2D digital grids. We consider all the seven cases with non-negative weights and also the case when negative weights are allowed. Also, we will discuss the number of weighted shortest paths between any two pixels in the triangular grid, where the number of shortest paths depend on the values of α, β and γ weights. In the triangular grid for each pixel, we have three types of neighbourhood:1st, 2nd and 3rd neighbourhood, where we assign a weight for each neighbourhood type, and according to these weights, we use Chamfer distance to define these shortest paths, and we use combinations of absolute differences between pixels to define number of these paths. Keywords: Binomial Coefficients; Trinomial Coefficients; Quadrinomial Coefficients; n-nomial Coefficients; Multinomial Coefficients; Trajectories; Weighted Distances; Digital Distances; Combinatorics; Triangular Grid, Neighbourhood Types, Chamfer Distance; Shortest Weighted Paths; Path Counting. ÖZ: Pascal üçgeninin binom açılımındaki binom katsayılarını temsil ettiği iyi bilinmektedir. Bu sayılar, aynı zamanda, bu konumlarda iki tür adım (sol-yukarı ve sağ-yukarı adımlar) kullanılmasına izin verilen, verilen konumdan üçgenin üst elemanına kadar (en kısa) yolların sayısı olarak da yorumlanabilir. Binom katsayıları, aslında sadece ızgara yollarının, yani ızgara çizgilerindeki yollara (şehir bloğu uzaklığına sahip yollar) izin verilirse, kare ızgaradaki en kısa yolların sayısını gösterir ve ayrıca altıgen ızgaradaki en kısa yolların sayısını verir. Kare ızgarada (satranç tahtası uzaklıklı yollar) köşegen adımlara da izin verildiğinde, en kısa yolların sayısı üçlü katsayılarla tanımlana bilir. Bir önceki satırda üç komşu elemanı toplayarak üçgen şeklinde de elde edilebilirler. Bu tür üçgenlerin ve elemanlarının, kuadrinomiyal ve n-nominal katsayıların daha fazla genelleştirilmesini de düşünüyoruz. Bu bağlamda, n-nomal açılımların n-nomal katsayıları, katsayı pozisyonundan üçgenin üst elemanına kadar n farklı tipte adım kullanılmasına izin verilen yolların sayısını temsil eder, böylece üçlü katsayılar için üç adım türleri ve dört adım katsayısı dört tür adım kullanırız. Ayrıca, ikiden fazla öğenin toplamının kuvvetinin hesaplandığı üçlü, dörtlü ve n-nomiyal açılımlara dayanan üçlü, dörtlü ve n-nomal katsayıları hesaplamak için formüller sunuyoruz. Çok terimli açılımlar da ilişkilidir. Ayrıca binom katsayılarının çeşitli genelleme yöntemleri olarak bilinen değerlerin bir karşılaştırmasını da veriyoruz. Ağırlıklı mesafelere göre kare ızgaranın herhangi bir nokta çifti arasındaki en kısa yolların sayısı hesaplanır. 8-komşu kare ızgara kullanıyoruz, yani bir ilk ağırlık yatay ve dikey hareketlerle ilişkiliyken, ikinci bir ağırlık (birinciden farklı olması gerekmez) köşegen adımlara atanmıştır. İki noktanın chamfer uzaklığı, 'en kısa yoldaki' adımların sayılarına ve ağırlıklarına bağlıdır. Özel durumlarda, daha önce de belirttiğimiz gibi, şehir bloğu ve satranç tahtası mesafeleri, iki boyutlu dijital alanın en temel ve yaygın olarak kullanılan iki dijital mesafesi meydana gelir. Kombinatorik sonucumuz teorik olmasına rağmen, iletişim ağları, dijital görüntülerde yol sayma, 2D dijital ızgaralardaki izler ve yörüngeler gibi uygulamalarla yakından bağlantılıdır. Negatif olmayan ağırlıkları olan yedi durumu ve negatif ağırlığa izin verilen durumu da ele alıyoruz. Ayrıca, α, β ve γ ağırlıklarının değerlerine bağlı olarak en kısa yol sayısının olduğu üçgen ızgaradaki herhangi iki piksel arasındaki ağırlıklı en kısa yolların sayısını tartışacağız. Her piksel için üçgen ızgarada, üç tip komsuluk var: her komsuluk tipi için bir ağırlık atadığımız 1., 2. ve 3. komsuluk ve bu ağırlıklara göre, bu en kısa yolları tanımlamak için Chamfer mesafesini kullanıyoruz ve biz bu yolların sayısını tanımlamak için pikseller arasındaki mutlak farklılıkların kombinasyonlarını kullandık. Anahtar Kelimeler: Binom Katsayıları; Trinomiyal Katsayılar; Dörtlü Katsayıları; n-nominal Katsayıları; Çok Terimli Katsayılar; Yörüngeleri; Ağırlıklı Mesafeler; Dijital Mesafeler; Bir Kombinasyon; Üçgen Izgara, Komşuluk Tipleri, Chamfer Mesafesi; En Kısa Ağırlıklı Yollar; Yol Sayımı. Doctor of Philosophy in Applied Mathematics and Computer Science. Thesis (Ph.D.)--Eastern Mediterranean University, Faculty of Arts and Sciences, Dept. of Mathematics, 2020. Supervisor: Prof. Dr. Benedek Nagy.

This thesis extends in several directions the cohomological study of information theory pioneered by Baudot and Bennequin. We introduce a topos-theoretical notion of statistical space and then study several cohomological invariants. Information functions and related objects appear as distinguished cohomology classes; the corresponding cocycle equations encode recursive properties of these functions. Information has thus topological meaning and topology serves as a unifying framework.Part I discusses the geometrical foundations of the theory. Information structures are introduced as categories that encode the relations of refinement between different statistical observables. We study products and coproducts of information structures, as well as their representation by measurable functions or hermitian operators. Every information structure gives rise to a ringed site; we discuss in detail the definition of information cohomology using the homological tools developed by Artin, Grothendieck, Verdier and their collaborators.Part II studies the cohomology of discrete random variables. Information functions—Shannon entropy, Tsallis alpha-entropy, Kullback-Leibler divergence—appear as 1-cocycles for appropriate modules of probabilistic coefficients (functions of probability laws). In the combinatorial case (functions of histograms), the only 0-cocycle is the exponential function, and the 1-cocycles are generalized multinomial coefficients (Fontené-Ward). There is an asymptotic relation between the combinatorial and probabilistic cocycles.Part III studies in detail the q-multinomial coefficients, showing that their growth rate is connected to Tsallis 2-entropy (quadratic entropy). When q is a prime power, these q-multinomial coefficients count flags of finite vector spaces with prescribed length and dimensions. We obtain a combinatorial explanation for the nonadditivity of the quadratic entropy and a frequentist justification for the maximum entropy principle with Tsallis statistics. We introduce a discrete-time stochastic process associated to the q-binomial probability distribution that generates finite vector spaces (flags of length 2). The concentration of measure on certain typical subspaces allows us to extend Shannon's theory to this setting.Part IV discusses the generalization of information cohomology to continuous random variables. We study the functoriality properties of conditioning (seen as disintegration) and its compatibility with marginalization. The cohomological computations are restricted to the real valued, gaussian case. When coordinates are fixed, the 1-cocycles are the differential entropy as well as generalized moments. When computations are done in a coordinate-free manner, with the so-called grassmannian categories, we recover as the only degree-one cohomology classes the entropy and the dimension. This constitutes a novel algebraic characterization of differential entropy.; Cette thèse étend dans plusieurs directions l’étude cohomologique de la théorie de l’information initiée par Baudot et Bennequin. On introduit une notion d'espace statistique basée sur les topos, puis on étudie plusieurs invariants cohomologiques. Les fonctions d’information et quelques objets associés apparaissent comme des classes de cohomologie distinguées ; les équations de cocycle correspondantes codent les propriétés récursives de ces fonctions. L'information a donc une signification topologique et la topologie sert de cadre unificateur.La première partie traite des fondements géométriques de la théorie. Les structures d’information sont présentées sous forme de catégories qui codent les relations de raffinement entre différents observables statistiques. On étudie les produits et coproduits des structures d’information, ainsi que leur représentation par des fonctions mesurables ou des opérateurs hermitiens. Chaque structure d’information donne lieu à un site annelé ; la cohomologie de l'information est introduite avec les outils homologiques développés par Artin, Grothendieck, Verdier et leurs collaborateurs.La deuxième partie étudie la cohomologie des variables aléatoires discrètes. Les fonctions d'information — l'entropie de Shannon, l'alpha-entropie de Tsallis, et la divergence de Kullback-Leibler — apparaissent sous la forme de 1-cocycles pour certains modules de coefficients probabilistes (fonctions de lois de probabilité). Dans le cas combinatoire (fonctions des histogrammes), le seul 0-cocycle est la fonction exponentielle, et les 1-cocycles sont des coefficients multinomiaux généralisés (Fontené-Ward). Il existe une relation asymptotique entre les cocycles combinatoires et probabilistes.La troisième partie étudie en détail les coefficients q-multinomiaux, en montrant que leur taux de croissance est lié à la 2-entropie de Tsallis (entropie quadratique). Lorsque q est une puissance première, ces coefficients q-multinomiaux comptent les drapeaux d'espaces vectoriels finis de longueur et de dimensions prescrites. On obtient une explication combinatoire de la non-additivité de l'entropie quadratique et une justification fréquentiste du principe de maximisation d'entropie quadratique. On introduit un processus stochastique à temps discret associé à la distribution de probabilité q-binomial qui génère des espaces vectoriels finis (drapeaux de longueur 2). La concentration de la mesure sur certains sous-espaces typiques permet d'étendre la théorie de Shannon à ce cadre.La quatrième partie traite de la généralisation de la cohomologie de l'information aux variables aléatoires continues. On étudie les propriétés de fonctorialité du conditionnement (vu comme désintégration) et sa compatibilité avec la marginalisation. Les calculs cohomologiques sont limités aux variables réelles gaussiennes. Lorsque les coordonnées sont fixées, les 1-cocycles sont l’entropie différentielle ainsi que les moments généralisés. Les catégories grassmanniennes permettent de traiter les calculs canoniquement et retrouver comme seuls classes de cohomologie de degré 1 l'entropie et la dimension. Ceci constitue une nouvelle caractérisation algébrique de l'entropie différentielle.

This thesis extends in several directions the cohomological study of information theory pioneered by Baudot and Bennequin. We introduce a topos-theoretical notion of statistical space and then study several cohomological invariants. Information functions and related objects appear as distinguished cohomology classes; the corresponding cocycle equations encode recursive properties of these functions. Information has thus topological meaning and topology serves as a unifying framework.Part I discusses the geometrical foundations of the theory. Information structures are introduced as categories that encode the relations of refinement between different statistical observables. We study products and coproducts of information structures, as well as their representation by measurable functions or hermitian operators. Every information structure gives rise to a ringed site; we discuss in detail the definition of information cohomology using the homological tools developed by Artin, Grothendieck, Verdier and their collaborators.Part II studies the cohomology of discrete random variables. Information functions—Shannon entropy, Tsallis alpha-entropy, Kullback-Leibler divergence—appear as 1-cocycles for appropriate modules of probabilistic coefficients (functions of probability laws). In the combinatorial case (functions of histograms), the only 0-cocycle is the exponential function, and the 1-cocycles are generalized multinomial coefficients (Fontené-Ward). There is an asymptotic relation between the combinatorial and probabilistic cocycles.Part III studies in detail the q-multinomial coefficients, showing that their growth rate is connected to Tsallis 2-entropy (quadratic entropy). When q is a prime power, these q-multinomial coefficients count flags of finite vector spaces with prescribed length and dimensions. We obtain a combinatorial explanation for the nonadditivity of the quadratic entropy and a frequentist justification for the maximum entropy principle with Tsallis statistics. We introduce a discrete-time stochastic process associated to the q-binomial probability distribution that generates finite vector spaces (flags of length 2). The concentration of measure on certain typical subspaces allows us to extend Shannon's theory to this setting.Part IV discusses the generalization of information cohomology to continuous random variables. We study the functoriality properties of conditioning (seen as disintegration) and its compatibility with marginalization. The cohomological computations are restricted to the real valued, gaussian case. When coordinates are fixed, the 1-cocycles are the differential entropy as well as generalized moments. When computations are done in a coordinate-free manner, with the so-called grassmannian categories, we recover as the only degree-one cohomology classes the entropy and the dimension. This constitutes a novel algebraic characterization of differential entropy., Cette thèse étend dans plusieurs directions l’étude cohomologique de la théorie de l’information initiée par Baudot et Bennequin. On introduit une notion d'espace statistique basée sur les topos, puis on étudie plusieurs invariants cohomologiques. Les fonctions d’information et quelques objets associés apparaissent comme des classes de cohomologie distinguées ; les équations de cocycle correspondantes codent les propriétés récursives de ces fonctions. L'information a donc une signification topologique et la topologie sert de cadre unificateur.La première partie traite des fondements géométriques de la théorie. Les structures d’information sont présentées sous forme de catégories qui codent les relations de raffinement entre différents observables statistiques. On étudie les produits et coproduits des structures d’information, ainsi que leur représentation par des fonctions mesurables ou des opérateurs hermitiens. Chaque structure d’information donne lieu à un site annelé ; la cohomologie de l'information est introduite avec les outils homologiques développés par Artin, Grothendieck, Verdier et leurs collaborateurs.La deuxième partie étudie la cohomologie des variables aléatoires discrètes. Les fonctions d'information — l'entropie de Shannon, l'alpha-entropie de Tsallis, et la divergence de Kullback-Leibler — apparaissent sous la forme de 1-cocycles pour certains modules de coefficients probabilistes (fonctions de lois de probabilité). Dans le cas combinatoire (fonctions des histogrammes), le seul 0-cocycle est la fonction exponentielle, et les 1-cocycles sont des coefficients multinomiaux généralisés (Fontené-Ward). Il existe une relation asymptotique entre les cocycles combinatoires et probabilistes.La troisième partie étudie en détail les coefficients q-multinomiaux, en montrant que leur taux de croissance est lié à la 2-entropie de Tsallis (entropie quadratique). Lorsque q est une puissance première, ces coefficients q-multinomiaux comptent les drapeaux d'espaces vectoriels finis de longueur et de dimensions prescrites. On obtient une explication combinatoire de la non-additivité de l'entropie quadratique et une justification fréquentiste du principe de maximisation d'entropie quadratique. On introduit un processus stochastique à temps discret associé à la distribution de probabilité q-binomial qui génère des espaces vectoriels finis (drapeaux de longueur 2). La concentration de la mesure sur certains sous-espaces typiques permet d'étendre la théorie de Shannon à ce cadre.La quatrième partie traite de la généralisation de la cohomologie de l'information aux variables aléatoires continues. On étudie les propriétés de fonctorialité du conditionnement (vu comme désintégration) et sa compatibilité avec la marginalisation. Les calculs cohomologiques sont limités aux variables réelles gaussiennes. Lorsque les coordonnées sont fixées, les 1-cocycles sont l’entropie différentielle ainsi que les moments généralisés. Les catégories grassmanniennes permettent de traiter les calculs canoniquement et retrouver comme seuls classes de cohomologie de degré 1 l'entropie et la dimension. Ceci constitue une nouvelle caractérisation algébrique de l'entropie différentielle.