Ну что, выходим на финишную прямую.
Давайте расписывать нашу двойную сумму так, как я, собственно, обещал.
Значит, сначала мы суммируем по всем t от 1 до k, это сколько у нас общих вершин.
Ну дальше, наверное, удобно все-таки нарисовать очередную картину,
вот у нас тут t общих вершин, тут k, тут k.
Нам нужно посчитать каким-то образом, сколько существует вот этих самых
способов зафиксировать 2 копии графа H с конкретно t общими вершинами.
Ну смотрите, все на самом деле просто: надо взять C из n по k — это
количество способов выбрать вершины для первой копии.
А затем надо подумать, сколькими способами можно выбрать вершины для второй копии.
Ну, во-первых, надо выбрать t общих.
Это делается C из k по t способами, выбираются те t общих,
по которым они пересекаются.
Дальше, когда эти t общих выбраны, нам надо взять n − k вершин,
которые не попали в фиксированную первую копию,
и добавить к уже зафиксированной части второй копии (зафиксировано t вершин),
вот видите, зафиксировано t вершин.
А всего во второй копии должно быть k вершин.
Ну значит, надо добавить k − t, вот у нас t вершин выбраны, еще k −
t вершин из n − k мы выбираем, и вот это уже в итоге получается то, чего нам нужно.
Так, ну это еще не все, потому что мы таким образом лишь зафиксировали вершины
для наших двух пересекающихся копий, но надо еще зафиксировать ребра, правильно?
То есть надо выбрать, как именно расположена копия графа H на
первом множестве, которое мы вот здесь вот выбирали одним из стольких способов,
и затем еще зафиксировать, как именно выбираются ребра на второй части.
Ну, понимаете, товарищи, нам-то нужно сейчас доказать, что все вот это
суммирование, будучи там на что-то поделенным (сейчас я напомню на что),
стремится к нулю при n, стремящемся к бесконечности.
Ну и очередная радость аналитическая состоит в том,
что нам вовсе необязательно знать, чему равняется это количество способов.
Мы обозначим его как-нибудь B от (k,
l) — по аналогии с тем, как мы вводили обозначение A от (k, l).
Значит, это просто, повторяю, B от (k, l) — это просто количество
способов на уже фиксированных 2k − t вершинах, видите, здесь 2k − t вершин.
Вот на этих фиксированных 2k − t вершинах как-то еще там расположить копии графа H.
Все равно это величина, которая от n никак зависеть не будет, это величина,
которая зависит только от k и от l.
Вот.
Ну и все, а теперь надо умножить на нашу верхнюю оценку вероятности,
это p в степени 2l − lt поделить на k,
lt поделить на k, вот такая вот штука у нас получилась.
Правильно?
Вроде правильно.
lt поделить на k.
Да, да-да-да-да, именно такая штука у нас и получилась, конечно, конечно, конечно...
Замечательно, но это вот верхняя оценка для двойного суммирования,
это верхняя оценка для двойного суммирования, а нам хочется доказать,
что ведь не она стремится к нулю, а дробь стремится к нулю,
если мы всю вот эту вот верхнюю оценку поделим на
величину C из n по k в квадрате на p в степени 2l.
Ну это ж замечательно, друзья,
мы с вами сегодня уже не раз писали соответствующие асимптотики.
Во-первых, вот это благополучно шлёп-шлёп, тут никаких 2l не остается,
а остается просто p в степени −lt поделить на k.
Дальше, какие асимптотики мы писали?
Ну давайте я перепишу это вот так: я напишу,
что это сумма по t от 1 до k, а вот здесь,
под знаком суммирования, буду писать соответствующие дроби.
Во-первых, видно, что...
ой, как же я не заметил сразу.
Вот эти еще шлёп-шлёп, то есть вот этот квадрат сокращается вот с этим C из n по
k, тут даже никаких асимптотик знать не надо, просто сокращается и все.
Так, чудесно, чудесно, так, так, так, так, так, так, так, так...
Так, так, так...
Ну давайте напишем, ладно.
C из k по t на B от (k, l) — это все фигня,
это все константы, они ни на что не влияют вообще.
Сейчас мы этим воспользуемся, не будем их переписывать дальше.
Так, здесь у нас остается C из n − k по k − t на p в
степени −lt, деленное на k.
А в знаменателе каждого из слагаемых благополучно выжило только C из n по k.
И вот нам нужно доказать, что такая сумма стремится к нулю.
Хе! Но я повторяю, вот эти вот штуковины,
это константы: что C из k по t там, что C из k по 1, что C из k по k.
Ну, как хотите, я могу оценить, например, это как 2 в степени k.
Понятно, что C из k по t меньше, чем 2 в степени k при абсолютно любом t.
Это какая-то тривиальная оценка, вытекающая из того,
что сумма всех биномиальных коэффициентов — это уж в точности 2 в степени k.
Ну значит, каждый из них не превосходит 2 в степени k.
Но даже 2 в степени k — это константа, это фиксированная величина,
которая на стремление к нулю никакого влияния не оказывает вовсе.
Поэтому на вот это вот произведение мы благополучно можем,
как бы вам это сказать поприличней, это мы его можем забыть.
Да, мы его можем забыть, я вот все время как-то пытаюсь неприличные слова
произносить на лекциях, это нехорошо.
Вот, значит, мы можем его вообще не рассматривать никак,
оно не влияет на скорость стремления к нулю никоим образом.
Более того, смотрите, товарищи,
у нас ведь здесь фиксированное число слагаемых, всего k штучек.
Если мы докажем, что каждое из этих слагаемых, то есть, по сути,
вот эта величина, если мы докажем, что вот эта величина стремится к 0 при n,
стремящемся к бесконечности вне зависимости от того, чему равняется t,
то понятное дело, за счет фиксированности числа слагаемых,
мы тем самым получим, что и вся сумма стремится к нулю тоже.
Если бы вот это k могло от n зависеть, ну да,
там с ростом n могло бы набежать какое-то количество слагаемых,
и мы с вами в таких ситуациях как-то тоже побывали за время этого курса.
Но нет, все гораздо проще.
Андрей Райгородскийпрофессор, доктор физико-математических наук
Максим Жуковскийпреподаватель
