Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e., subwords of $k$ symbols) that appear in $w$ (without multiplicity) and $E$ given by the $(k+1)$-lets in $w$ that appear *with* multiplicity. If $w$ is a [de Bruijn sequence][1], $G_k(w)$ is a [de Bruijn graph][2]. So call $G_k(w)$ a generalized de Bruijn graph corresponding to $w$ (and $k$). It is not hard to compute the number of words $w'$ having $G_k(w)$ as their generalized de Bruijn graph, using the [matrix-tree][3] and [BEST theorems][4]. 

In two dimensions, the picture is much less clear. [De Bruijn tori][5] are basically periodic rectangular arrays of symbols in which all possible subarrays of a certain size occur with multiplicity 1. There is a [hypergraph][6]--the "generalized de Bruijn hypergraph"--corresponding to a generic rectangular array of symbols in a generalization of the sketch above, so by analogy call a rectangular array of symbols over a finite alphabet a generalized de Bruijn torus in this context.

How can the number of arrays corresponding to a generalized de Bruijn hypergraph be enumerated?

(Note that even the *existence* of de Bruijn tori for nonsquare subarrays is uncertain, which is why I'm working in the "generalized" context.)


  [1]: http://en.wikipedia.org/wiki/De_Bruijn_sequence
  [2]: http://en.wikipedia.org/wiki/De_Bruijn_graph
  [3]: http://en.wikipedia.org/wiki/Kirchhoff%2527s_theorem
  [4]: http://en.wikipedia.org/wiki/BEST_theorem
  [5]: http://en.wikipedia.org/wiki/De_Bruijn_torus
  [6]: http://en.wikipedia.org/wiki/Hypergraph