atgnybo4fq

Answered

2022-11-17

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{array}{ll}{\displaystyle (k-d)\cdot f(i+1,d+1,k)+\sum _{c=1}^{d}f(i+1,c,k)}& i<n,d<k\\ 1& i=n,d<k\\ 0& i>n\\ 0& d\ge k\end{array}$

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 3rd 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?

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{array}{ll}{\displaystyle (k-d)\cdot f(i+1,d+1,k)+\sum _{c=1}^{d}f(i+1,c,k)}& i<n,d<k\\ 1& i=n,d<k\\ 0& i>n\\ 0& d\ge k\end{array}$

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 3rd 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?

Answer & Explanation

Phiplyrhypelw0

Expert

2022-11-18Added 24 answers

If you want $wv=r$ where $w,v$ are irrational and $r$ is rational, that must mean that $w=\frac{r}{v}$ (since $v$ is irrational it isn't $0$ so we don't have to worry about that)

So to find any pair you want just pick any arbitrary rational number (so long as it is not zero; as $w\ne 0$ and $v\ne 0$ then $wv\ne 0$; but that is the only restriction; we can pick any other rational at all), and pick any arbitrary irrational $v$. Then let $w=\frac{r}{v}$. As $v$ is irrational and $r$ is non-zero rational we will have $w=\frac{r}{v}$ be irrational.

And we have, voila $wv=\frac{r}{v}\cdot v=r$.

So to find any pair you want just pick any arbitrary rational number (so long as it is not zero; as $w\ne 0$ and $v\ne 0$ then $wv\ne 0$; but that is the only restriction; we can pick any other rational at all), and pick any arbitrary irrational $v$. Then let $w=\frac{r}{v}$. As $v$ is irrational and $r$ is non-zero rational we will have $w=\frac{r}{v}$ be irrational.

And we have, voila $wv=\frac{r}{v}\cdot v=r$.

Most Popular Questions