# Density of appearances of word in a shifted grid

Let $w = w_1 \dots w_n$ for $n \geq 1$ be your favorite word, chosen from some alphabet $\Sigma$. Say you like the word ALPHA. Now consider the following infinite table:

ALPHA
AALPH
HAALP
PHAAL
LPHAA
ALPHA
AALPH
HAALP
.....


Now using standard boggle rules, there's a whole bunch of ways in this table to spell the word "ALPHA" -- for example, one can take the top row:

ALPHA


or one could also use the top two rows in a bunch of ways (the letters you use are in caps)

aLPHA
Aalph

aLPHA
aAlph

alpHA
aALPh

alphA
aALPH


and so forth.

The question is, is there a way to describe the "density" of solutions to this equation? Roughly speaking, if $|w| = n$, then let $c_w(k)$ be the number of ways to spell the word in the first $nk$ rows using these rules (I think it makes sense here to call two solutions different if they use the same letters in a different order). Then is there a closed form for $\displaystyle \lim_{k \to \infty} \frac{c_w(k)}{k}?$

• Can you state the standard Boggle rules for those of us not familiar with them? It seems to be a walk along an 8-connected grid i.e. diagonals are considered adjacent, is that right?
– user856
Aug 24 '17 at 2:19
• I think it's useful to think of the case where all of the letters are distinct. For example, if your word is ABOVE, there are $2^5$ possible ways starting specifically in the leftmost column (note branching factor of 2). There are fewer ways if you start in any other column, because some of the letters get cut off. Aug 24 '17 at 2:58
• Edit: $2^4$. According to these rules, are you allowed to visit the same space twice in one walk? That is, can you have a cycle in your solution path? Aug 24 '17 at 3:46
• @Rahul that is exactly correct -- my apologies
– MCT
Aug 24 '17 at 5:17

Consider words with all-distinct letters. In that case, you can always walk up or right, but never any other direction. Starting in the leftmost column leaves all possibilities open, while starting in a more rightward column will limit some of the possibilities because the letters get cut off.

Based on the combinatorics of these up-right walks, the total number of ways of making an $$n$$-letter words with distinct letters is $$(n+2)\cdot 2^{n-1}$$ (see https://oeis.org/A001792).

$$1, 6, 17, 20, 48, 112, 256, \ldots$$

By total number of ways, I mean that there are $$n\times n$$ essentially unique places to start. If you take the sum over all of those places of the number of different ways of forming the word, you obtain this formula.

Hence the density of ways per square in the infinite grid is

$$\frac{1}{n^2}(n+2)\cdot 2^{n-1}$$

This is a lower bound for general $$n$$ letter words, since repeated letters mean more possibilities.

In particular, for the other extreme case of an $$n$$-letter word made of all the same letter, the density is much higher. I haven't found a closed form for it, but assuming cycles are not allowed, the sequence of densities seems to be (for $$n=1,2,3,\ldots$$) :

$$1, 20, 216, 744, 1750, 3024,\ldots$$