1

Topic: Tandemnye repetitions

All greetings. There was  a task. It is required to find an amount of lines of length n (n <= 100) which do not comprise  repetitions of length from 1 to k (1 <= k <= 9) over the given alphabet from and letters (1 <= a <= 26). As tandemnym repetition is called the line of a type ww. I.e., to find all the line long which do not comprise type substrings ww, |w | <= k. There are ideas? Thanks.

2

Re: Tandemnye repetitions

Hello, Serge, you wrote: S> There are ideas? Well, we scan every line from left to right and if the current character is equal previous we increase the counter and if it is not equal - it is dropped. If in the course of magnification reached to k, means, a line rejected, we pass to the following. As a result, we look at each character no more an once. Hardly it is possible to make better.

3

Re: Tandemnye repetitions

Hello, Pzz, you wrote: Pzz> Well, we scan every line from left to right. A what lines we will scan? Lines are not set also to us it is required to learn, how many such lines exist. For example, for n=4, k=2, a=10 the answer will be 7200.

4

Re: Tandemnye repetitions

Hello, Serge, you wrote: Pzz>> Well, we scan every line from left to right. S> A what lines we will scan? Lines are not set also to us it is required to learn, how many such lines exist. I misunderstood the task. I thought, means, to find such lines among set, instead of the greatest possible number of such lines. I suppose, this task has the analytical decision, but to find it to me too hard.

5

Re: Tandemnye repetitions

Hello, Serge, you wrote: S> All greetings. S> there was  a task. It is required to find an amount of lines of length n (n <= 100) which do not comprise  repetitions of length from 1 to k (1 <= k <= 9) over the given alphabet from and letters (1 <= a <= 26). As tandemnym repetition is called the line of a type ww. I.e., to find all the line long which do not comprise type substrings ww, |w | <= k. S> There are ideas? S> thanks. Correctly I understand? w is a certain sequence of letters (in this sequence from 1 to k letters) If in line there are two identical sequences going one after another, such line bad to Find an amount of good lines of length n

6

Re: Tandemnye repetitions

Hello, the Corkcrew, you wrote: Hello, Serge, you wrote: S>> All greetings. S>> there was  a task. It is required to find an amount of lines of length n (n <= 100) which do not comprise  repetitions of length from 1 to k (1 <= k <= 9) over the given alphabet from and letters (1 <= a <= 26). As tandemnym repetition is called the line of a type ww. I.e., to find all the line long which do not comprise type substrings ww, |w | <= k. S>> There are ideas? S>> thanks. Correctly I understand? w is a certain sequence of letters (in this sequence from 1 to k letters) If in line there are two identical sequences going one after another such line bad to Find an amount of good lines of length n Yes, all is true.