Сколько треугольников можно составить из вершин правильного

[gris]

Ах, как бы я хотел почитать в вашем изложении что-нибудь захватывающее про убивающие пространства...
Кстати, дозвольте коснуться одного момента: а почему мы делим на шесть? Все перестановки равноправны, да. И что? А то, что при нашем методе подсчёта мы неизбежно получаем каждый треугольник шесть раз. Каждая вершина многоугольника выбирается два раза как первая, два как вторая, три как третья.
Не всегда так бывает. Вот было предложено посчитать количество треугольников с возможными соседними вершинами. Это сделать несложно, но обратите внимание, что в таких треугольниках вершины неравноправны и в зависимости от способа подсчёта определённый треугольник мы можем посчитать шесть раз, а можем и два, или три. Попробуйте!

[nothingg]

gris в сообщении #1561604 писал(а):

Ах, как бы я хотел почитать в вашем изложении что-нибудь захватывающее про убивающие пространства...
Кстати, дозвольте коснуться одного момента: а почему мы делим на шесть? Все перестановки равноправны, да. И что? А то, что при нашем методе подсчёта мы неизбежно получаем каждый треугольник шесть раз. Каждая вершина многоугольника выбирается два раза как первая, два как вторая, три как третья.
Не всегда так бывает. Вот было предложено посчитать количество треугольников с возможными соседними вершинами. Это сделать несложно, но обратите внимание, что в таких треугольниках вершины неравноправны и в зависимости от способа подсчёта определённый треугольник мы можем посчитать шесть раз, а можем и два, или три. Попробуйте!

Извините, что убил место в моем комментарии. Я постараюсь написать комментарий более четко.

Я думаю, что мы должны разделить это на шесть, потому что каждый треугольник повторяется 3 раза для 3 его вершин и 2 раза для каждой из его вершин, тогда в сумме он повторяется $3\times2 = 6$.

Я хочу спросить, почему каждая вершина многоугольника выбрана дважды как первая, дважды как вторая, трижды как третья. Я не очень понимаю это.

Кроме того, я хочу, чтобы мне объяснили больше о треугольников с возможными соседними вершинами. Я думаю, что это треугольники, у которых 1 или 2 стороны совпадают с многоугольником, верно?

[gris]

Я имел в виду, что при подсчёте всех хороших треугольников мы пользуемся некоторым методом. Для теоретических расчётов часто проще организовать сквозной просчёт, при котором могут быть повторения.
Например. Рассмотрим семиугольник и пронумеруем его вершины по часовой стрелке начиная с одной, выбранной раз и навсегда. Треугольники будут изображаться тройками вида $(1, 4, 6)$. По вашему желанию треугольники, отличающиеся порядком вершин, считаются эквивалентными. При нашем методе подсчёта мы учитываем озвученный треугольник шесть раз: два раза считая $<1>$ первой вершиной, два раза второй и два раза третьей. То есть занося в счёт треугольники $(1,4,7), (1,7,4),(4,1,7),(4,7,1),(7,1,4),(7,4,1)$.
Разумеется, при определении числа хороших треугольников все эти дела скрыты под простым умножением на количество способов разместить первую вершину на количество способов разместить вторую при уже размещённой третьей и т.д. Но мы должны быть уверены в том, что все хорошие треугольники учтены и при этом по одинаковому количеству раз. Можно подсчитывать, например, упорядоченные хорошие треугольники. Тогда формулы определения количества способов могут усложниться, мы получим проигрыш в наглядности, а кому это нужно?
А вот кому. Предположим, вы хотите организовать компьютерный перебор треугольников в выпуклом стоугольнике, заданном координатами вершин на плоскости. И для каждого треугольника посчитать его площадь, а потом найти среднюю. Площадь треугольника не зависит от порядка вершин, и наш метод перебора задаст компьютеру лишнюю работу. Только перейдя к упорядоченным тройкам, мы сократим время расчётов в шесть раз. Я уж не говорю о более тонких методах оптимизации. А вот если надо считать не площадь, а, скажем, нечто, зависящее от порядка вершин, то тут уже придётся перебирать всё.
Ах, да. Вот пример с подсчётом треугольников с соседними вершинами aka треугольниками, у которых есть стороны, совпадающие со стороной многоугольника. Тут вы можете зафиксировать первую вершину, вторую выбрать сразу за ней, а третью как получится, за исключением одного места. Прогнать первую вершину по кругу. Убедитесь, что все хорошие треугольники посчитаны и ровно по одному разу. И на ничего делить не нужно. Хотя при вычитании из формулы всех треугольников надо домножить ЧиЗ на 6.

У меня к вам просьба. Не цитируйте длинные сообщения целиком. Ибо длинные цитаты затрудняют чтение и отягощают работу индексирующих ботов. И лишнее место занимают на физических устройствах. Впрочем, это суждение профана:(

[nothingg]

gris в сообщении #1561617 писал(а):

У меня к вам просьба. Не цитируйте длинные сообщения целиком. Ибо длинные цитаты затрудняют чтение и отягощают работу индексирующих ботов. И лишнее место занимают на физических устройствах. Впрочем, это суждение профана:(

Хорошо!

gris в сообщении #1561617 писал(а):

Ах, да. Вот пример с подсчётом треугольников с соседними вершинами aka треугольниками, у которых есть стороны, совпадающие со стороной многоугольника. Тут вы можете зафиксировать первую вершину, вторую выбрать сразу за ней, а третью как получится, за исключением одного места. Прогнать первую вершину по кругу. Убедитесь, что все хорошие треугольники посчитаны и ровно по одному разу. И на ничего делить не нужно. Хотя при вычитании из формулы всех треугольников надо домножить ЧиЗ на 6.

Следуя этой идее, есть 1 способ выбрать первую вершину и вторую вершину в каждом случае, потому что мы фиксируем первую вершину и выбираем вторую сразу после нее. Мы проедем первую вершину из вершины $1$ в вершину $n$ по часовой стрелке. В каждом случае у нас будет $n-3$ способа выбрать третью после исключения двух выбранных вершин и вершины, которая является первой вершиной в предыдущем случае. В случае вершины $1$ исключенной вершиной является вершина $n$ из-за направления по часовой стрелке. После каждого случая мы добавляем результат каждого случая к общему результату всех $n$ случаев. Итак, количество треугольников, у которых хотя бы одна сторона совпадает с многоугольником, равно:

$$n\times(n-3)$$

Я думаю, что это интересный пример об эффективности использования упорядоченных треугольников вместо перечисления всех.

Благодарю вас!

[мат-ламер]

Я так понял, что по второй задаче проблема состоит в том, как проще описать решение. Для начала задачу упростим и попробуем найти ответ для случая, когда одна вершина жёстко фиксирована. Ответ тут будет $\frac{(n-4)(n-5)}{2}$ . Затем результат умножим на количество вершин и учтём, что в нашем подсчёте каждый треугольник будет учитываться три раза.

[nothingg]

мат-ламер в сообщении #1561661 писал(а):

Я так понял, что по второй задаче проблема состоит в том, как проще описать решение. Для начала задачу упростим и попробуем найти ответ для случая, когда одна вершина жёстко фиксирована. Ответ тут будет $\frac{(n-4)(n-5)}{2}$ . Затем результат умножим на количество вершин и учтём, что в нашем подсчёте каждый треугольник будет учитываться три раза.

Можете ли подробнее объяснить, почему ответ для случая, когда одна вершина жестко закреплена, равен $\frac{(n-4)(n-5)}{2}$? И почему в нашем расчете каждый треугольник будет учитываться трижды?

[мат-ламер]

nothingg в сообщении #1561686 писал(а):

Можете ли подробнее объяснить, почему ответ для случая, когда одна вершина жестко закреплена, равен $\frac{(n-4)(n-5)}{2}$?

1. Найдите, сколько треугольников, когда она вершина фиксирована, а две остальные вершины не являются соседними к фиксированной. Это число равно количеству способов выбрать две вершины из $n-3$ вершин.
2. Найдите, сколько треугольников, когда она вершина фиксирована, а две остальные вершины не являются соседними к фиксированной, но являются соседними друг к другу.
3. Вычтите из первой величины вторую.

nothingg в сообщении #1561686 писал(а):

И почему в нашем расчете каждый треугольник будет учитываться трижды?

Первый раз, когда первая вершина треугольника фиксирована, второй раз ...

[мат-ламер]

мат-ламер в сообщении #1561687 писал(а):

1. Найдите, сколько треугольников, когда она вершина фиксирована, а две остальные вершины не являются соседними к фиксированной. Это число равно количеству способов выбрать две вершины из $n-3$ вершин.
2. Найдите, сколько треугольников, когда она вершина фиксирована, а две остальные вершины не являются соседними к фиксированной, но являются соседними друг к другу.
3. Вычтите из первой величины вторую.

Ну, это я слишком сложно замутил. Проще считать, что вторая и третья вершина может находиться рядом, но число вершин в многоугольнике уменьшено на единицу. То есть надо найти число способов выбрать две вершины из $n-4$ вершин.

[nothingg]

мат-ламер в сообщении #1561687 писал(а):

1. Найдите, сколько треугольников, когда она вершина фиксирована, а две остальные вершины не являются соседними к фиксированной. Это число равно количеству способов выбрать две вершины из $n-3$ вершин.
2. Найдите, сколько треугольников, когда она вершина фиксирована, а две остальные вершины не являются соседними к фиксированной, но являются соседними друг к другу.
3. Вычтите из первой величины вторую.

Первый раз, когда первая вершина треугольника фиксирована, второй раз ...

Вау, я понял это!

мат-ламер в сообщении #1561700 писал(а):

Ну, это я слишком сложно замутил. Проще считать, что вторая и третья вершина может находиться рядом, но число вершин в многоугольнике уменьшено на единицу. То есть надо найти число способов выбрать две вершины из $n-4$ вершин.

Да, я думаю, что этот способ проще.

Спасибо!