Перестановки, Объясните [перемещено] Опции

[Cheburashka]

В общем, достаточно давно я встретился с такой сложной темой (для меня) как перестановки. Сколько я не искал литературы на эту темы, но ничего стоющего не нашёл. Поэтому обратился именно к Вам.

Не могли бы Вы объяснить в чём основной смысл, и как они выполняются?

Сообщение отредактировано: Lapp - 17.07.2009 3:00

[Cheburashka]

Назовем перестановку из N чисел 1…N K-перестановкой, если любые два соседних в ней элемента отличаются не более, чем на K.

Требуется найти число K-перестановок из N чисел от 1 до N.

В общем нашёл ещё одну интересную задачку на перестановки, и хотел бы спросить у Вас кое-что.
Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1).
А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи?

[Lapp]

Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (2, 3, 1) и (3, 2, 1).
А для N=4 и K=2 существует уже 12 перестановок. Не могли бы Вы объяснить почему именно 12 или разъяснить основную суть задачи?

Сергей, когда ты уже научишься наконец правильно ставить задачу и правильно выбирать раздел? Я всегда рад помочь (если могу), но следить за правильным наполнением Форума - моя обязанность (почетная)). Если воспринимать эту задачу как математическую и решать чисто аналитически (то есть вывести общую формулу), то это одно (и, думаю, это ооочень непросто). Но ты забыл сказать, что задачу-то нужно решать численно, т.к. она взята с олимпиады по информатике. И в этом случае она должна быть в разделе Задачи (переносить я не буду - замучился уже)). Я понимаю, что тема типа та же, но ты пойми, что комбинаторика - это целая большая отрасль математики. Как и в других областях, в ней есть задачи, которые решаются аналитически, и есть, которые численно. И не нужно всю ее лепить в одну тему. Выяснил основы предмета - решаешь задачи. Нужно выяснить еще что-то по ее теории - вернись сюда...

Объяснять тут численное решение не буду, флуд это. Надо - создай тему там, где надо. И приведи условие полностью (с ограничениями на N). Но могу сказать некое чисто аналитическое соображение: при любом N число 1-перестановок (то есть К=1) всегда равно 2. Это следует из того, что в этом случае годятся только восходящая и низходящая расстановки, больше никакие. Для других значений К (например, 2), все значительно усложняется

Еще, проверяй свои мессаджи на предмет ошибок, плз. Мне кажется, должно быть так:

Для N=3 и K=1 существует 2 таких перестановки. (1, 2, 3) => (1, 2, 3) и (3, 2, 1).

Ну, а как объяснить, что для N=4, К=2 получается 12? Вот так, например:

1 2 3 4
2 1 3 4
1 3 2 4
.. 3 1 2 4
.. 1 3 4 2
1 2 4 3

4 3 2 1
3 4 2 1
4 2 3 1
.. 2 4 3 1
.. 4 2 1 3
4 3 1 2