Верблюжья комбинаторика

[MrDindows]

По пустыни идёт караван из $N$ верблюдов. После отдыха верблюдов переставили так, чтоб впереди каждого верблюда шёл верблюд, отличный от того, что шёл раньше. Сколькими способами можно это сделать?)

Посчитал количества способов для нескольких первых N: (поправил немного числа, в программе была ошибка)
1, 1, 3, 11, 53, 309, ...
Зависимости не увидел.

Идей решения пока-что тоже маловато=)

[Sonic86]

Вроде бы это классическая задачка о перестановках $n$ элементов, не сохраняющих ни один элемент, таких по формуле включений исключений по признаку совпадения $k$ элементов после перестановки ровно $n! \sum\limits_{k=0}^n \frac{(-1)^k}{k!} = \left[ \frac{n!}{e} + \frac{1}{2} \right]$. Но у меня другая последовательность. Вот у Вас $C(3)=3$ - почему? Если верблюды стояли как $123$, то возможны только варианты $312$ и $231$ - получаем всего $2$ варианта, а не $3$, где у меня ошибка?

[Naf2000]

Sonic86 в сообщении #498068 писал(а):

Вроде бы это классическая задачка о перестановках $n$ элементов, не сохраняющих ни один элемент

Нет, сохранения (не сохранения) своего номера не требуется. Пересказ примерно такой:

Перестановку на множестве $\{1,2,...,N\}$ назовем сильно перемешанной, если для любого числа $K (0<K<N)$ следующее за ним число в ней (если такое есть) отлично от $K+1$.
Вопрос: Сколько всего сильно перемешанных перестановок?

[Sonic86]

А, все, понял, извините.

[Naf2000]

Пусть $F_r(n)$ - количество перестановок на $n$ элементах, где РОВНО $r$ пар числе удовлетворяют условию: $A_{k+1} = A_k + 1$.
Тогда искомая функция это $F_0(n)$.
Получились следующие рекурентные соотношения:
$F_0(n+1) = nF_0(n) + F_1(n)$
$F_r(n+1) = F_{r-1}(n) + (n-r)F_r(n) + (r+1)F_{r+1}(n), r>0$

[MrDindows]

Я сегодня утром, пока в универ ехал, разобрался с задачей.

Пусть $a_n$ - искомое количество способов.
Тогда: $a_n=(n-1)a_{n-1}+(n-2)a_{n-2}$

Почему так:
Как мы можем получить последовательность из $n$ элементов. Во-первых, если у нас есть любая последовательность из $n-1$ элементов, удовлетворяющая условие, то мы можем вставить в неё элемент в одну из $n-1$ позиций ( так как всего позиций $n$, но одна позиция находится после элемента n-1, значит туда вставить n мы не можем). Это есть слагаемое $(n-1)a_{n-1}$.
Во-вторых, для любой последовательности из $n-1$ элементов, где ровно одна пара элементов нехорошая ( тоесть это последовательные два числа), мы можем вставить элемент n, разбив эту пару, и соответственно получим последовательность из $n$ элементов удовлетворяющую условию. Теперь надо ответить на вопрос, сколько есть таких ( с одной нехорошей парой=) последовательностей из $n-1$ элементов.
Для этого, зафиксируем любую пару последовательных элементов k, k+1 . Количество последовательностей с этой парой будет равно $a_{n-2}$, и, так как пару k, k+1 из $n-1$ элементов мы можем выбрать $n-2$ способами, то вот мы и получили слагаемое $(n-2)a_{n-2}$

Таким образом:
$a_n=(n-1)a_{n-1}+(n-2)a_{n-2}$.
$a_1=a_2=1$
Теперь, кто бы помог избавится от рекурентности в этой формуле?)

[worm2]

MrDindows писал(а):

Теперь, кто бы помог избавится от рекурентности в этой формуле?)

A000255 помог бы

[Whitaker]

MrDindows по-моему эта задачка есть в книжке Виленкина и она там хорошо очень подробно описана.

[MrDindows]

worm2, Спасибо.
Whitaker, спасибо, мб почитаю на досуге=)

[bnovikov]

MrDindows в сообщении #498114 писал(а):

Теперь, кто бы помог избавится от рекурентности в этой формуле?)

Ну, это уже несложно. Положите $b_n=a_n-a_{n-1}$.

[Хорхе]

А меня, как обычно, биекция мучит. Получается та же эпф, что у таких помеченных структур (с размером на двойку меньше): две последовательности (перестановки) и множество.

[TOTAL]

bnovikov в сообщении #498224 писал(а):

MrDindows в сообщении #498114 писал(а):

Теперь, кто бы помог избавится от рекурентности в этой формуле?)

Ну, это уже несложно. Положите $b_n=a_n-a_{n-1}$.

Что потом делать?

[bnovikov]

TOTAL в сообщении #498425 писал(а):

bnovikov в сообщении #498224 писал(а):

MrDindows в сообщении #498114 писал(а):

Теперь, кто бы помог избавится от рекурентности в этой формуле?)

Ну, это уже несложно. Положите $b_n=a_n-a_{n-1}$.

Что потом делать?

Получаем $b_n=(n-2)b_{n-1}$, откуда $b_n=(n-2)!b_2$.

[nnosipov]

bnovikov в сообщении #498452 писал(а):

Получаем $b_n=(n-2)b_{n-1}$, откуда $b_n=(n-2)!b_2$.

Посмотрите ещё раз рекуррентное соотношение --- там знак другой.

[bnovikov]

nnosipov в сообщении #498455 писал(а):

Посмотрите ещё раз рекуррентное соотношение --- там знак другой.

Вы правы. Тогда можно составить дифф. ур. для производящей функции, но не знаю, будет ли от этого толк.