For background and some illustrative pictures, refer to this preprint by A M Grasia and G Ganzberger: Fibonacci polynomials. For the present purpose, it suffices to read into pages 4 and 5.
The part that interested me comes from the map between monomer-dimer heaps and 2-alphabet (finite) words, where a monomer of ground coordinate $i$ corresponds to $m_i$ and a dimer projecting to the interval $[i-1,i]$ corresponds to $d_i$. For examples, look into the above paper.
It becomes clear that several words $w$ might be associated to a given a monomer-dimer heap.
QUESTION. Is it possible to determine the number of words corresponding to a given heap? More modestly, is there an algorithm to compute such number?
