Binomial Complexity of Multidimensional Arrays

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,\mathrm{\ell })$-binomial equivalence for finite arrays and, from it, the $(k,\mathrm{\ell })$-binomial complexity function of an infinite array. Roughly, two finite arrays are $(k,\mathrm{\ell })$-binomially equivalent when they share the same number of subarrays of size at most $k\times \mathrm{\ell }$. We obtain general results on the $(k,\mathrm{\ell })$-binomial complexity of infinite arrays coding direct products of infinite words. Our main theorem gives an exact formula for the $(k,\mathrm{\ell })$-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.