Может ли быть, что из миллиона деревьев, построенных на 10 вершинах, не найдётся ни одной пары изоморфных?

задан 4 Июл '20 12:25

Там количество деревьев с точностью до изоморфизма равно 106. См. здесь. При желании, их можно даже перечислить. Дать грубую оценку сверху нетрудно: даже если брать корневые деревья с 9 рёбрами, то их не больше числа Каталана c(9)=4862. Или ещё более грубо: c(9) < 4^9 = 2^{18}=8^6 < 10^6.

(4 Июл '20 12:37) falcao

@falcao, спасибо! Там, конечно, задача была рассчитана на последнюю грубую оценку - просто как-то забылось её существование.

(4 Июл '20 13:03) ralfio

@ralfio: судя по подбору чисел, так и есть. Правда, в таких случаях полезно указывать, что изучали по этому поводу. Всё-таки оценка тут очень далека от оптимальной.

Снизу, кстати, тоже можно очень грубо оценить как n^{n-2}/n!. Эта величина растёт примерно как e^n, а реально рост там составляет порядка 2,99...^n, но это уже неэлементарно доказывается.

(4 Июл '20 13:38) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,870
×86
×11

задан
4 Июл '20 12:25

показан
322 раза

обновлен
4 Июл '20 13:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru