Сколько способов соединить 6 точек

Сколько существует способов соединить некоторые пары точек?

Сколько существует способов соединить некоторые пары точек так, чтобы из каждой точки выходила хотя бы одна линия?
Пример:
1) Для 3 точек (a,b,c) = <(a-b,c),(a-c,b),(b-c,a),(a-b-c)>= 4 способа
2) Для 4 точек = 41 способ

Есть догадки, что используются формулы комбинаторики, но к полному решению не подобрался.

Полный текст задачи с разбором второго примера во вложениях.

Соединить некоторые пары гвоздиков ниточками
Гвоздики. В дощечке в один ряд вбиты гвоздики. Любые два гвоздика можно соединить ниточкой.

Сколько существует способов
Сколько существует способов из колоды в 52 карты, если извлечь 10 карт, среди которых содержится.

Сколько существует способов расставить?
Есть три красных, четыре синих и пять зеленых вагончиков, из которых ему хочется собрать паровозик.

Сколько существует способов расстановки?
1)Числа 1, 2, . . . , 9 записывают в порядке возрастания. Сколько существует способов расстановки.

У меня мысля такая.
Рассмотрим функцию F(n) = количество графов на n помеченных вершинах без изолированных точек. (хороших)
F(1) = 0
F(2) = 1
Для любого хорошего графа на n вершинах можно построить хороший граф на (n+1) вершине следующим образом.
Добавляем вершину с пометкой (n+1) и соединяем ребрами с любым непустым набором из n вершин. Таких способов 2 n — 1
Получается как бы F(n+1) = F(n)*(2 n — 1)
Но штука в том, что хороший граф можно получить и из плохого. Что хорошо видно для случая n = 2
Была еще мысль рассмотреть функции G(n, k) = количеству графов с k изолированными вершинами (F(n) = G(n,0))
Но вот дальше я завял.

Добавлено через 36 минут
Программно можно попытаться решить задачу с помощью перебора. n = 3 — 2 6 вариантов, n = 4 — 2 10 , n = 5 — 2 15
На том брут-форс себя исчерпывает.
Но можно применить какие-нибудь ветви и границы, и продвинуться немного дальше.

Источник

Логическая задача помогите найти объяснение. Есть Есть 6 точек которые лежат ровно противоположно друг дгугу цель соеди

Есть 6 точек которые лежат ровно противоположно друг дгугу цель соединить нижние точки с верхними так, чтобы они не пересекались.
В примере 3 коттежда (верхние точки) и 3 внизу газ, свет, вода соедините нижние с коттедами, чтоб нижние (газ, свет, вода) те не пересеклись.
Мне кажется решение не возможно, объясните почему?
1 2 3
* * *

* * *
г в с
——
Решение не возможно
газ соединяем с 123
воду с 123
свет с 123
и всегда один из них пересекается.

Их нельзя соединить, можно соединить максимум 5 точек
На примере с тремя домиками и тремя колодцами, которые нужно соединить тропинками, я объясняю это так:

1) Если существует два домика и два колодца, то от каждого домика можно провести по тропинке к каждому колодцу так, чтоб они не пересекались, и эти два домика, два колодца и тропинки между ними образуют замкнутый четирехугольник.

2) По отношению к такому четырехугольнику любой третий домик или колодец находится или вне его границ, или в его пределах. При этом, находясь вне границ четырехугольника, от третьего домика невозможно проложить тропинку к любому третьему колодцу, который находится в пределах этого четырехугольника, без пересечения какой-либо из тропинок, образующих данный четырехугольник. И наоборот, от третьего домика, который находится в пределах замкнутого четырехугольника, невозможно провести тропинку к третьему колодцу, который находится вне пределов четырехугольника, без пересечения какой-либо из тропинок, образующих его.

3) Если существует больше двух колодцев, то обязательно будут существовать четырехугольники, в пределах которых будет находится хотя бы один колодец, и четырехугольники, вне границ которых будет находится хотя бы один колодец.

Исходя из данных свойств получается, что от третьего домика невозможно провести тропинку ко всем трем колодцам, чтобы они не пересекли хотя бы один четырехугольник.

Источник

Найти количество способов соединить точки

Задача: написать функцию, которая принимает на вход целое число точек и возвращает количество способов соединить эти точки. Отсутствие соединения между точками тоже считается за способ. Для 8 точек — ответ 64, для 2 точек — 2, для 3 точек — 8:

Решается как-то через графы. Проверка: для 991 точки — ответ 948726690

Прошу прощения, я вероятно недопонял условия. Вот сам текст исходной задачи:

Given a number of vertices, determine the number of ways these vertices can form a graph. The graph may be disjoint, so it is not necessary to connect all vertices.The answer may be very large, return its value modulo (10**9+7). Note: Two ways of drawing edges are considered different if at least one pair of vertices has a different connection or the number of edges is different.

Спасибо за эти решения:

раз просто кол-во, то пусть они стоят по кругу. я думаю, что число ребер n=int(X*(X-1)/2), и тогда sum(f(n)/f(n-k)/f(k) for k in range(n+1)) – splash58 2 часа назад

Существует 2^(n*(n-1)/2) произвольных графов с n вершинами. Есть ощущение, что задача недопоставлена. – MBo 1 час назад

Осталась проблема переполнения стека для больших чисел на входе функции, как я понимаю, надо как-то разбивать вычисление на этапы и на каждом этапе выполнять операцию вида res = res % M, где M = 1000000000 + 7

Вот такое решение работает, но не проходит по лимиту времени:

Источник

Сколько отрезков можно получить из N точек? Сколько различных треугольников можно получить из N отрезков?

Есть ли какие-то формулы, в которые можно поставить число N и получить ответ?

Все это мне необходимо для решения этой задачи:

На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна сторона которого лежит на оси Ох. Если таких треугольников нет, то вывести «таких нет»

• Вопрос задан более трёх лет назад
• 15339 просмотров

Из N точек можно получить N*(N-1)/2 различных пар (C из N по 2) Длины, возможно, будут разные, но это уже без знания конкретных точек не лечится.

Про треугольники аналогичная ситуация, но надо выбрать три отрезка — M*(M-1)*(M-2)/6, где M — количество отрезков. Если же надо просто количество треугольников из заданных точек, то их будет N*(N-1)*(N-2)/6.

Получается из соображений выбираем первую точку N способами, вторую — N-1, третью — N-2 (потому что предыдущие уже выбраны). Надо разделить на 6=3!, потому что каждую перестановку трёх точек получили ровно по разу.

Не очень понимаю, как это может в данной конкретной задаче.
Но точно поможет такое наблюдение: S=len*h/2, где len — длина основания, h — соответствующая высота. Т.к. основание лежит на Ox, надо найти длиннейший отрезок на этой оси (max-min) и самую далёкую от Ox точку, чтобы максимизировать высоту.

Источник

Сколько способов соединить 6 точек

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

Решение

Пусть a n – количество способов соединить 2 n точек на окружности n непересекающимися хордами. Ясно, что a 1 = 1 и a 2 = 2. Покажем, что
a n = a n –1 + a n –2 a 1 + a n –3 a 2 + . + a 1 a n –2 + a n –1 .
Фиксируем одну из данных 2 n точек. Хорда, выходящая из неё, делит окружность на две дуги, причём на каждой дуге расположено чётное число данных точек. Если на одной дуге расположено 2 k точек, то на другой – 2( n – k – 1) точек; эти точки можно соединить непересекающимися хордами (не пересекающими первую хорду) a n–k –1 a k способами. Осталось просуммировать по k от 0 до 2 n – 2.
Таким образом, . a 10 = 16796.

Ответ

Замечания

Из полученной рекуррентной формулы видно, что числа a_n – это числа Каталана. Общую формулу для их вычисления см. в задаче 60451.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	13
Год	1950
вариант
Класс	7,8
Тур	2
задача
Номер	4

Проект осуществляется при поддержке и .

Источник