До никъде.

Нищо не направихме.Поставеният въпрос остава открит.

От къде си взел тази задача и защо толкова искаш да я решиш?
Ако е важно, мога да опитам пак.

Dobre. Togava prez pochivnite dni shte probvam "dyrvarskia metod", t.e. s porajdashti funkcii i t.n. Da vidim kakvo shte izleze:-)

Broia na razlichnite vazmojni priatelskite dvoiki (mnojestva ot dva elementa 1<=A(k)<A(k+1)<=2*n, A(k+1)-A(k)=n) vav vsichki i plusovi permutacia e raven na (n/nad/i) (binomen koeficient n nad i)
Vsiaka takava uchastva v (n-i)! permutacii. Dualnite A(k)-A(k+1) umnojavat obshtata broika po 2^i.
Krainiat otgovor e ((n/nad/i))*(n-i)!*2^i
Kombinatornite zadachi sa podla rabota, ne sam siguren v korektnostta na gornite razsajdenia.
Shte se radvam , ako niakoi ot vas (b3 ili mrasnika) posochi greshka.
A eto i edna zadacha ot men:
Imate redica ot chisla, S(1), S(2)...S(n)
Tarsi se rekurentna vrazka C(1),C(2),...C(L), takava che
S(j)={suma (C(i)*S(j-i)) za i ot 1 do L) e viarno za j=L,L+1,L+2,...n
s minimalnomvazmojno L.
Ako chislata sa racionalni, zadachata mi e iasna- znam kak se programira algorithm koito da ia reshava.
Malko neiasnoti imam kogato rabotia s celi chisla po niakakav modul.
Pozdravi!
A

Аз се опитах отново и мисля, че успях да реша тази задача. Давам тук моето решение с доказателство. Ще се радвам ако някой го провери и ми съобщи дали е съгласен с мен. Предварително се извинявам, че обяснението ми е много подробно.

З а д а ч а (на mrasnika)

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

Р е ш е н и е.

Броя P(n, i) на i – плюсовите пермутации от числата между 1 и 2*n е

(1) P(n, i) = Q(n, i) – Q(n, i + 1) при 0 <= i

където

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

и където с C(u, v) е означен биномния коефицент u! / (v! * (u – v)!).

Забележка: при i < 0 или n < 1 задачата не е определена.


Д о к а з а т е л с т в о.

При дадено n, разполагаме с максимално n неподредени приятни двойки, а именно с двойките (1, 1 + n), (2, 2 + n), . . . (n, n + n).

Нека да означим с Q(n, i) броя на редиците (от числата между 1 и 2*n) които съдържат не по-малко от i приятни двойки. От самото определение на Q(n, i) веднага следва равенство (1).

Понеже броя на всички двойки е n очевидно е, че Q(n, i) = 0 при i > n. С това е доказано равенството (2).

Можем да изберем i неподредени приятни двойки от n-те с които разполагаме по C(n, i) = n! / (i! * (n – i)!) начина. От всеки такъв избор може да получим нов, ако пермутираме някоя от двойките по 2! = 2 начина, а понеже имаме i двойки ще получим общо 2^i пермутации вътре в самите двойки. Oкончателно получaваме числото

C(n, i) * i^2,

показващо ни по колко начина можем да изберем i подредени приятни двойки от всичките числа 1, 2, . . ., 2*n – 1, 2*n.

След като вече сме избрали i приятни двойки на нас ни остават още 2*n – 2*i неизползвани числа които трябва да пермутираме заедно с избраните двойки. Всяка такава пермутация можем да илюстрираме със следната схема, където с ( , ) e показано мястата на вече избраните двойки, а с ___ е показано мястото което се заема от нула, едно или повече от оставащите ни 2*n – 2*i числа:

___ ( , ) ___ ( , ) ___ . . . ___ ( , ) ___

Ние можем да пермутираме тези 2*n – i обекта по (2*n – i)! начина. Така получаваме равенството

Q(n, i) = C(n, i) * 2^i * (2 * n – i)!

От построението е ясно, че това е броя на всички редици с не по-малко от i приятно двойки, с което е доказано (3).

КРАЙ.


/b33
Бойко

P. S.
За Genki: Не можах да разбера твоята задача. Можеш ли да я обясниш по-подробно, по-точно и да демонстрираш как се намира решение при рационални числа? Обясни и защо я решаваш (от къде идва задачата).

Веднага видях, че пак имам грешка.

Ясно е, че

Q(n, i) < C(n, i) * 2^i * (2*n - i)!

понеже се получават повторения.

Задачата си остава НЕРЕШЕНА. Формулата на Genki също не е вярна.

/b33
Бойко

Popravka:
Broia na razlichnite vazmojni priatelskite dvoiki (mnojestva ot dva elementa 1<=A(k)<A(k+1)<=2*n, A(k+1)-A(k)=n) vav vsichki i plusovi permutacia e raven na (n/nad/i) (binomen koeficient n nad i)
Vsiaka takava uchastva v (n-i)! permutacii. Dualnite A(k)-A(k+1) umnojavat obshtata broika po 2^i.
Krainiat otgovor e ((n/nad/i))*(2*n-2*i)!*2^i
Kombinatornite zadachi sa podla rabota, ne sam siguren v korektnostta na gornite razsajdenia.
Shte se radvam , ako niakoi ot vas (b3 ili mrasnika) posochi greshka.
A eto i edna zadacha ot men:
Imate redica ot chisla, S(1), S(2)...S(n)
Tarsi se rekurentna vrazka C(1),C(2),...C(L), takava che
S(j)={suma (C(i)*S(j-i)) za i ot 1 do L) e viarno za j=L,L+1,L+2,...n
s minimalnomvazmojno L.
Ako chislata sa racionalni, zadachata mi e iasna- znam kak se programira algorithm koito da ia reshava.
Malko neiasnoti imam kogato rabotia s celi chisla po niakakav modul.
Pozdravi!
A

Zdravei, Boiko.
Prav si vav formulata imam greshka, vmesto (n/nad/i)(n-i)!2^i triabva da se chete (n/nad/i)(2*n-i)!*2^i.
mislia, che razsasjdeniata mi sa principno sashtite kato tvoite v postinga "reshenie" ot 28.06. Prosto zabravi za Q(n,i), tazi na prav pogled dobra ideia samo uslojnaiva reshenieto.
Otnosno moiata zadacha, publikuvam ia malko kato geroite ot "Kod Merkurii".
Tia vsashtnost idva i ot problem za dekodirane na kodove.
Ako se interesuvash, napravi search v Google za Berlekamp-Massey Algorithm.
REDAKCIA:Toku-shto vidiah che si programist, sigurno veche si napravil programa koiato da dava otgovor na zadachata za permutaciite. Kakvi sa rezultatite za niakoi malki stoinosti na (n,i)?

Prav si, formulata mi sashto ne e viarna, sashto i razsajdeniata.Ne mi e iasno kak da se eliminirat povtoreniata.Mislia che formulata za Q(n,n) e viarna, tam niama kak da se poluchat povtorenia. Probva li da presmetneh pone chastnia sluchai i=0?