Цитата(Сергей Меркурьев @ 21.07.2009 11:36)
Для 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 21 2
4 34 3 2 1
3 4 2 1
4
2 3 1
..
2 4 3 1
.. 4 2
1 34 3
1 2