Давайте обозначим их количество
g(n,m) это количество
всех возможных
выравниваний последовательностей a(1)...
a(n) и b(1)...
b(m) которые, выравнивание,
удовлетворяют условиям 1 и 2.
Вот я утверждаю, что той комбинаторики, которую мы с
вами изучили на предыдущих лекциях, более чем достаточно, для того чтобы осознать
много это или мало, и вообще понять просто чему эта величина равна.
Ну давайте действовать, наверное, постепенно.
Давайте сначала докажем вот такую теорему.
Сначала докажем такую теорему.
Катарсис наступит не в её рамках, а в тот момент когда мы из этой теоремы выведем
содержательное следствие с точной формулой для величины g(n).
А теорема говорит так: она говорит,
что g(n,m) – это в точности g а..
от (n-1,m) +
g(n,m-1) То есть,
если угодно, теорема даёт такую удобную,
как говорят рекуррентную формулу, позволяющую вычислять величину g(n,m).
Имеется в виду, что если мы знаем величину g(n − 1,m) и знаем величину g(n,m − 1),
то сложив эти 2 величины, мы получим величину g(n,m).
Разумеется, в такой формулировке теорема не является сколько-нибудь применимой,
потому что, для того чтобы её применять в конечном счёте нужны какие-то,
как говорят, начальные условия, то есть понятно, что надо с чего-то стартовать.
Надо стартовать с какого-то конкретного значения g.
Ну это легко сообразить.
Вот давайте поймём, например, чему равняется g(1,1).
Это-то можно просто явно посчитать: взять и выравнять 2 последовательности,
каждая из которых имеет длину единиц.
Давайте подумаем, чему равняется величина g(1,1).
Ну одна последовательность у нас а, другая последовательность у нас б.
а длины 1 и б длины 1.
Это вот одно выравнивание, вполне себе корректное.
Есть другое выравнивание, вот такое: а пусто, пусто б.
Естественно, если мы переставим порядок столбцов, то
согласно свойству 2 ничего не изменится, поэтому второго такого я не пишу.
Есть только 1 представитель, так сказать, класса эквивалентных выравниваний.
Так, ну и кажись всё.
Если мы начнём куда-то ещё добавлять гэпы,
то тот час же нарушится вот это свойство 1 просто по принципу Дирихле.
Если мы захотим рассматривать выравнивания,
в которых длина была бы больше двойки, ну 3, например, то у нас сразу возникнут 2
гэпа друг над другом по принципу Дирихле, который мы с вами тоже изучали.
Поэтому конечно g(1,1) = 2, ну и давайте ещё считать,
что g(0,1) = g(1,0) = 1.
То есть выравнять последовательность в длину 1 против последовательности,
которая вообще никакой длины не имеет, то есть из ничего, ни из чего не состоит,
можно только одним способом – ничего не делая.
Ну, условно говоря, рассмотрев вот такую вот штуку.
Вот это вот единственное выравнивание, которое соответствует величинам
g(0,1) и g(1,0), единственное такое выравнивание, вот.
Всё, имея на руках вот такие вот замечательные начальные условия мы дальше,
руководствуясь этой рекурсией, конечно можем написать любое значение g(n, m),
скажем.
Хочется нам найти g(2,2).
Мы уже не будем перечислять тупо все выравнивания,
которые имеются в этом случае, это долго.
Мы напишем вот так это: g(1,2) + g(2,1) ну понятно,
что каждая из этих величин равна одному и тому же, вот,
а в свою очередь g(1,2) это g(0,2) + g(1,1).
Ну и всё, g(1,1) мы с вами знаем, а g(0,2),
ну, понятное дело, равняется 1, или можно дальше применить рекурсию и всё получится.
То есть рано или поздно мы найдём любое число g(n,m) пользуясь вот
этим выражением.
Повторяю, катарсис наступит тогда, когда с помощью наших знаний комбинаторики
мы выведем отсюда следствие, а следствие даст нам уже явную формулу,
которую не нужно будет получать таким путём длительных спусков вниз,
а можно будет просто вот явно подставить и вычислить.
Вот. Но прежде чем мы придем к этой формуле,
давайте докажем вот это вот утверждение.
Оно на самом деле совершенно несложное.