Применение классических комбинаторных методов к разным задачам → .01 Анализ с конца

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

Итак, каждое из чисел можно сдвинуть с его позиции на любую из оставшихся, в итоге получаем способов.

Если число сдвигается больше, чем на одну позицию, то такой порядок встречается ровно один раз, поскольку оно поменялось порядком хотя бы с двумя числами, а мы двигаем ровно одно. Однако если число сдвинулось ровно на одну позицию, то такой порядок встретится ровно дважды — мы можем точно также сдвинуть его соседа на его место. В итоге получаем, что порядков (в каждом два соседних числа поменялись местами) посчитаны дважды.

А ещё не забудем изначальный набор по возрастанию, в котором никаких перестановок сделано не было.

Окончательно получаем

______________________________________________________________________________________________________________________________________________________

Второе решение. Подходят исходная расстановка и любая строка, полученная переносом любого числа с исходного места на любое другое. При этом перенос на соседнее место равносилен обмену местами двух соседей, то есть, может быть получен двумя способами; каждый из остальных переносов дает уникальную строку. На не соседнее место можно переставить 99 способами крайние числа 1 и 101 и 98 способами каждое из 99 остальных чисел. Учитывая, что есть 100 пар соседей, всего получаем хороших порядков .

Например, так:

______________________________________________________________________________________________________________________________________________________

Замечание. Проще всего такой алгоритм придумывается «с конца»: умножаем число на 2 и стираем последние двойки, как только можем.