V
V
Vladimir Petrigo2015-03-16 12:03:48
Discrete Math
Vladimir Petrigo, 2015-03-16 12:03:48

How many words of length n can be made from Russian letters such that they contain the word X?

Good afternoon.
I am attending a course on discrete mathematics and in the problem book there are very often tasks like "How many words of length n can be made from Russian letters, that it contains the word X?" or "How many words of length n can be made from Russian letters that it does not contain the word X?". Do I understand correctly that in the first case the task is to find all the placements with the repetition of the remaining n - len(x)letters?
That is, for example, the number of words of length 11 containing the subword "hello":
The word "hello" - length 6
5 more characters can be before "hello", or 4 characters before and 1 after, 3 before - 2 after, etc. .
We get the following result:
c5a7cf2164004ca59168c131e2a80ba1.gif
Am I correct?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
L
localghost, 2015-03-16
@vpetrigo

Perhaps I didn’t understand something, but where do you get degrees below the fifth? If, for example, there are 4 characters before and 1 after - do you count this as 33^4 + 33? Why, how is this different from the case of just 5 characters before?
In my opinion, it should be considered like this: in addition to "hello" there are five more letters. There are 33^5 options to type these five letters. When we already have five letters, the word "hello" can be crammed into it in six different ways. Total 6 * 33^5.
In addition, in the general case, we must take into account that we could count some "words" more than once. Let's say if there are 12 letters in total, then "hello hello" is counted once again. Here, it seems, there is no such thing.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question