2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Деление точек на непересекающиеся множества
Сообщение08.09.2021, 13:46 


21/05/16
4292
Аделаида
Пусть на окружности расположены $n$ пронумерованных точек. Подскажите, пожалуйста, как называется (или хотя бы дайте какую-нибудь статью с исследованием этого числа) количество способов выбрать из этих точек непересекающиеся множества из $a_1$, $a_2$, ..., и $a_k$ последовательных точек (к примеру, если $a_1=a_2=\ldots=a_k=1$, то это число - $n(n-1)\ldots(n-k+1)$, т.е. символ Похгаммера).

 Профиль  
                  
 
 Re: Деление точек на непересекающиеся множества
Сообщение11.10.2021, 17:48 
Аватара пользователя


12/10/16
637
Almaty, Kazakhstan
Скажите, пожалуйста, как пронумерованы точки на окружности: последовательно или хаотично.
И если, к примеру, количество точек на окружности $n=3$, то каков будет ответ на вопрос " количество способов выбрать из этих точек непересекающиеся множества из $a_1$, $a_2$, ..., и $a_k$ последовательных точек".
Тоже хочу разобраться, но не понял сути.
Сначала подумал что это просто разбиение числа $n$, но погуглив символ Похгаммера, во мне затаились смутные сомнения.

 Профиль  
                  
 
 Re: Деление точек на непересекающиеся множества
Сообщение11.10.2021, 19:21 
Заслуженный участник
Аватара пользователя


08/11/11
5940
Не знаю, как называется, но мне кажется, что оно выражается через число разбиений $n-a_1-\ldots-a_k$ на $k$ слагаемых. А именно, если зафиксировать порядок, в котором идут интервалы, и положение первого интервала, то дальнейшее определяется длинами промежутков между интервалами, единственное условие на которые -- чему равна их сумма.

 Профиль  
                  
 
 Re: Деление точек на непересекающиеся множества
Сообщение11.10.2021, 22:57 
Заслуженный участник
Аватара пользователя


08/11/11
5940
А, ну и разбиения здесь упорядоченные, поэтому получится просто биномиальный коэффициент (точнее, сочетания с повторениями, которые к нему сводятся).

Пусть $s=a_1+\ldots+a_k-k$. Тогда ответ будет видимо $(n-s)(n-s-1)\ldots(n-s-k+1)$ (ясно, что ответ не поменяется, если уменьшить $n$ и одно из $a$ на единицу). То есть ещё проще.

 Профиль  
                  
 
 Re: Деление точек на непересекающиеся множества
Сообщение12.10.2021, 08:04 


21/05/16
4292
Аделаида
Soul Friend в сообщении #1534604 писал(а):
Скажите, пожалуйста, как пронумерованы точки на окружности: последовательно или хаотично.

Неважно, важно то, что они различны.

g______d, допустим, $n=6$. Ваша формула даёт одинаковые числа в случаях $a_1=a_2=3$ и $a_1=2, a_2=4$. А это явно неправильно.

-- 12 окт 2021, 14:36 --

$s=4$, т.е. ваша формула говорит, что варианта 2. А на самом деле в одном случае их 3, а в другом 6.

 Профиль  
                  
 
 Re: Деление точек на непересекающиеся множества
Сообщение12.10.2021, 08:43 
Заслуженный участник
Аватара пользователя


08/11/11
5940
kotenok gav в сообщении #1534665 писал(а):
А это явно неправильно.


Как я понял задачу, в обоих примерах ответ 6, т. к. в первом посте формула предполагает, что сам набор множеств упорядочен. Другими словами, при $n=2$, $a_1=a_2=1$ способы $(\{1\},\{2\})$ и $(\{2\},\{1\})$ считаются разными, что даёт 6 вариантов при $n=6$, $a_1=a_2=3$.

Но моя формула всё равно неправильная. Я не в тот момент зафиксировал положение первого множества и испортил первый множитель.

Попробуем так:

$$
n (k-1)! \binom{n-a_1-\ldots -a_k+k-1}{k-1}=n(n-s-1)(n-s-2)\ldots(n-s-k+1).
$$

$n$ вариантов выбрать положение первого множества. $\binom{n-a_1-\ldots a_k+k-1}{k-1}$ вариантов выбрать набор длин промежутков на окружности между соседними множествами. Ещё $(k-1)!$ выбрать в каком порядке идут оставшиеся $k-1$ множеств.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group