2014 dxdy logo

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

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




 
 Вопрос по комбинаторике
Сообщение12.05.2006, 18:20 
Определим групу: \[
A = \{ 1,...,n\} 
\]
Теперь захотим построит подгрупы B, следующим образом:
\[
B \subseteq A
\]
\[
i \in B \Rightarrow \left\{ {i - 1 \in B{\text{  }} \vee {\text{  }}i + 1 \in B} \right\}
\]
Вопрос заключaетса в следующем: Сколько таких груп есть?

Рекурсивно вопрос решаетса не сложно:
\[
\begin{gathered}
  f_{(n)}  = f_{(n - 1)}  + f_{(n - 2)}  + f_{(n - 4)}  \hfill \\
  n \geqslant 4 \hfill \\
  f_{(0)}  = 1,f_{(1)}  = 1,f_{(2)}  = 2,f_{(3)}  = 4 \hfill \\ 
\end{gathered} 
\]
Где f_n это количество этих подгруп.

А вот теперь хотелось бы получит закрытую формулу для f_n.
Напрямую, т.е., принципом исключения, задача идёт очень туго...
Решить f_n через рекурсию не очень выходит. Не через линейные трансформации,
не через степенные ряды.
В обеих случаях приходим к полиному:
\[
x^3  - 2x^2  + x - 1 = 0
\]
У которого два комплексных корня и один вещественный корень.
Все трое уродливые...

Можэт у кого то есть идея?
Или можэт быть у него на самом деле нет нормальной формулы...

Thx

 
 
 
 
Сообщение12.05.2006, 19:21 
Не понятен подсчёт подгрупп.
Если решаете указанное линейное рекурентное соотношение: $f_n=f_{n-1}+f_{n-2}+f_{n-4}$ то в любом придёте к решению уравнения $x^4-x^3-x^2-1=(x+1)(x^3-2x^2+x_1)=0$ (корень -1 никуда не девается).

 
 
 
 
Сообщение12.05.2006, 19:55 
Подгрупы считаютса следующим образом:
\[
f_{(n)}  = f_{(n - 1)}  + g_{(n - 2)} 
\]
Где g_n говорит сколько подгруп есть если "n" можэт
участвовать одинь (при этом как будто нарушая правила).
Поэтому:
\[
g_{(n)}  = f_{(n - 1)}  + g_{(n - 1)} 
\]
Отсюда получаем (рекурсивно подставлая):
\[
f_{(n)}  = \left( {\sum\limits_{i = 0}^{n - 1} {f_{(i)} } } \right) - f_{(n - 2)}  + g_{(0)}  = \left( {\sum\limits_{i = 0}^{n - 1} {f_{(i)} } } \right) - f_{(n - 2)}  + 1
\]
Подставим \[
f_{(n - 2)} 
\] по этой жэ формуле, и получим результат.

А вот вопрос можно ли получит формулу для f_n всё равно
можэт пройти через рекурсию, но не стандартными
методами, а то как вы сами сказали получаетса этот полином...
Или можно как нибудь эти групы хитро подсчитать?

 
 
 
 
Сообщение13.05.2006, 04:10 
Кстати, другой метод получение той жэ самой формулы:
Если "n" не в групе, тогда есть \[
f_{(n - 1)} 
\] опций. Если
"n" и "n-1" в групе, тогда есть три опции: или брать "n-2"
вместе с "n-3", или только "n-2", без "n-3", или вообще
не брать "n-2": \[
f_{(n - 2)}  + f_{(n - 4)} 
\].
Нужно заметит: те опции когда "n-2"
не вклучаетса, посчитаны в: \[
f_{(n - 2)} 
\]

Вопрос остаётса, есть ли идеи?
Заранее спасибо...

 
 
 
 Re: Вопрос по комбинаторике
Сообщение13.05.2006, 05:29 
Аватара пользователя
sniffer писал(а):
Определим групу: \[
A = \{ 1,...,n\} 
\]
Теперь захотим построит подгрупы B, следующим образом:
\[
B \subseteq A
\]
\[
i \in B \Rightarrow \left\{ {i - 1 \in B{\text{  }} \vee {\text{  }}i + 1 \in B} \right\}
\]
Вопрос заключaетса в следующем: Сколько таких груп есть?

Как я понял вопрос не про группы, а про множества? Или же все-таки про группы, но тогда какая операция задана на A и B? Сложение по модулю n?

Для множеств задачу можно решить так:

"Пробегом" длины $l$ в $B$ назовем элементы $i,i+1,\dots,i+l-1\in B$ такие что, $i-1\not\in B$ и $i+l\not\in B$. По условию в $B$ не может быть пробегов длины меньше 2.

Пусть в $B$ имеется $k$ пробегов длин $x_1,\dots, x_k$, причем эти пробеги отсортированы в порядке возрастания стартового элемента. Пусть $y_0$ - число элементов $A$ до первого пробега, $y_1$ - число элементов $A$ между первым пробегом и вторым, ..., $y_k$ число элементов $A$ после последнего пробега. Тогда
$y_0 + x_1 + y_1 + x_2 + \dots + x_k + y_k = n$
причем $x_i\geq 2$ и $y_0\geq 0$, $y_1\geq 1$, ..., $y_{k-1}\geq 1$, $y_k\geq 0$.
Нетрудно также понять, что любой набор $x_i$, $y_j$ удовлетворяющий указанным условиям задает некоторое подмножество $B$ удовлетворяющее условиям задачи.
Таким образом, количество различных подмножеств $B$ с $k$ пробегами удовлетворяющих условию задачи равно числу решений уравнения
$y_0 + x_1 + y_1 + x_2 + \dots + x_k + y_k = n$
удовлетворяющих неравенствам $x_i\geq 2$ и $y_0\geq 0$, $y_1\geq 1$, ..., $y_{k-1}\geq 1$, $y_k\geq 0$.

Положим $x'_i = x_i - 2$ для $i=1,\dots,k$ и $y'_j=y_j-1$ для $j=1,\dots,k-1$. Тогда
$y_0 + x'_1 + y'_1 + x'_2 + \dots + x'_k + y_k = n + 1 - 3k$
и все переменные в этом уравнении неотрицательны и целочисленны. Поэтому число решений этого уравнения равно биномиальному коэффициенту ${n+1-3k+2k\choose 2k} = {n+1-k\choose 2k}$.

Чтобы получить ответ к исходной задаче, надо просуммировать полученное выражение по числу пробегов $k$:
$f_n = \sum\limits_{k=0}^{\left\lfloor\frac{n+1}{3}\right\rfloor}  {n+1-k\choose 2k}$.

Численная проверка на PARI/GP значений $f_n$ для $n=0,\dots,20$:
Код:
? f(n) = sum(k=0,(n+1)\3,binomial(n+1-k,2*k))
? vector(21,n,f(n-1))
%1 = [1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405]

Получившаяся последовательность - это A005251 со сдвигом индексов на 1.

 
 
 
 
Сообщение13.05.2006, 05:50 
Огромное спасибо maxal.
Извиняюсь за неправильную терминологию,
просто на местном языке (по привычке), множэства
как раз называютса групами (в буквальном переводе),
а для груп есть очень кривое название.
И поэтому появляютса неправильные ассоциации. ;)

 
 
 
 
Сообщение13.05.2006, 06:27 
Аватара пользователя
Кстати, с учетом того что комплексные корни характеристического уравнения по модулю меньше единицы, получаем еще одну формулу: $f_n = \mathop{round}(c\cdot\alpha^n)$
где
$\alpha = \frac{1}{6} (100 + 12 \sqrt{69})^{1/3} + \frac{2}{3 (100 + 12 \sqrt{69})^{1/3}} + \frac{2}{3} \approx 1.754877667$
и
$c = -\frac{1}{276}(100+12\sqrt{69})^{1/3}\sqrt{69} - \frac{11}{276}(100+12\sqrt{69})^{2/3}\sqrt{69} + \frac{1}{12}(100+12\sqrt{69})^{1/3} + \frac{1}{3}(100+12\sqrt{69})^{2/3} + \frac{1}{3} \approx 0.72212442$

 
 
 
 
Сообщение13.05.2006, 07:35 
Интересно.

Я вот пытался с уравнением, но как увидил корни
сразу разхотелось декомпозировать матрицу...
И степенной ряд тоже не хотелось раскладывать.

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

 
 
 
 
Сообщение13.05.2006, 08:00 
Аватара пользователя
sniffer писал(а):
Я вот пытался с уравнением, но как увидил корни
сразу разхотелось декомпозировать матрицу...
И степенной ряд тоже не хотелось раскладывать.

Для этого есть мат.пакеты типа Maple. Я нашел в нем корни хар.уравнения и соответствующие коэффициенты в формуле для $f_n$. При этом оказалось, что коэффициент при $(-1)^n$ равен 0, а вклад комлексных корней (которые по абсолютной величине меньше 1) сводится к округлению результата до ближайшего целого числа. Так и получилась формула в http://dxdy.ru/viewtopic.php?p=19338#19338

 
 
 
 
Сообщение13.05.2006, 08:47 
Ok, разберусь. Спасибо.

 
 
 
 Re: Вопрос по комбинаторике
Сообщение15.04.2010, 16:02 
Рекомендую почитать статью: Заторський Р.А., Литвиненко I.М. Застосування параперма-
нентiв до лiнiйних рекурентних рiвнянь.//Науковi вiстi НТУУ
"КПI". — 2008., №5. — с. 122-128.

 
 
 
 Re: Вопрос по комбинаторике
Сообщение14.06.2010, 12:23 
Аватара пользователя
Не пониммаю, зачем общаться с гениями, которые ассоциируют группу с одним п.
Недостаток общего образования не перекрыть никакими идеями, это такая антиреклама, что дальше читать противно и отношение такое же..
Советую нанять корректора ( можно меня) прилично излагать с легким пиаром.
Извиняюсь за офтоп, можно убрать.

 !  Предупреждение за оффтопик и разжигание флейма!

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


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