2014 dxdy logo

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

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



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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Комбинаторная задача
Сообщение31.03.2014, 18:12 


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

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

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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:24 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:32 


12/10/12
132
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 вариантов.

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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:37 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:38 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:39 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:42 


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


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

 Профиль  
                  
 
 Re: Комбинаторная задача
Сообщение31.03.2014, 18:44 


12/10/12
132
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$ ячеек, а закрашивается каждой краской по одной ячейке. В этом случае некоторые ячейки будут "крупные", но роли это не играет.


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

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

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



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

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


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

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