2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Вопрос по комбинаторике
Сообщение12.05.2006, 18:20 


10/05/06
24
Бесконечность
Определим групу: \[
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 
Заслуженный участник


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


10/05/06
24
Бесконечность
Подгрупы считаютса следующим образом:
\[
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 


10/05/06
24
Бесконечность
Кстати, другой метод получение той жэ самой формулы:
Если "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 
Модератор
Аватара пользователя


11/01/06
5710
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 


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

 Профиль  
                  
 
 
Сообщение13.05.2006, 06:27 
Модератор
Аватара пользователя


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


10/05/06
24
Бесконечность
Интересно.

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

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

 Профиль  
                  
 
 
Сообщение13.05.2006, 08:00 
Модератор
Аватара пользователя


11/01/06
5710
sniffer писал(а):
Я вот пытался с уравнением, но как увидил корни
сразу разхотелось декомпозировать матрицу...
И степенной ряд тоже не хотелось раскладывать.

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

 Профиль  
                  
 
 
Сообщение13.05.2006, 08:47 


10/05/06
24
Бесконечность
Ok, разберусь. Спасибо.

 Профиль  
                  
 
 Re: Вопрос по комбинаторике
Сообщение15.04.2010, 16:02 


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

 Профиль  
                  
 
 Re: Вопрос по комбинаторике
Сообщение14.06.2010, 12:23 
Заблокирован
Аватара пользователя


03/05/09

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

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

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

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



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

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


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

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