Комбинаторная задача

[R_e_n]

Добрый день. У меня такая задача. Есть линия из $N$ клеточек. И есть $m$ красок. Каждой краской с номером $i$ нужно закрасить $n_i$ клеточку. Красится сразу непрерывная линия. Красить уже закрашенные клеточки нельзя. Все краски различные. Нужно посчитать сколькими способами это можно сделать.

Пример, пусть четыре клеточки и две краски, пусть синяя и зеленая, $n_1=2$, $n_2=2$ Ответ: 2. либо красим сначала две синие потом две зеленые либо наоборот.
Пример 2, пусть теперь $n_1=3$, $n_2=2$. В этом случае ни одним способом покрасить нельзя.

Что то у меня никаких идей по поводу решения.

[Shtorm]

R_e_n, так формула же количество размещений! Или что-то не так?
Тут конечно, должно быть $N<m$.
Нет стоп, что-то я не понял: если линия должна быть закрашена вся, причём каждая клеточка должна быть закрашена своей краской, отличной от других, то $N=m$? Или я что-то не так понял?

[R_e_n]

Shtorm в сообщении #843698 писал(а):

Нет стоп, что-то я не понял: если линия должна быть закрашена вся, причём каждая клеточка должна быть закрашена своей краской, отличной от других, то $N=m$? Или я что-то не так понял?

Нет, линия не должна быть закрашена вся

Приведу еще один пример:
Пусть есть 5 клеточек, две краски, $n_1=2$ и $n_2=2$. Тогда есть варианты:
синей красим клетки [1,2] зеленой или [3,4] или [4,5]
синей красим клетки [2,3] зеленой [4,5]
синей красим клетки [3,4] зеленой [1,2]
синей красим клетки [4,5] зеленой или [1,2] или [2,3]

Итого 6 вариантов.

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

[Shtorm]

R_e_n, тогда я у Вас уточню ещё раз сам для себя: имеется $m$ различных красок и имеется $N$ клеток. Причём $N \ne m$. Так? Закрасить надо так, что бы каждая клеточка была покрашена в свой собственный цвет, отличный от других, так? Если Вы говорите, что клеточки не должны быть все закрашены, то $m<N$, так? А могут ли тогда пустые незакрашенные клетки оставаться между закрашенными?

[Shtorm]

R_e_n, а! Так необходимо обязательно каждый раз 2 клетки красить одним цветом?

[AV_77]

Пусть $n = n_1 + n_2 + \ldots + n_m$ - число закрашенных ячеек, $T = N - n$ - число не закрашенных ячеек. Тогда вместо $N$ ячеек можно рассматривать $T + m$ ячеек, а закрашивается каждой краской по одной ячейке. В этом случае некоторые ячейки будут "крупные", но роли это не играет.

[R_e_n]

Shtorm в сообщении #843711 писал(а):

R_e_n, тогда я у Вас уточню ещё раз сам для себя: имеется $m$ различных красок и имеется $N$ клеток. Причём $N \ne m$. Так? Закрасить надо так, что бы каждая клеточка была покрашена в свой собственный цвет, отличный от других, так? Если Вы говорите, что клеточки не должны быть все закрашены, то $m<N$, так? А могут ли тогда пустые незакрашенные клетки оставаться между закрашенными?

$m<N$ точно, но $n_1+n_2+..+n_m$ может быть как больше (пример 2) так и меньше $N$
Клетка красится один раз, но может и вообще остаться не покрашенной.
Да клетки могут между непрерывными линиями быть не покрашенными

[R_e_n]

Shtorm в сообщении #843716 писал(а):

Так необходимо обязательно каждый раз 2 клетки красить одним цветом?

Нужно последовательно покрасить $i$ цветом $n_i$ еще не закрашенных в другой цвет клеток

-- 31.03.2014, 19:52 --

AV_77 в сообщении #843718 писал(а):

Пусть $n = n_1 + n_2 + \ldots + n_m$ - число закрашенных ячеек, $T = N - n$ - число не закрашенных ячеек. Тогда вместо $N$ ячеек можно рассматривать $T + m$ ячеек, а закрашивается каждой краской по одной ячейке. В этом случае некоторые ячейки будут "крупные", но роли это не играет.

Да, все правильно, большое спасибо.