Задача о неправильных шеренгах

[Xenia1996]

Шеренга солдат называется неправильной, если никакие три подряд стоящих солдата не стоят по росту (ни в порядке возрастания, ни в порядке убывания). Сколько неправильных шеренг можно построить из n солдат разного роста, если

а) n=4;

б) n=5?

У меня для $n=4$ получилось 10, но когда я увидела их решение, я обомлела:
http://problems.ru/view_problem_details ... p?id=32132

[ИСН]

Я не особо вчитывался, но они там что - доказали несуществование последовательности 4132?

[venco]

Они, похоже, пропустили слово "подряд".

[Xenia1996]

ИСН в сообщении #461653 писал(а):

Я не особо вчитывался, но они там что - доказали несуществование последовательности 4132?

Вот и я о том же.

-- Чт июн 23, 2011 22:17:00 --

venco в сообщении #461655 писал(а):

Они, похоже, пропустили слово "подряд".

Скорее всего.

[TOTAL]

$$S_{n+1}=\frac{1}{4} \sum_{k=0}^{n}C_n^k S_k S_{n-k}, \; \; S_0=S_1=S_2=2, \; \; n+1 \ge 3$$

[Xenia1996]

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

$$S_{n+1}=\frac{1}{4} \sum_{k=0}^{n}C_n^k S_k S_{n-k}, \; \; S_0=S_1=S_2=2, \; \; n+1 \ge 3$$

Это, я так понимаю, формула для "трёх, стоящих подряд". Как Вы её вывели, если не секрет? Или просто знали?

[TOTAL]

Xenia1996 в сообщении #461803 писал(а):

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

$$S_{n+1}=\frac{1}{4} \sum_{k=0}^{n}C_n^k S_k S_{n-k}, \; \; S_0=S_1=S_2=2, \; \; n+1 \ge 3$$

Это, я так понимаю, формула для "трёх, стоящих подряд". Как Вы её вывели, если не секрет? Или просто знали?

Да, для "подряд".
Перед самым высоким стоят $k$ человек, после него стоят остальные $n-k.$
Поэтому $C_n^k \cdot \frac{1}{2} S_k \cdot \frac{1}{2} S_{n-k}$ и сумма по $k$.

[Xenia1996]

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

Xenia1996 в сообщении #461803 писал(а):

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

$$S_{n+1}=\frac{1}{4} \sum_{k=0}^{n}C_n^k S_k S_{n-k}, \; \; S_0=S_1=S_2=2, \; \; n+1 \ge 3$$

Это, я так понимаю, формула для "трёх, стоящих подряд". Как Вы её вывели, если не секрет? Или просто знали?

Да, для "подряд".
Перед самым высоким стоят $k$ человек, после него стоят остальные $n-k.$
Поэтому $C_n^k \cdot \frac{1}{2} S_k \cdot \frac{1}{2} S_{n-k}$ и сумма по $k$.

(Оффтоп)

Вы - чудо!