В очереди за мороженым стоит 5 ребят. Сколькими способами можно переставить ребят так, чтобы впереди каждого из них оказался другой, чем был раньше?

задан 25 Май '16 1:18

Я понимаю условие так: пусть они стоят в порядке 12345. Нужно найти число перестановок, где нет ни 12, ни 23, ни 34, ни 45 друг за другом.

Формулировка несколько "скользкая", потому что впереди первого никого нет. Логически точнее так: чтобы впереди каждого не оказался тот, кто был раньше.

(25 Май '16 1:33) falcao

По формуле включений и исключений можно получить ответ 53. Но я пока думаю над тем, нельзя ли то же самое получить попроще.

(25 Май '16 2:34) falcao
10|600 символов нужно символов осталось
1

Пусть в очереди стоят $%n$% ребят.

$%\beta_n$% - число перестановок в очередь таким образом, что впереди каждого оказался другой.

$%\gamma_n$% - число перестановок в очередь таким образом, что впереди ровно одного оказался тот же самый.

Тогда : $$\beta_n = (n-1)\cdot \beta_{n-1}+\gamma_{n-1}$$ $$\gamma_n = (n-1)\cdot\gamma_{n-1}$$

Получаем : $%\beta_n=(n-1)\cdot \beta_{n-1}+(n-2) \cdot \beta_{n-2}$%

$%\beta_1=1, \beta_2=1,\beta_3=3, \beta_4=11, \beta_5=53, ...$%

Пользуясь формулой включения и исключения можно написать и явное выражение для $%\beta_n$%:

$$\beta_n=(n-1)! \cdot (n - \frac{n-1}{1!}+\frac{n-2}{2!}+ \cdots + \frac{(-1)^{n-1}}{(n-1)!})$$

ссылка

отвечен 26 Май '16 0:57

изменен 26 Май '16 20:56

@Sergic Primazon: не знаю, в чём здесь ошибка (возможно, в рекуррентных формулах, которые никак не объяснены), но это значение $%\beta_5$% точно неверное. Там должно быть 53. См. здесь.

(26 Май '16 2:17) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×874
×61

задан
25 Май '16 1:18

показан
817 раз

обновлен
26 Май '16 20:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru