Explore Discrete Math Examples

Recent questions in Discrete math
Discrete mathAnswered question
unecewelpGGi unecewelpGGi 2022-12-01

What is the meaning of l.h.s and r.h.s?

Discrete mathAnswered question
goorst9Bi goorst9Bi 2022-11-24

Why is the value of π is 22 7 ?

Discrete mathAnswered question
atgnybo4fq atgnybo4fq 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 ) = { ( k d ) f ( i + 1 , d + 1 , k ) + c = 1 d f ( i + 1 , c , k ) i < n , d < k 1 i = n , d < k 0 i > n 0 d k
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?

Dealing with discrete Math is an interesting subject because discrete Math equations can be encountered basically anywhere from scheduling of sports games and live shows to education where each person is examined online. It is a reason why discrete math questions that we have collected for you are aimed at solutions that go beyond equations to provide you with the answers that will help you understand the concept. Still, discrete Math equations are explained as well by turning to problems in computer science, programming, software, and cryptography among other interesting subjects like software and mobile apps development.