Число вариантов соединения точек некоторым кол-вом отрезков

[layer19]

Пусть $N$ — количество различных точек на некоторой прямой $k$, $L$ — количество различных отрезков, которые можно использовать для соединения двух произвольных точек. Чему, в общем случае, равно число вариантов $M$ соединения точек данным количеством отрезков, если в каждом варианте каждая точка должна принадлежать концу хотя бы одного отрезка? Необходимо представить формулу $M=f(N, L)$ с доказательством. На рисунке представлены некоторые тривиальные случаи с эмпирическим выводом $M$ (отрезки показаны кривыми $l$).

Собственные попытки решения задачи:

1. Тот факт, что точки принадлежат прямой, не выглядит существенным, но, возможно, намекает на метод поиска решения (оно может быть геометрическим, комбинаторным или другим).
2. Вероятно, $M \leqslant \frac {N\cdot(N-1)} 2$, т.к. правая часть есть общее число вариантов соединения $N$ произвольных точек отрезками. Гипотеза опровергается эмпирической проверкой для $N=5, L=3$.
3. Есть интуиция, что решение может быть как-то связано с построением системы Штейнера вида $(?, 2, N)$.

4. Эмпирический способ решения задачи:
4.1. Каждый отрезок $l_i, i \in \left\{1, 2, ..., L\right\} $ можно обозначить вектором $v_i$ длины $N$: $v_i=[p_1, p_2, ..., p_N], p_j \in \left\{0, 1\right\}, j \in \left\{1, 2, ..., N\right\}$. Каждый элемент $p_j$ показывает принадлежность исходной точки под номером $j$ данному отрезку. Будем рассматривать $v$, в которых только некоторые два элемента $p$, определяющие концы отрезка, равны 1. Имеем ${N \choose 2}$ таких векторов.
4.2. Получается, из такого количества векторов $v$ мы можем составить ${{{N \choose 2}} \choose L}$ сумм. Проходя через все эти варианты, мы оставляем только те $M$ сумм из них, в которых каждый элемент результирующего вектора равен или превосходит 1.

[Pphantom]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Jnrty]

Jnrty:

И ещё: формулы оформлены неправильно. Как правильно — написано в двух темах, ссылки на которые есть слева от окна редактирования.
У Вас пока всё просто: нужно убрать теги форматирования [ b][ /b] и [ i][ /i], и вокруг каждой формулы, включая однобуквенные, написать знаки доллара. Внутри формулы знаков доллара быть не должно. Например, вместо L должно получиться $L$.

Например, вместо [i][b]L[/b][/i] должно получиться $L$.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[layer19]

Гипотеза 2 опровергается эмпирической проверкой для $N=5, L=3$:

$(1-2, 3-4, 5-1)$
$(2-3, 4-5, 1-2)$
$(1-2, 4-5, 3-1)$
$(1-3, 4-5, 2-4)$
$(1-2, 3-4, 5-2)$
$(2-3, 4-5, 1-3)$
$(1-2, 4-5, 3-5)$
$(1-3, 4-5, 2-5)$
$(1-2, 3-4, 5-3)$
$(2-3, 4-5, 1-4)$
$(1-2, 3-4, 5-4)$
$(2-3, 4-5, 1-5)$
$ . . . $

Здесь уже $M > \frac {N\cdot(N-1)} 2$

[waxtep]

layer19, $M$ будет расти с ростом $N$ заметно быстрее; чтобы оценить масштаб, попробуйте рассмотреть частный случай $N=2L$, где получить формулу для $M$ из комбинаторных соображений довольно просто

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»