2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Верблюжья комбинаторика
Сообщение01.11.2011, 01:43 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 07:47 
Заслуженный участник


08/04/08
8562
Вроде бы это классическая задачка о перестановках $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$, где у меня ошибка?

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 07:55 


05/10/10
71
Sonic86 в сообщении #498068 писал(а):
Вроде бы это классическая задачка о перестановках $n$ элементов, не сохраняющих ни один элемент

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

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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 08:30 
Заслуженный участник


08/04/08
8562
А, все, понял, извините.

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 10:39 


05/10/10
71
Пусть $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$

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 12:42 
Заслуженный участник


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

Пусть $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$
Теперь, кто бы помог избавится от рекурентности в этой формуле?)

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 13:56 
Заслуженный участник
Аватара пользователя


01/08/06
3136
Уфа
MrDindows писал(а):
Теперь, кто бы помог избавится от рекурентности в этой формуле?)
A000255 помог бы :wink:

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 14:06 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 14:44 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 18:35 
Заслуженный участник


06/05/11
278
Харьков
MrDindows в сообщении #498114 писал(а):
Теперь, кто бы помог избавится от рекурентности в этой формуле?)

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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение01.11.2011, 22:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение02.11.2011, 10:28 
Заслуженный участник
Аватара пользователя


23/08/07
5500
Нов-ск
bnovikov в сообщении #498224 писал(а):
MrDindows в сообщении #498114 писал(а):
Теперь, кто бы помог избавится от рекурентности в этой формуле?)

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

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

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение02.11.2011, 14:22 
Заслуженный участник


06/05/11
278
Харьков
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$.

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение02.11.2011, 14:24 
Заслуженный участник


20/12/10
9110
bnovikov в сообщении #498452 писал(а):
Получаем $b_n=(n-2)b_{n-1}$, откуда $b_n=(n-2)!b_2$.
Посмотрите ещё раз рекуррентное соотношение --- там знак другой.

 Профиль  
                  
 
 Re: Верблюжья комбинаторика
Сообщение02.11.2011, 16:04 
Заслуженный участник


06/05/11
278
Харьков
nnosipov в сообщении #498455 писал(а):
Посмотрите ещё раз рекуррентное соотношение --- там знак другой.

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

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

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



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

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


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

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