Skip to content
DraconiticResearch
Search Sources API
190,332 studies31 sourcesUpdated 13 min ago
PreprintCC BY 4.0arXiv

Binomial Complexity of Multidimensional Arrays

  • Mehdi Golafshan
  • Michel Rigo
Open at sourcePDFDOICite

Abstract

Binomial coefficients for multidimensional arrays count occurrences of particular configurations. For the sake of presentation, the emphasis is put on column-binomial coefficients for two-dimensional finite arrays. In this article, we first show that these coefficients can be computed through some Magnus transform. To get structural and combinatorial information on arrays, we then define (k,ℓ)-binomial equivalence for finite arrays and, from it, the (k,ℓ)-binomial complexity function of an infinite array. Roughly, two finite arrays are (k,ℓ)-binomially equivalent when they share the same number of subarrays of size at most k× ℓ. We obtain general results on the (k,ℓ)-binomial complexity of infinite arrays coding direct products of infinite words. Our main theorem gives an exact formula for the (k,ℓ)-binomial complexity of the two-dimensional Thue--Morse array. To that end, we closely examine the action of the bit-wise complement on the k-binomial equivalence classes of the factors of the Thue--Morse word.

Related

  1. Comments on "Multidimensional Costas Arrays and Their Periodicity"
    Shiv Munagala
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Regularity and depth of binomial ideals arising from combinatorics
    Takayuki Hibi, Seyed Amin Seyed Fakhari
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Stein's method for negative binomial and hyper-negative-binomial laws, with applications
    Stephen DeSalvo
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Diagonal F-threshold of binomial edge ideals
    Giancarlo Rinaldo, Francesco Romeo
    arXivPreprintCC0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. Extended One-Liners for the Gamma, Poisson, and Binomial Distributions
    Dylan Greaves
    arXivPreprintCC BY 4.0Full textProbabilityStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{golafshan2026binomial,
  title = {{Binomial Complexity of Multidimensional Arrays}},
  author = {Mehdi Golafshan and Michel Rigo},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.36389},
  eprint = {2609.36389},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.36389},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Binomial Complexity of Multidimensional Arrays
AU  - Mehdi Golafshan
AU  - Michel Rigo
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.36389
UR  - https://arxiv.org/abs/2609.36389
AB  - Binomial coefficients for multidimensional arrays count occurrences of particular configurations. For the sake of presentation, the emphasis is put on column-binomial coefficients for two-dimensional finite arrays. In this article, we first show that these coefficients can be computed through some Magnus transform. To get structural and combinatorial information on arrays, we then define (k,ℓ)-binomial equivalence for finite arrays and, from it, the (k,ℓ)-binomial complexity function of an infinite array. Roughly, two finite arrays are (k,ℓ)-binomially equivalent when they share the same number of subarrays of size at most k× ℓ. We obtain general results on the (k,ℓ)-binomial complexity of infinite arrays coding direct products of infinite words. Our main theorem gives an exact formula for the (k,ℓ)-binomial complexity of the two-dimensional Thue--Morse array. To that end, we closely examine the action of the bit-wise complement on the k-binomial equivalence classes of the factors of the Thue--Morse word.
ER  -