Комбинаторика. Разбиения плоскости.

[bgm313]

Всем привет. Попалась задача:
Найти количество частей на которые разбивается плоскость n прямыми, причём никакие 2 прямые не параллельны и никакие 3 не пересекаются в 1 точке.
Трудность возникает при подсчёте закрытых частей плоскости.
Вопрос:
1)Если знать число точек пересечения и число треугольников, можно ли сказать ответ на эту задачу?
2)Как подсчитать число закрытых частей?

[ewert]

Допустим, это количество для $n$ прямых у Вас есть. Сколько добавится кусков, если наложить дополнительно $(n+1)$-ю прямую? Выпишите это рекуррентное уравнение и решите его.

[maxal]

Используйте Эйлерову характеристику.

[V.V.]

maxal в сообщении #604100 писал(а):

Используйте Эйлерову характеристику.

По индукции быстрее.
Хотя по формуле Эйлера интереснее, да.

[ewert]

(Оффтоп)

V.V. в сообщении #604219 писал(а):

Хотя по формуле Эйлера интереснее, да.

Возможно, судить не берусь; но безыдейнее -- да. Ведь про ту характеристику надо ещё и знать, ну как минимум об её существовании.

[V.V.]

(Оффтоп)

Формула Эйлера: В-Р+Г=2. Знают очень многие.

[Mathusic]

bgm313 в сообщении #604050 писал(а):

причём никакие 2 прямые не параллельны и никакие 3 не пересекаются в 1 точке.

Это условие можно заменить на "всякие 2 пересекаются в одной точке".

Для двумерного пространства -- ответ $\Omega_2(n)=1+C^2_n$, для одномерного -- $\Omega_1(n)=n+1$

Для $\mathbb{R}^3$ можно обобщить, так, например: всякие три плоскости пересекаются по в одной точке? Что в ответе будет?

[Someone]

Mathusic в сообщении #604284 писал(а):

bgm313 в сообщении #604050 писал(а):

причём никакие 2 прямые не параллельны и никакие 3 не пересекаются в 1 точке.

Это условие можно заменить на "всякие 2 пересекаются в одной точке".

Нельзя.

Mathusic в сообщении #604284 писал(а):

Для двумерного пространства -- ответ $\Omega_2(n)=1+C^2_n$

Неверно.

[ewert]

(Оффтоп)

V.V. в сообщении #604280 писал(а):

Формула Эйлера: В-Р+Г=2. Знают очень многие.

Во-первых, не совсем так. Во-вторых, в стандартных курсах этого не проходят (в отличие от арифметической прогрессии), и знать это для данной задачи даже и вредно.

bgm313 в сообщении #604050 писал(а):

2)Как подсчитать число закрытых частей?

Вычесть из общего количества кусков очевидное количество бесконечных.

[Mathusic]

Someone в сообщении #604285 писал(а):

Неверно.

А, ну опечатка, конечно, должно быть: $\Omega_2(n) = 1 + C^2_{n+1}$

Someone в сообщении #604285 писал(а):

Mathusic в сообщении #604284 писал(а):

bgm313 в сообщении #604050 писал(а):

причём никакие 2 прямые не параллельны и никакие 3 не пересекаются в 1 точке.

Это условие можно заменить на "всякие 2 пересекаются в одной точке".

Нельзя.

В виду имелось: "Всякие 2 прямые пересекаются ровно в одной точке..." Стоп! опять неверно, получается не то, что хочется сказать. Ох уж этот естественный язык
Давайте тогда так.
Определим
степень точки на плоскости есть количество различных прямых, проходящих через неё.

Тогда условие исходной задачи переформулируется так:
"Найти количество областей, на которые плоскость разбивается $n$ прямыми, всякие $2$ из которых пересекаются в точке степени $2$."

[Someone]

Mathusic в сообщении #604378 писал(а):

А, ну опечатка, конечно, должно быть: $\Omega_2(n) = 1 + C^2_{n+1}$

Да, теперь верно.

Mathusic в сообщении #604378 писал(а):

Определим
степень точки на плоскости есть количество различных прямых, проходящих через неё.

[Mathusic]

Someone в сообщении #604405 писал(а):

Mathusic в сообщении #604378 писал(а):

Определим
степень точки на плоскости есть количество различных прямых, проходящих через неё.

Да всё ж элегантно выходит
По аналогии определим степень точки в $s$-мерном пространстве.

Степень точки в пространстве размерности $s \geqslant 2$ -- это количество различных гиперплоскостей (плоскостей с размерностью направляющего пространства $(s-1)$), проходящих через эту точку.
Замечание. Естественно, что через любую точку в пространстве проходит бесконечно много гиперплоскостей. В определении участвуют только "выделенные" нами гиперплоскости, то есть те, которые мы взяли в рассмотрение.

Давайте пока для случая $s=3$ сформулируем задачу:
Найти количество областей $\Omega_3(n)$, на которые пространство разбивается $n \geqslant 3$ плоскостями, всякие три из которых пересекаются в точке степени $3$.

[Mathusic]

Mathusic в сообщении #604427 писал(а):

Давайте пока для случая $s=3$ сформулируем задачу:
Найти количество областей $\Omega_3(n)$, на которые пространство разбивается $n \geqslant 3$ плоскостями, всякие три из которых пересекаются в точке степени $3$.

Вот этот похожий топик topic61588.html заставил меня вернуться к этой задаче.

В итоге получился неожиданно красивый ответ

$$\Omega_3(n)=C^3_n+C^2_n+C^1_n+C^0_n=\frac{(n^2-1)n}6+(n+1).$$

С другой стороны, $\Omega_2(n)=1+C^2_{n+1}=C^2_n+n+1$, а $\Omega_1(n)=n+1$ ($n$ точек разбивают прямую на $n+1$ отрезков)
Это позволяет сделать предположение, что для $s$-мерной задачи (там будут гиперплоскости) будем иметь формулу

$$\Omega_s(n)=C_n^0+C_n^1+C_n^2+\dots+C_n^s = \sum \limits_{i=0}^{s}{C_n^i} \quad (n\geqslant s)$$

Остаётся только ждать, чтобы действительно, кто-то это подсчитал (или хотя бы привёл источник, где упоминается эта задача и результат)

[Alexander Evnin]

В $s$-мерном пространстве выберем такую ось $Ox$, что проекции всех точек степени $s$ на эту ось попарно различны и положительны. Будем считать, что эта ось направлена "вверх".
Проведём гиперплоскость $x=0$. Пересечения $n$ гиперплоскостей с этой гиперплоскостью
дают случай меньшей размерности, и мы знаем, сколько частей $s$-мерного пространства пересекает наша гиперплоскость. А каждая из "незадетых частей" однозначно определяется своей нижней точкой. Сколько их? $C_n^s$.
Так что Ваша догадка верная!

[Mathusic]

Справедливость формулы следует по индукции из реккурентного соотношения, которое привёл VAL: $\Omega_k(n)=\Omega_k(n-1)+\Omega_{k-1}(n-1)$ post609236.html#p609236

Alexander Evnin
Из вашей формулы $\Omega_k(n)=\Omega_{k-1}(n)+C_n^k$ тоже следует, что верна. И я, почему-то, вам верю