Комбинаторика

[Дэвил]

Чуваки, помогите с задачкой:

Дан алфавит А.
Найти число различных строк, находящихся на расстоянии Левенштейна(оно же редакционное расстояние) не большем, чем фиксированное k, от строки-образца длины m.

Заранее спасибо!!!

[Azog]

Здесь чуваков нет.

[незваный гость]

Киевляне уверяли меня, что чувак — это кастрированный бык. А быков здесь, действительно, нет. Да и быкующих не любят.

[Бодигрим]

Цитата:

Киевляне уверяли меня, что чувак — это кастрированный бык.

Нет, что вы: кастрированный бык - это вол. Этимология слова чувак не вполне ясна, насколько я понимаю, хотя и в любом случае оскорбительна: http://ru.wikipedia.org/wiki/Чувак

[Дэвил]

Добрый день!

Я Вас всех, товарищи, понял... У каждого свои понятия на счёт каждого слова. Если чем обидел, прошу извинений!

Прошу помочь, ответить на поставленный вопрос.

[maxal]

Дэвил писал(а):

Дан алфавит А.
Найти число различных строк, находящихся на расстоянии Левенштейна(оно же редакционное расстояние) не большем, чем фиксированное k, от строки-образца длины m.

Могу дать оценку сверху:

$$\sum_{j=0}^k \binom{m+j}{j} \binom{m}{k-j} a^k + \sum_{j=1}^k \binom{m}{j} \binom{m-j}{k-j} a^{k-j}$$

где $a=|A|$ - размер алфавита.
Идея состоит в подсчете числа строк, которые можно получить из данной операциями вставки, удаления и замены символов. К сожалению, в точности это число вычислить тяжело, потому что оно зависит от конкретной строки. А в данном посчете мы игнорируем тот факт, что одна и та же строка может быть получена из данной разными способами, и поэтому, возможно, считаем некоторые строки несколько раз. Поэтому наш подсчет ведет лишь в к верхней грани на число различных строк.

[незваный гость]

maxal, нельзя ли чуть подробнее? Например, для $k = 1$ Ваша формула даёт $2 a m + a + m$, в то время как считая все символы строки «значащими», мы получаем $((m+1)a)+(m) + (m(a-1))$ (вставки, удаления, замены) $ = 2 a m + a $.