На окружности выбрано n точек. сколько существует вариантов соединения этих точек, если они не пересекаются?

225

365

Посмотреть ответы 2

Ответы на вопрос:

ZolotoNaMoeyShee

Геометрия

4,8(24 оценок)

Вроде придумал решение. пусть число способов соединить n точек на окружности равно f(n). пронумеруем точки на окружности от 0 до n-1. возьмем точку n-1. рассмотрим два непересекающихся случая: 1) она не имеет у себя пары. тогда число способов это устроить равно f(n-1) 2) она имеет себе пару. теперь происходит выбор кандидатов. пусть ее пара точка 0. тогда число способов это устроить равно f(количество точек между 0 и n-1 в одном направлении) * f(количество точек между 0 и n-1 в другом направлении) = f(0)*f(n-2). то есть мы этим отрезком разбиваем все множество точек на две половины, считаем ответ на каждой половине, а потом по правилу произведения их умножаем. дальше ее парой может быть точка 1. поступаем аналогично, здесь будет f(1)*f(n-3), так как в одном направлении лишь точка 0, в другом направлении точки 2,-2. аналогично рассуждаем и доходим до f(n-2)*f(0). суммируем получившиеся способы и получаем: f(n) = f(n-1) + f(0)*f(n-2)+f(1)*f(n-3)+..+f(n-3)*f(1)+f(n-2)*f(0). начальные значения: f(0) = f(1) = 1, f(2) = 2 (мы можем соединять или не соединять две точки) по этим данным можно находить f(3), f(4) и т. д. для f(3) = f(2) + f(0)*f(1) + f(1)*f(0) = 2 + 1 + 1 = 4. перечислим эти способы: 1) ничего не связано 2) связаны только 0, 1 3) связаны только 0, 2 4) связаны только 1, 2