# Counting words of length $n$ from $k$-sized alphabet with no substring of $k$ consecutive distinct letters

How many words of length $$n$$ are there, if we have an alphabet of $$k$$ distinct letters, but the words cannot contain any substring that is made of $$k$$ consecutive distinct letters, i.e, no $$k$$-length substring that consists of the entire alphabet?

Other than that, no restrictions apply: any amount of distinct letters may be used throughout the entire word, and any letter can be used as many times as we like, as long as every substring inside the length $$n$$ word complies with the rules above.

There is the obvious case of $$k=2$$ which results in $$2$$ words, for every $$n$$, because you can only start with either letter, and they alternate.

For the larger case, I have come up with a recursive formula:

$$C(n,k)=f(0,0,k)$$ $$f(i,d,k)=\begin{cases}\displaystyle(k-d) \cdot f(i+1,d+1,k) + \sum_{c=1}^df(i+1,c,k) & in\\ 0 &d\geq k \end{cases}$$

With $$d$$ being the current length of consecutive distinct letters, and $$i$$ the current word length.

At every step, we can either use a letter other than the previous $$d$$ letters, in which case the length is increased by one, and the chain-length $$d$$ of distinct consecutive letters is also increased by one. In this case, there are $$(k-d)$$ such letters we can use at the stage, each subsequently resulting in the same contribution.

Or, we can use a letter already in the last $$d$$ letters. In this case, the position of the letter matters. If we use the last of the $$d$$ letters, a whole new chain begins. If instead we use the second last $$d$$ letter, then a chain of length $$2$$ of consecutive distinct letters begins. The $$3$$rd last would result in a chain of length $$3$$ and so on.

I was wondering if there is a another way to count the amount of such words, perhaps using matrices or combinatorics?

• what are the possible constraints for $n$ and $k$? Commented Jul 11, 2021 at 20:01
• @Yorch Well, it's theoretical, but say $k$ is relatively small I would say, up to $10$, and $n$ is really large, up to $10^{10}$ Commented Jul 11, 2021 at 20:13
• you can build an automaton that accepts it. Chomsky-Schutzenbergers theorem tells you how to count it. Commented Jul 11, 2021 at 20:17
• @Phicar Can you please elaborate? I went through the wikipedia entry and a few other sources. Did not understand how to apply it here exactly Commented Jul 13, 2021 at 18:35
• @Matan I will over the weekend, sorry for delay. Commented Jul 16, 2021 at 7:16

This might not provide a full answer, but here is some direction if you are familiar with generating functions. I believe that this type of ideas for counting problems on words was first introduced by Guibas and Odlyzko.

Imagine that the alphabet is $$\Sigma=\{1,\ldots, k\}$$. Let $$F(z)$$ be the generating function of strings with no permutation of $$\Sigma$$ as a substring (let's call them "good strings"), and $$G(z)$$ be the generating function of strings with no permutation of $$\Sigma$$ as a substring, except the last $$k$$ letters which are $$1, \ldots, k$$ (in that order). (By symmetry, you would get the same generating function if you replace $$1, \ldots, k$$ by any of its permutations in the definition of $$G$$.)

Now by counting what happens when you add one letter to the right of good string,

$$F(z)+k!G(z)=1+kzF(z)\tag{1}.$$

By another counting argument on the concatenation of good string and the sequence $$1, \ldots, k$$,

$$F(z)z^k=G(z)\sum_{i=0}^{k-1} i! z^i\tag{2}$$

After solving the linear system (1) and (2), we get

$$F(z)=\frac{P(z)}{k!z^k+(1-kz)P(z)},$$

where $$P(z)=\sum_{i=0}^{k-1} i! z^i$$. You can check the series expansion for $$k=2$$.