On the Enumerating sequences of r-discordant permutations for r between 1 and , 4 By Shalosh B. Ekhad The following theorem goes back to Euler Theorem No., 1, : Let , A(n), be the number of ways of reseating n diners around a round table in such a way that the number of seats, looking clockwise, that each diner moved, is never in the set, {0} Here are the first, 40, terms, starting at n=1, for the sake of OEIS [0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540, 413496759611120779881, 9510425471055777937262, 228250211305338670494289, 5706255282633466762357224, 148362637348470135821287825, 4005791208408693667174771274, 112162153835443422680893595673, 3252702461227859257745914274516, 97581073836835777732377428235481, 3025013288941909109703700275299910, 96800425246141091510518408809597121, 3194414033122656019847107490716704992, 108610077126170304674801654684367969729, 3801352699415960663618057913952878940514, 136848697178974583890250084902303641858505, 5063401795622059603939253141385234748764684, 192409268233638264949691619372638920453057993, 7503961461111892333037973155532917897669261726, 300158458444475693321518926221316715906770469041] The generating function w.r.t., u, of the sequence of rook polynomials in the variable, t, for the board (with the circular convention) made from, {0} is the following rational function: 1 - ----------- t u + u - 1 and in Maple input form -1/(t*u+u-1) Just for fun the number of such permutations whose length is, 300, equals: 1125922665605060626305135020919435631497097387297738123847658062136213354309264\ 7845505196343425808866206021187214129152277449756175128832877190511210139416343\ 1920567020992559443541751276086600577583888194629446987375246642858593246440596\ 3781866157508226963947132183063381303365219274080118098608230892622106506351965\ 3929973878009146330183707750126104255003040152837142786930031749070794128598530\ 3177615704131154683770442017751883340850645204669466017889591855997675003509113\ 8143888643915963439602596308447809251719859406637749471018828199377880651872524\ 47258876432114917736306138575246720033309700244197908595095801 A(n), satisfies the following linear recurrence equations with polynomial (of degree <= one!) coefficients A(n) = (n - 1) A(n - 1) + (n - 1) A(n - 2) In Maple input format: A(n) = (n-1)*A(n-1)+(n-1)*A(n-2) valid for n>=, 3 and with initial values A(1) = 0, A(2) = 1 The following theorem goes back to Lucas, Laisant, and Moreau, 19th-century Theorem No., 2, : Let , A(n), be the number of ways of reseating n diners around a round table in such a way that the number of seats, looking clockwise, that each diner moved, is never in the set, {0, 1} Here are the first, 40, terms, starting at n=1, for the sake of OEIS [0, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123, 52441212770215183676081296, 1418087454121354412691790045, 39762923867612001445482824194, 1154647923129989496658559750193, 34682040826614983472734095531712, 1076377544439444821254633352940175, 34481075598943956929185850329319426, 1139021316022134503795436380243251567, 38763360887576451083282096894245455168, 1357925683976108354812838248065515591633, 48926368181726746427350357974128938839554, 1811711144161235789501336816905011424974653, 68896667977874338233390779975807570251145232, 2688879692613377250447931017322962684269637331, 107627710512932852479215546777103567971049856642] The generating function w.r.t., u, of the sequence of rook polynomials in the variable, t, for the board (with the circular convention) made from, {0, 1} is the following rational function: 3 3 2 2 2 t u - t u - t u + t u - 1 - ------------------------------ 2 2 t u - 2 t u - u + 1 and in Maple input form -(t^3*u^3-t^2*u^2-t*u^2+t*u-1)/(t^2*u^2-2*t*u-u+1) Just for fun the number of such permutations whose length is, 300, equals: 4128208257490031005997271773146225439986039398577016663474729940162105673468753\ 0466839248712598212458801657473190042917992937780444016005041984598902134947342\ 9293051044072879304214796412692750191555851614625858702610443414406764873391690\ 2341206742361458486311088997772432257754213258757590304866183663892971749142348\ 7065684860241479353613737001268181743214669512514998594991513056814200941201725\ 8706198779752248595261458795648566286019909599976094596369462714341212299695726\ 1292783048891097199794526232158383414305987949948942789921862630321740140245056\ 7119404709495197669962634068879091030949019593515853804576002 A(n), satisfies the following linear recurrence equations with polynomial (of degree <= one!) coefficients A(n) = n A(n - 1) + 2 A(n - 2) + (-n + 4) A(n - 3) - A(n - 4) In Maple input format: A(n) = n*A(n-1)+2*A(n-2)+(-n+4)*A(n-3)-A(n-4) valid for n>=, 6 and with initial values A(1) = 0, A(2) = 0, A(3) = 1, A(4) = 2, A(5) = 13 The generating function for the rook polynomials in the following theorem was first derived by Riordan (ca.1962) The recurrence for , A(n), may be new Theorem No., 3, : Let , A(n), be the number of ways of reseating n diners around a round table in such a way that the number of seats, looking clockwise, that each diner moved, is never in the set, {0, 1, 2} Here are the first, 40, terms, starting at n=1, for the sake of OEIS [0, 0, 0, 1, 2, 20, 144, 1265, 12072, 126565, 1445100, 17875140, 238282730, 3407118041, 52034548064, 845569542593, 14570246018686, 265397214435860, 5095853023109484, 102877234050493609, 2178674876680100744, 48296053720501168037 , 1118480911876659396600, 27012357369486579075844, 679192344651429663510262, 17752214070309648660242257, 481640300664961181281424256, 13546525138532752664834181025, 394485386492593863034028504858, 11880374396893285022387630686100, 369620168041784245895021556023784, 11867701438858797521809666206294209, 392869648298809266720099521071616040, 13397102558601680313614481786999560773, 470203170270317138997112729566977311524 , 16971667661830718586462210092362989371076, 629503993367959826314631459105345184302114, 23977030992583231156237861017264718948511465, 937171617718212892390255046935606099990399328, 37565421435130418446037410881796832593260502049] The generating function w.r.t., u, of the sequence of rook polynomials in the variable, t, for the board (with the circular convention) made from, {0, 1, 2} is the following rational function: 6 6 5 6 5 5 4 5 4 4 3 5 3 4 3 3 - (3 t u + 2 t u - t u - 5 t u - 5 t u - 2 t u - 6 t u + 3 t u 2 3 2 2 3 / + 7 t u + t u + 2 t u - 2 t u + 1) / ((t u - 1) / 3 3 2 (t u - t u - 2 t u - u + 1)) and in Maple input form -(3*t^6*u^6+2*t^5*u^6-t^5*u^5-5*t^4*u^5-5*t^4*u^4-2*t^3*u^5-6*t^3*u^4+3*t^3*u^3 +7*t^2*u^3+t^2*u^2+2*t*u^3-2*t*u+1)/(t*u-1)/(t^3*u^3-t*u^2-2*t*u-u+1) Just for fun the number of such permutations whose length is, 300, equals: 1508524684838193106106519198801623176845635875716392614976433954652338766823981\ 9202338375206858839235532020505616198105389862809275168296160227327478498472170\ 3940760816901686732626038429363480952325085214474133010231491035234135105675422\ 5756272326162763717003064222554900540629766525779212829508912802816480577991708\ 2468272875498827280330331174612768861623961431642706409492723799557229230425294\ 4694448551243133330775581391810625674601420236371226135661199344356652939657318\ 6636849412693248803636084974447556133703753571539445152300975958239085029505714\ 2153652757621384407705691148452927939193655569425088319608004 A(n), satisfies the following linear recurrence equations with polynomial (of degree <= one!) coefficients A(n) = (n + 1) A(n - 1) + (-n + 11) A(n - 2) + (-7 n + 17) A(n - 3) + (4 n - 39) A(n - 4) + (14 n - 74) A(n - 5) + (-8 n + 66) A(n - 6) + (-10 n + 62) A(n - 7) + (8 n - 81) A(n - 8) + (n + 1) A(n - 9) + (-3 n + 35) A(n - 10) + (n - 15) A(n - 11) + A(n - 12) In Maple input format: A(n) = (n+1)*A(n-1)+(-n+11)*A(n-2)+(-7*n+17)*A(n-3)+(4*n-39)*A(n-4)+(14*n-74)*A (n-5)+(-8*n+66)*A(n-6)+(-10*n+62)*A(n-7)+(8*n-81)*A(n-8)+(n+1)*A(n-9)+(-3*n+35) *A(n-10)+(n-15)*A(n-11)+A(n-12) valid for n>=, 15 and with initial values A(1) = 0, A(2) = 0, A(3) = 0, A(4) = 1, A(5) = 2, A(6) = 20, A(7) = 144, A(8) = 1265, A(9) = 12072, A(10) = 126565, A(11) = 1445100, A(12) = 17875140, A(13) = 238282730, A(14) = 3407118041 The generating function for the rook polynomials was first derived by Eearl Glenn Whitehead (1979) We were unable to find a recurrence (it is too long for us) Theorem No., 4, : Let , A(n), be the number of ways of reseating n diners around a round table in such a way that the number of seats, looking clockwise, that each diner moved, is never in the set, {0, 1, 2, 3} Here are the first, 40, terms, starting at n=1, for the sake of OEIS [0, 0, 0, 0, 1, 2, 31, 264, 2783, 30818, 369321, 4745952, 65275999, 957874226, 14951584189, 247524019720, 4334022049377, 80052395326514, 1555999253409203, 31755107852542144, 679008663143893773, 15182701602959054546, 354364531995856105099, 8618865446674052425224, 218107566239993684272531, 5734302907005373513322674, 156419366922989437119483053, 4421296327690290833867429280, 129342793572697058001361979515, 3911872744020239697091063448610, 122186361171383713228524253528505, 3937574492398733597775756214634504, 130797671713809401672661431633725701, 4474620445439502062225784325579426082, 157520825370053795921028965470658524071, 5701710972929337471229726555336743113088, 212048638027981291325131546552683175743897, 8096977188862533046508859949651226179533410, 317231862755043395438188803396603795429015031, 12744435983915127294453604684178447501994406664] The generating function w.r.t., u, of the sequence of rook polynomials in the variable, t, for the board (with the circular convention) made from, {0, 1, 2, 3} is the following rational function: 11 11 10 11 10 10 9 11 9 10 9 9 - (10 t u + 15 t u + 6 t u + 3 t u - 6 t u + 3 t u 8 10 8 9 7 10 8 8 7 9 7 8 7 7 - 15 t u - 6 t u - 3 t u - 33 t u - 4 t u - 93 t u - 4 t u 6 8 6 7 5 8 5 7 5 6 4 7 - 57 t u + 30 t u - 9 t u + 64 t u + 33 t u + 27 t u 5 5 4 6 3 7 4 5 3 6 4 4 3 5 + 30 t u + 37 t u + 3 t u + 66 t u + 7 t u - 10 t u + 19 t u 3 4 3 3 2 4 2 3 4 2 2 3 2 - 39 t u - 2 t u - 24 t u - 5 t u - 3 t u - 2 t u - t u + t u / 8 8 6 7 5 5 4 5 4 4 3 4 + 3 t u - 1) / (t u - t u - 4 t u - 3 t u + 2 t u + 4 t u / 2 4 2 3 2 2 + t u + t u + 4 t u - 4 t u - u + 1) and in Maple input form -(10*t^11*u^11+15*t^10*u^11+6*t^10*u^10+3*t^9*u^11-6*t^9*u^10+3*t^9*u^9-15*t^8* u^10-6*t^8*u^9-3*t^7*u^10-33*t^8*u^8-4*t^7*u^9-93*t^7*u^8-4*t^7*u^7-57*t^6*u^8+ 30*t^6*u^7-9*t^5*u^8+64*t^5*u^7+33*t^5*u^6+27*t^4*u^7+30*t^5*u^5+37*t^4*u^6+3*t ^3*u^7+66*t^4*u^5+7*t^3*u^6-10*t^4*u^4+19*t^3*u^5-39*t^3*u^4-2*t^3*u^3-24*t^2*u ^4-5*t^2*u^3-3*t*u^4-2*t^2*u^2-t*u^3+t*u^2+3*t*u-1)/(t^8*u^8-t^6*u^7-4*t^5*u^5-\ 3*t^4*u^5+2*t^4*u^4+4*t^3*u^4+t^2*u^4+t^2*u^3+4*t^2*u^2-4*t*u-u+1) Just for fun the number of such permutations whose length is, 300, equals: 5493779206134193624485103639947090952150512467147921715202704011311480485766362\ 4206037479706270049093463407796012777079298907413166342522564168336769844478661\ 7354449819000916695429309584596217919855222897845881843251557098310474343273406\ 3163821358534240716307074198890465581944021067490208465195295779525650984164701\ 2816801947344710025176312321186553385177732905802272449355615759096240690460663\ 3912865225890771649554148277299959353282767344771147314058188969178855024109350\ 7465891383623684336608755405390454031664211927292437291771265770988482579588882\ 104679061809477121650756159723494521221059286441467251252320 This ends this article, that took, 12.788, seconds.