Дано $%n$% точек на плоскости. Сколько можно построить $%m$%-угольников $%(m < n)$% с вершинами в заданных точках?

Обозначим каждую точку плоскости числами от $%1$% до $%m$%. Тогда имеем упорядоченную совокупность из $%m$% чисел: $%(a_1, ..., a_m)$%, где $%a_1, ..., a_m$% - вершины многоугольника, каждое $%a_i$% может принимать значения от $%1$% до $%n$%. Задача сводится к тому, чтобы найти всевозможные совокупности $%(a_1, ..., a_m)$%. Каждый элемент совокупности должен быть уникален (инъективное отображение). Первый член совокупности $%a_1$% можно выбрать $%n$% способами, второй $%(n-1)$% способами, третий - $%(n-2)$% способами. По правилу произведения: $%n\cdot...\cdot(n-m+1)$% - число всевозможных совокупностей. Теперь нужно учесть, что каждый многоугольник можно построить как по часовой стрелке, так и против нее. Например, $%(1,2,3,4)$% и $%(4,3,2,1)$% - это один и тот же четырех угольник. То есть каждый многоугольник дублируется. Значит, полученное число нужно поделить пополам: $%n\cdot...\cdot(n-m+1) / 2$%.

Но это не верно, на самом деле ответ $%[n]_m/2m = n\cdot...\cdot(n-m+1)/ 2m$%. Помогите, пожалуйста, разобраться.

задан 1 Июл '14 18:44

изменен 1 Июл '14 21:47

Deleted's gravatar image


126

спасибо вам :)

(1 Июл '14 22:56) Silence

falcao, вы можете, пожалуйста, продублировать ваше сообщение в качестве ответа, а то я не могу принять ответ :)

(26 Авг '14 18:55) Silence
10|600 символов нужно символов осталось
1

Задача не совсем точно поставлена. Здесь подсчитывается не число многоугольников, а число замкнутых ломаных. Это не одно и то же, потому что ломаные могут быть самопересекающимися. Тогда они не ограничивают многоугольник. (Например, если точки лежат в вершинах квадрата ABCD, то ACBDA не задаёт многоугольник.) Кроме того, надо сделать оговорку, что никакие три точки не лежат на одной прямой.

Объяснение ответа очень простое: дополнительное деление на $%m$% связано с тем, что ломаная замкнута, и её можно обходить с любой из $%m$% точек -- результат при этом окажется тем же самым.

ссылка

отвечен 1 Июл '14 20:03

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×846

задан
1 Июл '14 18:44

показан
929 раз

обновлен
26 Авг '14 23:23

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

по почте:

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

по RSS:

Ответы

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

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