2014 dxdy logo

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

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




 
 Задачка по комбинаторике
Сообщение26.05.2011, 18:15 
Есть $n$ ячеек образующих кольцо. В каждой ячейке есть либо стрелка вверх, либо стрелка вниз (ячейки различимы, стрелки - нет). $s$ - число стрелок, торчащих вверх. И есть число согласованных пар ячеек - $p$ - т.е. это число соседних пар ячеек, ориентированных одинаково.
Например для такой конфигурации: (++--) - n=4, s=2, p=2
а для такой (+-+-) n=4, s=2, p=0 ну и для такой (-+--) n=4, s=1, p=2. (подразумевается, что ячейки образуют кольцо, поэтому надо учитывать и "согласованность" первой и последней стрелки).
В чем, собственно вопрос: пусть фиксированы числа n,s,p т.е. задано кол-во ячеек, сколько стрелок торчит вверх (и автоматически сколько вниз), число согласованных пар (и автоматически число противоположных пар). Сколькими различными способами можно реализовать эти числа (s,p при фиксированном n)? (Способы одинаковы если в каждой ячейке совпадают стрелки, в других случаях - различны)

Ясно, что всегда будет произвол в том, что можно циклически сдвигать ячейки, например (-+--) и (--+-) имеют одинаковые n,s,p (n=4, s=1, p=2). Сперва я даже думал что кроме произвола циклического сдвига ничего не остается, однако, например (++-++-) и (+++-+-) имеют одинаковые n,s,p (n=6, s=4, p=2) но не различаются лишь циклической перестановкой. В общем, хотелось бы найти аналитическую формулу, если это возможно.

 
 
 
 Re: Задачка по комбинаторике
Сообщение27.05.2011, 16:03 
Метод решения кажется рабочий, а расчеты надо провести заново и уточнить.
Вспомогательная, простая задачка:
Дано $m$ ящиков (различимых) $s$ предметов (неразличимых) $p$ согласованностей (согласованности между предметами считаются только внутри ящиков, т.е. два подряд единичных ящика дают в сумме ноль согласованностей между предметами). Найти число комопзиций предметов по ящимкам $P(m,s,p)$. Ответ у меня получился равным произведению одно биномиального коэффициента на другой.
Теперь решение исходной задачи получается типа такого (формула иллюстративная, поэтому привожу ее полностью)
$$S(n,s,p)=2\left(\sum\limits_{m<n;  p_1+p_2=p}P(m,s,p_1)P(m,n-s,p_2)+\sum\limits_{m<n;  p_1+p_2=p-1}P(m,s,p_1)P(m-1,n-s,p_2)\right)$$
Пояснение:
Разомкнем круг, и будем решать задачу для цепочки- это почти не меняет задачу, надо лишь учесть одну согласованность в конце либо ее отсутствие (обсчитать два случая отдельно). Положим так же, для упрощения, что цепь начинается с минуса (а потом домножим на двойку, чтобы учесть и цепи начинающиеся с плюса).
На четных местах у нас стоят серии из +++ на нечетных местах серии из ---. Поэтому для фиксированных $p_1+p_2=p$ и $m$ число вариантов есть произведение числа вариантов минусовых серий на число вариантов плюсовых. В конце остается суммировать по разным $m$ и $p_1+p_2=p$.

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group