Аннотация:
We prove that the number of partitions of the hypercube ${\mathbf Z}_q^n$ into $q^m$ subcubes of dimension $n-m$ each for fixed $q$, $m$ and growing $n$ is asymptotically equal to $n^{(q^m-1)/(q-1)}$.
For the proof, we introduce the operation of the bang of a star matrix and demonstrate that any star matrix, except for a fractal, is expandable under some bang, whereas a fractal remains to be a fractal under any bang.
Ключевые слова:
combinatorics, enumeration, asymptotics, partition, partition of hypercube, subcube, star pattern, star matrix, fractal matrix, associative block design, SAT, $k$-SAT.