zadachka

Interesuva me otgovorat na slednata zadacha:
Нека n е естествено число.Една пермутация на числата от 1 до 2*n се нарича
приятна ,ако разликата на някои два съседни елемента е точно n.
Една приятна пермутация се нарича i-плюсова ако в нея има точно i двойки
(двойка наричаме два съседни елемента)такива,че разликата на елементите
на всяка двойка е n.Ако с P(n,i) означим броя на i-плюсовите пермутации,да се
пресметне P(n,i).

До колкото съм разрбрал търсим броя на редиците A1, A2, . . . A2n, от цели числа между 1 и 2n в които се срещат i приятни двоики (Аk, Ak+1) за които имаме абсолютната стойност |Ak – Ak+1| = n.

За n > 0 получих следните формули за броя на редиците съдъежащи i приятни двойки:

(1) P(n, i) = 0 при i > n,
(2) P(n, n) = n! * 2^n,
(3) P(n, i) = Q(n, i) – Q(n, i + 1) при 0 <= i < n

Където

Q(n, i) = (i! * 2^i) * Сума за j=1 до m от [ C(2*(k-i)-1, j-1) * C(i+1, j) ]

m = min(i + 1, 2 * (n – i)), т.е. по-малкото от i+1 и 2*(n-i)

и имаме означенията

2^i е 2 на степен i,
i! = 1*2*3*...*i, т.е. i факториел
C(u, v) = u! / (v! * (u – v)!), т.е. количеството v-подмножества на u-множество (или биномните коефициенти),
Използвал съм израза “Сума за j=1 до m от [ . . .]” вместо стандартния знак за сума сигма, където индекса j се изменя от 1 до m.

Тук смисъла на Q(n, i) е броя на редиците съдържащи “не по-малко” от i приятни двойки.
Формулата има смисъл и за i = 0.

Ако заместим в (3) израза за Q(n, I) е възможно да получим и по-проста формула.

Забелязах, че в израза за Q съм допуснал малка печатна грешка. Написал съм буквата 'k' вместо 'n'. Така, че израза нека да се чете:

Q(n, i) = (i! * 2^i) * Сума за j=1 до m от [ C(2*(n-i)-1, j-1) * C(i+1, j) ]

Извинения

Съжалявам, но съм допуснал още една грешка. Пропуснал съм множителя C(n, i) във формулата за Q(n, i), който идва от факта, че когата i < n можем да изберем C(n, i) на брой i-подмномножества на n-те възможни приятни двойки.

Така, че окончателната формула е:

(1) P(n, i) = 0 за i > n,
(2) P(n, n) = n! * 2^n,
(3) P(n, i) = Q(n, i) – Q(n, i + 1) за 0 <= i < n,

Където

Q(n, n) = P(n, n) = n! * 2^n,
Q(n, i) = (i! * 2^n * C(n, i)) * (Сума за j = 1 до m от [C(2 * (n – i) – 1, j – 1) * C(i + 1, j)]) при I < n

m = min(2 * (n – i), i + 1)

Поздрави,
Бойко

[повтарям постинга заради печатна грешка. този път трябва да е вярното :)))) ]

Съжалявам, но съм допуснал още една грешка. Пропуснал съм множителя C(n, i) във формулата за Q(n, i), който идва от факта, че когата i < n можем да изберем C(n, i) на брой i-подмномножества на n-те възможни приятни двойки.

Така, че окончателната формула е:

(1) P(n, i) = 0 за i > n,
(2) P(n, n) = n! * 2^n,
(3) P(n, i) = Q(n, i) – Q(n, i + 1) за 0 <= i < n,

Където

Q(n, n) = P(n, n) = n! * 2^n,
Q(n, i) = (i! * 2^i * C(n, i)) * (Сума за j = 1 до m от [C(2 * (n – i) – 1, j – 1) * C(i + 1, j)]) при i < n

m = min(2 * (n – i), i + 1)

Поздрави,
Бойко

Най - последен резултат (преди беше пропуснато едно j! :))))

(1) P(n, i) = 0 при i > n,
(2) P(n, n) = n! * 2^n,
(3) P(n, i) = Q(n, i) – Q(n, i + 1) при 0 <= i < n

Където

Q(n, n) = P(n, n) = n! * 2^n,
Q(n, i) = (i! * 2^i * C(n, i)) * (Сума за j = 1 до m от [j! * C(2 * (n - i) - 1, j - 1) * C(i + 1, j)]) при 0 <= i < n

n > 0,
m = min( i + 1, 2 * (n – i) ),
C(u, v) = u! / (v! * (u – v)!) – биномния коефициент.

Q(n, i) е броя на редиците съдържащи “не по-малко” от i приятни двойки.
Формулите P(n, i) и Q(n, i) имат смисъл и за i = 0.

Допуснах грешки, понеже съм малко невнимателен в момента.
Сега го проверих 5 пъти; едва ли има повече грешки : )))

/b33
Бойко

Вярното и просто решение е:

P(n, i) = C(n, i) * (2 * n - i)! * 2^i

C(u, v) = u! / (v! * (u - v)!) -- биномния коефициент.


Не чети постингите ми от 3:53 до 9:19!
Бях се объркал нещо.
При i = n отново плучаваме n! * 2^n.

Айде чао,
/b33
Бойко