Doctoral thesis (Dissertations and theses)
Binomial Coefficients of Words and Multidimensional Arrays: Geometry, Complexity, and Reconstruction
Golafshan, Mohammadmehdi
2026
 

Files


Full Text
PhD_Dissertation_113.pdf
Embargo Until 10/Dec/2027 - Author postprint (4.65 MB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Combinatorics on words; Binomial coefficients of words; Binomial complexity; Multidimensional words; Word reconstruction
Abstract :
[en] THE BINOMIAL COEFFICIENT of two words counts occurrences of one as a scattered subword of the other. This dissertation studies how these multiplicities encode order. For binary words, chambers of affine hyperplane arrangements correspond bijectively to abelian, 3/2-binomial, 2-binomial, and finer quasi-binomial classes. We obtain canonical representatives and enumeration formulas; class sizes are coefficients of Gaussian binomial polynomials. For generalized Thue–Morse words over m letters, we determine the k-binomial complexity at every length for all k ≥ 2 and establish eventual periodicity with period mk, proving a conjecture of Lü, Chen, Wen, and Wu. We also develop an intermediate 3/2-binomial equivalence over ordered alphabets, compute its complexity for several classical families, and characterize boundedness by C-balance for some constant C. We extend binomial coefficients recursively to multidimensional arrays, preserving the main identities, and define complexity functions for rectangular factors. For the binary two-dimensional Thue–Morse array, we obtain exact formulas and eventual periodicity in both coordinates. For generalized Thue–Morse arrays over m ≥ 3 letters, the (k,2)-binomial complexity, for k ≥ 2, agrees with a periodic function on a set of shapes of natural density one, yet is not eventually periodic in either coordinate on any cofinal quadrant. In a fixed component of a regular language of polynomial growth, binomial queries are polynomials in the loop exponents. We solve reconstruction for reduced two-loop presentations and give, for any number of loops, a decidable sufficient condition by quantifier elimination over the reals.
[fr] LE COEFFICIENT BINOMIAL de deux mots dénombre les occurrences de l’un comme sous-mot épars de l’autre. Cette thèse étudie la manière dont ces multiplicités encodent l’ordre des lettres. Pour les mots binaires, les chambres d’arrangements d’hyperplans affines sont en bijection avec les classes d’équivalence abélienne, 3/2-binomiale et 2-binomiale, ainsi qu’avec des classes quasi-binomiales plus fines. Nous obtenons des représentants canoniques et des formules de dénombrement; les cardinalités des classes sont des coefficients de polynômes binomiaux gaussiens. Pour les mots de Thue–Morse généralisés sur un alphabet à m lettres, nous déterminons la complexité k-binomiale pour toute longueur et tout k ≥ 2, et établissons sa périodicité ultime de période mk, démontrant ainsi une conjecture de Lü, Chen, Wen et Wu. Nous développons également une équivalence intermédiaire, l’équivalence 3/2-binomiale, sur les alphabets ordonnés. Nous calculons la complexité correspondante pour plusieurs familles classiques et montrons que cette complexité est bornée si et seulement si le mot considéré est C-équilibré pour une certaine constante C. Nous étendons récursivement les coefficients binomiaux aux tableaux multidimensionnels, en préservant leurs principales identités, et définissons des fonctions de complexité pour les facteurs rectangulaires. Pour le tableau de Thue– Morse binaire bidimensionnel, nous obtenons des formules exactes et établissons la périodicité ultime suivant chacune des deux coordonnées. Pour les tableaux de Thue–Morse généralisés sur un alphabet à m ≥ 3 lettres, la complexité (k,2)-binomiale, pour k ≥ 2, coïncide avec une fonction périodique sur un ensemble de formats rectangulaires de densité naturelle 1, mais n’est ultimement périodique suivant aucune des deux coordonnées sur aucun quadrant cofinal. Dans une composante fixée d’un langage régulier à croissance polynomiale, les requêtes binomiales s’expriment comme des polynômes en les exposants des boucles. Nous résolvons le problème de reconstruction pour les présentations à deux boucles sous forme réduite et donnons, pour un nombre quelconque de boucles, une condition suffisante décidable par élimination des quantificateurs sur les réels.
Research Center/Unit :
Mathematics - ULiège
Disciplines :
Mathematics
Author, co-author :
Golafshan, Mohammadmehdi ;  Université de Liège - ULiège > Mathematics
Language :
English
Title :
Binomial Coefficients of Words and Multidimensional Arrays: Geometry, Complexity, and Reconstruction
Defense date :
10 December 2026
Number of pages :
384
Institution :
ULiège - Université de Liège [Faculté des Sciences], Liège, Belgium
Degree :
Docteur en sciences
Promotor :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
President :
Charlier, Emilie  ;  Université de Liège - ULiège > Mathematics
Secretary :
Leroy, Julien ;  Université de Liège - ULiège > Mathematics
Jury member :
FOKKINK, Robbert;  Delft University of Technology > Delft Institute of Applied Mathematics (DIAM) > Applied Probability
DRMOTA, Michael;  TU Wien > Institute of Discrete Mathematics and Geometry > Research Unit of Combinatorics and Algorithms
PIN, Jean-Éric;  CNRS - Centre National de la Recherche Scientifique > Institut de Recherche en Informatique Fondamentale (IRIF)
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique
Funding number :
T.196.23
Funding text :
This research was supported by the PDR FNRS grant T.196.23.
Available on ORBi :
since 05 November 2026

Statistics


Number of views
34 (9 by ULiège)
Number of downloads
5 (5 by ULiège)

Bibliography


Similar publications



Contact ORBi