2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Рекуррентная последовательность и перестановки
Сообщение16.12.2016, 20:50 
Аватара пользователя


26/04/15
7
Россия
Нашел в oeis такую последовательность:
A038718
В шапке страницы можете увидеть любопытное утверждение. Каждый член последовательности - число перестановок $P$ набора $ 1,2,...,n $ такое, что $P_{1}=1$ и $|P_{i+1}-P_{i}|\leqslant2$ для $i=1,2,...,n-1$. Если непонятно, то $P$ - сама перестановка. Получается очень красивая рекурреннтная последовательность $a_{n} = a_{n-1} + a_{n-3} + 1$. Я попытался вывести эту формулу.
Идея была такая: пусть есть набор $ 1,2,...,n $, и какая-то его перестановка в рамках данных условий. Увеличим все числа в перестановке на 1 и слева допишем 1. Так мы получиим первые $a_{n}$ перестановок следующего набора $ 1,2,...,n, n+1 $. Далее заметим, что перестановки набора $ 1,2,...,n-2 $ тоже можно как-то дописывать и получим еще $ a_{n-2}$ перестановок набора $ 1,2,...,n, n+1 $. Ну и наконец догадываемся, что каждый новый набор генерит еще одну уникальную перестановку, которую первыми двумя способами из перестановок более мелких наборов получить нельзя.
Решение недоделанное и, вполне возможно, вообще не про то, что нужно. В правильном ли направлении я мыслю? Какие подходы использовали бы вы?

 Профиль  
                  
 
 Re: Рекуррентная последовательность и перестановки
Сообщение16.12.2016, 21:09 
Заслуженный участник


10/01/16
2315
icu в сообщении #1177660 писал(а):
Какие подходы использовали бы вы?

Я ж Вам писал в Вашей предыдущей теме: была указана ссылка на тему, в которой эта задача решалась для $n=41$, и было показано, как сводится к 40 и 38....

 Профиль  
                  
 
 Re: Рекуррентная последовательность и перестановки
Сообщение17.12.2016, 10:25 
Заслуженный участник
Аватара пользователя


19/12/10
1546
icu в сообщении #1177660 писал(а):
Получается очень красивая рекурреннтная последовательность $a_{n} = a_{n-1} + a_{n-3} + 1$

Уже было, причём недавно. Решение.

-- 17 дек 2016, 11:06 --

Пардон, Вы не про решение рекуррентности, а про её вывод. :?

Тоже было, и тоже не так давно.

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

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



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

Сейчас этот форум просматривают: Mikhail_K


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

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