Density of appearances of word in a shifted grid

34 Views Asked by At

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}?$

1

There are 1 best solutions below

0
On

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$$