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
1713
Не больше $N$ одинаковых символов подряд? Хорошей формулы не будет.

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


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

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


14/11/21
156
Можно попытаться задействовать 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 ] 

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



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

Сейчас этот форум просматривают: Skipper


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

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