Число разбиений в n-мере

Katty-e

Подскажите, сколько существует разбиений k точек в n-мерном пространстве на две части при помощи гиперплоскости ( то есть одна непустая часть точек должна лежать по одну сторону от не, вторая непустая - по другую ).
Ссылки приветствуются .

greekdom

А точки как расположены?

Dr_Jones

оочень резонный вопрос

Katty-e

Общее положение( никакие n не лежат в одной гиперплоскости ).

greekdom

А точки различимы или нет?

Katty-e

Да.

greekdom

Ну тода это пипец какойто.

WLAD28031939

ничего в голову не приходит.
и правда похоже на пипец...
может, и правда неразличимы?
тогда СУЩЕСТВЕННО проще!

Katty-e

Ответ напишите, поразмышляем.

WLAD28031939

хех, быстрый какой....
понять бы, что он, за ответ этот....

halithh

На уровне идеи, вероятно можно довести. F(k,n) - число разбиений n-мерного пространства c k точками.
Делаем по индукции. Пусть точка A отделима от остальных гиперплоскостью. Пусть ее координаты - (0,0,...,0). Построим проективную гиперплоскость. По условию все точки в этой гипереплоскости различны. По индукции, их можно разбить F(k-1,n-1) способами. Причем, если рассмотреть n-мерное пространство, то каждое такое разбиение можно продолжить 2 способами - в зависимости от того, куда попадет A. Таким образом, F(n,k) = F(n,k-1) + 1 + F(n-1,k-1).
Может быть я ошибаюсь.

WLAD28031939

хмм....
предположим, идея верна.
Дальше что?
решать двумерное рекуррентное соотношение? хорошо, хоть порядок первый....

filippov2005

Соотношение напоминает реккурентность для чисел сочетаний.

WLAD28031939

очень напоминает!

filippov2005

F(n, k) = -1 + C_k^n, например.

filippov2005

Вроде все правильно.
Ответ:

WLAD28031939

НЕПРАВИЛЬНО!

filippov2005

Что неправильно? Доказательство или ответ?
1 (отделяет выделенную точку) + 2 * F(n - 1, k - 1) (получаются из гиперплоскостей в проективном пространстве) + F(n, k - 1) (количество разбиений не учитывая выделенную точку) - F(n-1, k - 1) (эти учли два раза - один раз учитывая выделенную точку и один раз не учитывая). Насчет формулы - она вытекает из того что сумма числа последовательных чисел сочетаний с одинаковым нижним числом равна числу сочетаний с нижним числом на 1 больше.
Вот такое несколько сумбурное объяснение.

jordan922

акуеть можно ...
что такое гиперплоскость ?

greekdom


А что это?

NHGKU2

C_k^{2p}

greekdom

Напомни ка что у нас при 2p > k .

NHGKU2

я в смысл не вникал, но просто знаю, что это просто обозначение числа сочетаний такое есть:

обычно считается, что C_n^m=0 при m>n и m<0.

greekdom

Тода чёто както неясно.

WLAD28031939

Твоя формула неверна!
она работает при k <= n, этот случай и так частный.. интереснее, как ведёт себя эта функция при числе точек >> размерности!

filippov2005

Моя формула верна. Она работает и при k >= n (к слову сказать, при k - 1 <= n - ответ тривиален - 2^{k-1} - 1).
Скажи по существу, чем тебя не устраивает доказательство или приведи контрпример, пожалуйста. И еще просьба - Аня, можешь отвечать развернутее?

greekdom

Так чему равно число сочетаний при 2p > k

filippov2005

Это вообще-то offic.

Гиперповерхность, обобщение понятия обычной поверхности 3-мерного пространства на случай n-мерного пространства.
Обычно Г. задаётся одним уравнением F (x1,..., xn) = 0 между координатами.
Если в евклидовом n-мерном пространстве Г. задаётся одним линейным уравнением, то она называется гиперплоскостью
© 2001 Russ Portal Company Ltd.
© 2001 "Большая Российская энциклопедия"

В контексте этой задачи, под гиперплоскостью в пространстве размерности n, называется гиперповерхность размерности n-1, задающаяся линейным уравнением a1x1 + a2x2 + ... + anxn - b = 0, где a1, a2, ..., an, b - коэффициэнты, а (x1, x2, ..., xn) - координаты точки. Примеры гиперплоскостей: на прямой (евклидово пространство размерности 1) - точка, на плоскости - прямая, в трехмерном пространстве - плоскость.

filippov2005

нулю, как обычно. Т.е. при n >= k некоторые числа сочетаний в сумме становятся нулями. При n>= k-1 эти сумму можно посчитать - получится число независящее от n - 2^{k-1} - 1.

greekdom

Тоесть если размерность больше чем точек то число разбиений равно 0?

filippov2005

Нет. В этой сумме всегда будут ненулевые числа сочетаний с "маленьким" нижним числом. Надо не забывать, что в принятом в СССР обозначении (C_m^n) верхнее и нижнее число переставлены по сравнению с международным.

greekdom

А эти формулы для различимых точек, я так понимаю?

filippov2005

Да. Я не понимаю, как можно решать для неразличимых - всегда можно провести гиперплоскость, отделяющую сколько угодно точек Это не задача

greekdom

А кстати ща вдумался в это условие:
никакие n не лежат в одной гиперплоскости

И как это в двухмерии, никакие две точки не лежат на прямой

filippov2005

Точки имеют "общее положение": никакие m точек не лежат в гиперплоскти размерности m - 1. Например, никакие три точки не лежат на одной прямой.

filippov2005

Раз уж я взялся в этой теме объяснять все и вся , то буду последовательным. При n>= k-1 сумму считать не надо (я не выделял этот случай для универсальности ответа). Можно и так показать, что любое разбиение на два непустых подмножества можно получить с помощью разделяющей гиперплоскости. Покажем это.
Итак, в пространстве размерности n даны два непересекающихся множества A и B, в cумме в них не более n+1 точек общего положения.
Пусть в A - p точек, а в B - q. По условию p + q <= n + 1
Ясно что, если мы докажем утвержедние для случая p + q = n + 1, то оно будет верно и для p + q < n + 1. Далее считаем p + q = n + 1.
Одну из них т.О (пусть из A) назовем центром координат. Вектора, выходящие в остальные точки (радиус-векторы) по условию задачи линейны и независимы. Иначе все n + 1 точки лежат в одной гиперплоскости размерности n.
Введем систему координат с началом в точке О, первые p - 1 координатных векторов из A, остальные q из B. Рассмотрим гиперплоскость задающуюся уравнением x_p + x_{p+1} + ... + x_{n} = 0.5 (первые p - 1 коэффициэнтов - нули). Она будет искомой, т.е. будет разделять множества A и B. Точки из A будут лежать на плоскости x_p + x_{p+1} + ... + x_{n} = 0, из В - на x_p + x_{p+1} + ... + x_{n} = 1. Т.е. на параллельных ей плоскостях, лежащих по разные стороны от нее. Что и требовалось доказать.

greekdom

Точки имеют "общее положение": никакие m точек не лежат в гиперплоскти размерности m - 1. Например, никакие три точки не лежат на одной прямой.

Чёто я вообще непонимаю. Тогда никакие 4 точки не лежат на одной поверхности
Но как это можно выполнить в 2D?

filippov2005

Да, согласен с тобой - я был не точен
Надо так:
Точки имеют в пространстве размерности n "общее положение", если никакие m <= n точек не лежат в гиперплоскти размерности m - 1. Например, никакие три точки не лежат на одной прямой (для пространств размерности >= 2).
ЗЫ Может лучше go в Q3?

greekdom

Например, никакие три точки не лежат на одной прямой

Я ща повешуть.Как из условия
если никакие m <= n точек не лежат в гиперплоскти размерности m - 1

при n=2 ты можеш накладывать условие на 3 точки

z731a

успокойся m <= n+1

filippov2005

Блять, я чего-то совсем затупил. Сорри
m <= n + 1 точек не лежат в гиперплоскти размерности m - 1

filippov2005

Да, не очень у меня объяснять получается

greekdom

Прадолжаем разговор
Берём 4 точки в углах квадрата и считаем по формуле, получается 6 способов.
Я прав?

filippov2005

да
Надеюсь, ты заметил, что там подмножества должны быть непустые?

greekdom

Ну всё я поверил, тока непойму зачем -1 во 2й формуле?
Там типа при 4 точках в 3D получается 7?

filippov2005

Да. Кстати, я нашел у себя ошибку - когда k <= n + 1, то ответ 2^{k - 1} - 1. Потому что разбиение на пустое и все остальное недопустимо.
Оставить комментарий
Имя или ник:
Комментарий: