2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Найти количество возможных комбинаций, но с условием
Сообщение16.04.2024, 12:13 


16/04/24
1
Пытаюсь выделить формулу, которая позволит вычислить количество возможных неповторяющихся комбинаций в множестве с повторяющимися элементами, где каждый уникальный элемент не может образовывать одну последовательность (состоящую из этого уникального элемента) больше чем N раз. Т.е. между этими последовательностями обязательно должно быть хотя бы 1 иной уникальный символ или иная допустимая последовательность.

Например, существует множество с повторяющимися элементами $\left\lbrace1,1,1,1,1,9,9\right\rbrace$ . $ N = 2$.
В этом случае одна из правильных комбинаций будет выглядеть так: $\left\lbrace1,1,9,1,1,9,1\right\rbrace$,
а не правильная будет выглядеть так:$\left\lbrace1,1,9,9,1,1,1\right\rbrace$.

Известно общее количество не повторяющихся комбинаций: $\frac{S!}{\prod\limits_{1}^{2} Ei!}$, где S - количество позиций в множестве.
Еi - Количество вхождений в множество уникального элемента. Таким образом, расчет для нашего примера будет выглядеть так $\frac{7!}{5!\ast2!}=\frac{5040}{240}=21$

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

 Профиль  
                  
 
 Re: Найти количество возможных комбинаций, но с условием
Сообщение16.04.2024, 15:45 
Заслуженный участник


12/08/10
1677
Не больше $N$ одинаковых символов подряд? Хорошей формулы не будет.

 Профиль  
                  
 
 Re: Найти количество возможных комбинаций, но с условием
Сообщение16.04.2024, 18:02 
Заслуженный участник
Аватара пользователя


16/07/14
9151
Цюрих
Null, можно доказать сложность?
Я навскидку ничего известного к этому свести не могу (а decision версия вроде бы решается тривиально).

 Профиль  
                  
 
 Re: Найти количество возможных комбинаций, но с условием
Сообщение16.04.2024, 18:46 


14/11/21
141
Можно попытаться задействовать k-композиции:
3-композиции числа 5:
11 + 11 + 1 = 2 + 2 + 1 = 5
1 + 11 + 11 = 1 + 2 + 2 = 5
итд

2-композиции числа 5:
111 + 11 = 3 + 2 = 5
11 + 111 = 2 + 3 = 5

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

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



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

Сейчас этот форум просматривают: dgwuqtj, Ivan 09


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

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