Вопрос по комбинаторике

[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етса в следующем: Сколько таких груп есть?

Рекурсивно вопрос решаетса не сложно:

\[ \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

[Руст]

Не понятен подсчёт подгрупп.
Если решаете указанное линейное рекурентное соотношение: $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 никуда не девается).

[sniffer]

Подгрупы считаютса следующим образом:

\[ 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 всё равно
можэт пройти через рекурсию, но не стандартными
методами, а то как вы сами сказали получаетса этот полином...
Или можно как нибудь эти групы хитро подсчитать?

[sniffer]

Кстати, другой метод получение той жэ самой формулы:
Если "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)} \]

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

[maxal]

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.

[sniffer]

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

[maxal]

Кстати, с учетом того что комплексные корни характеристического уравнения по модулю меньше единицы, получаем еще одну формулу: $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$

[sniffer]

Интересно.

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

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

[maxal]

sniffer писал(а):

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

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

[sniffer]

Ok, разберусь. Спасибо.

[romanz]

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

[iig]

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

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