On the Enumeration of Generalized Menages Numbers for all subsets of , {0, 1, 2, 3}, containing 0 By Shalosh B. Ekhad -------------------------------------------- If pi[i]-i is never in, {0, 1}, we have the following Theorem number, 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, 1} The first, 30, terms (for the sake of Sloane) are: [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] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients 2 2 (n - 3 n + 3) a(n - 1) (n - 3 n + 3) a(n - 2) (n - 1) a(n - 3) a(n) = ----------------------- + ----------------------- + ---------------- n - 2 n - 2 n - 2 and in Maple input format: a(n) = (n^2-3*n+3)/(n-2)*a(n-1)+(n^2-3*n+3)/(n-2)*a(n-2)+(n-1)/(n-2)*a(n-3) Just for fun, the number of such permutations of length, 1000, is: 5440270940916427795620790501019929348872986505634963859163496814793721393032\ 975646735910228263562190416660571332341840924638926684962666045524728468\ 655736353141732090019473395400748937429526697386606995419378335171318096\ 106301149167571054919370893124489326731419501449702026342433919755398953\ 612594603550445234849294527106315776466854800883004895086503544641195592\ 980224990890630372706759567592591582739313159498110648743492003096534308\ 938960208301966655426036202037700431703362637967385059671765748426369194\ 142258860302322802336992306537812822150557840707626721299906651622934479\ 928976610540792199405191625640025268433788902448971143866568502725862664\ 111317720910636058655162094423864082211389746769685638412780789699938192\ 329578485503974656356403005801171057435653907188329339632389640064716212\ 467950571896177150473193968667178869169641709667346929682490083334255073\ 713368679669554478935765271377032592383001578525866569416125037963899252\ 624116377007897197433524650288771373945104731097577476117267394340631909\ 811922739042043996832208801864033262948233507024173501397149608896395244\ 568090537457183196538597763829831188417825075829679649255691667489078655\ 277585898990232736891902611965827815291401889322406438327748354864738253\ 783163156913367756698420817385067697870401290590046469501582742006154647\ 995386465634021598097432590129746056447803577956276055865052757087741871\ 322268232814975848414964622940988904121746055423067130196700263144105238\ 777454582746055279930633223556060223005615896020098399983197119362181616\ 216214463212412985613378224406723256435850665249550367862130347276860401\ 823211738429062389183565920156375222731984371049913516484197886656702433\ 771622539924373901733538375474289615031221869604903018823153621909703411\ 525874473540344656158573856267434431010600542460053738792753634630548300\ 393993574172023418845815427940007451290360013654584389890939952610930373\ 661186056146763001103664988486497451825466117077221839360614261219837925\ 586215157672453096114832714610581102844012346175941328668116879092317498\ 910518506512183850129257320485098632325094005470550702914437068729275250\ 123251245560747159257998416534963433651602788864927818638457846671092790\ 770293419767428146874492067502774966707977055545525461183631330051513346\ 897273880016424924951067531630007396818391082872741915831311202927935132\ 876502743871596754826339694516750801994796189772151203096490974963169726\ 657814340588542531950279270504499956018035150724072332411694695448260428\ 553905669079321780780066522722772710112586616603457914322056402867971902\ 1861571057928070111613283936655948656400002 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 1 1 37 329 1501 15677 a(n) = n! exp(-2) |1 - 1/n - ---- + ---- + ----- + ------ + ------ - ------- | 2 3 4 5 6 7 \ 2 n 3 n 24 n 120 n 720 n 2520 n 483989 39284461 737652869 \ - -------- - --------- - -----------| 8 9 10| 13440 n 362880 n 3628800 n / and in Maple input format: a(n) = n!*exp(-2)*(1-1/n-1/2/n^2+1/3/n^3+37/24/n^4+329/120/n^5+1501/720/n^6-\ 15677/2520/n^7-483989/13440/n^8-39284461/362880/n^9-737652869/3628800/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 2}, we have the following Theorem number, 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, 2} The first, 30, terms (for the sake of Sloane) are: [0, 1, 1, 4, 13, 82, 579, 4740, 43387, 439794, 4890741, 59216644, 775596313, 10927434466, 164806435783, 2649391469060, 45226435601207, 817056406224418, 15574618910994665, 312400218671253764, 6577618644576902053, 145051250421230224306, 3343382818203784146955, 80399425364623070680708, 2013619745874493923699123, 52441212770215183676081298, 1418087454121354412691790045, 39762923867612001445482824196, 1154647923129989496658559750193, 34682040826614983472734095531714] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients a(n) = n a(n - 1) + 3 a(n - 2) + (-2 n + 6) a(n - 3) - 3 a(n - 4) + (n - 6) a(n - 5) + a(n - 6) and in Maple input format: a(n) = n*a(n-1)+3*a(n-2)+(-2*n+6)*a(n-3)-3*a(n-4)+(n-6)*a(n-5)+a(n-6) Just for fun, the number of such permutations of length, 1000, is: 5440270940916427795620790501019929348872986505634963859163496814793721393032\ 975646735910228263562190416660571332341840924638926684962666045524728468\ 655736353141732090019473395400748937429526697386606995419378335171318096\ 106301149167571054919370893124489326731419501449702026342433919755398953\ 612594603550445234849294527106315776466854800883004895086503544641195592\ 980224990890630372706759567592591582739313159498110648743492003096534308\ 938960208301966655426036202037700431703362637967385059671765748426369194\ 142258860302322802336992306537812822150557840707626721299906651622934479\ 928976610540792199405191625640025268433788902448971143866568502725862664\ 111317720910636058655162094423864082211389746769685638412780789699938192\ 329578485503974656356403005801171057435653907188329339632389640064716212\ 467950571896177150473193968667178869169641709667346929682490083334255073\ 713368679669554478935765271377032592383001578525866569416125037963899252\ 624116377007897197433524650288771373945104731097577476117267394340631909\ 811922739042043996832208801864033262948233507024173501397149608896395244\ 568090537457183196538597763829831188417825075829679649255691667489078655\ 277585898990232736891902611965827815291401889322406438327748354864738253\ 783163156913367756698420817385067697870401290590046469501582742006154647\ 995386465634021598097432590129746056447803577956276055865052757087741871\ 322268232814975848414964622940988904121746055423067130196700263144105238\ 777454582746055279930633223556060223005615896020098399983197119362181616\ 216214463212412985613378224406723256435850665249550367862130347276860401\ 823211738429062389183565920156375222731984371049913516484197886656702433\ 771622539924373901733538375474289615031221869604903018823153621909703411\ 525874473540344656158573856267434431010600542460053738792753634630548300\ 393993574172023418845815427940007451290360013654584389890939952610930373\ 661186056146763001103664988486497451825466117077221839360614261219837925\ 586215157672453096114832714610581102844012346175941328668116879092317498\ 910518506512183850129257320485098632325094005470550702914437068729275250\ 123251245560747159257998416534963433651602788864927818638457846671092790\ 770293419767428146874492067502774966707977055545525461183631330051513346\ 897273880016424924951067531630007396818391082872741915831311202927935132\ 876502743871596754826339694516750801994796189772151203096490974963169726\ 657814340588542531950279270504499956018035150724072332411694695448260428\ 553905669079321780780066522722772710112586616603457914322056402867971902\ 1861571057928070111613283936655948656400004 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 1 1 37 329 1501 15677 a(n) = n! exp(-2) |1 - 1/n - ---- + ---- + ----- + ------ + ------ - ------- | 2 3 4 5 6 7 \ 2 n 3 n 24 n 120 n 720 n 2520 n 483989 39284461 737652869 \ - -------- - --------- - -----------| 8 9 10| 13440 n 362880 n 3628800 n / and in Maple input format: a(n) = n!*exp(-2)*(1-1/n-1/2/n^2+1/3/n^3+37/24/n^4+329/120/n^5+1501/720/n^6-\ 15677/2520/n^7-483989/13440/n^8-39284461/362880/n^9-737652869/3628800/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 3}, we have the following Theorem number, 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, 3} The first, 30, terms (for the sake of Sloane) are: [0, 0, 2, 2, 13, 80, 579, 4738, 43390, 439792, 4890741, 59216648, 775596313, 10927434464, 164806435822, 2649391469058, 45226435601207, 817056406224656, 15574618910994665, 312400218671253762, 6577618644576903790, 145051250421230224304, 3343382818203784146955, 80399425364623070694920, 2013619745874493923699123, 52441212770215183676081296, 1418087454121354412691920206, 39762923867612001445482824194, 1154647923129989496658559750193, 34682040826614983472734096851088] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients a(n) = (-176306831368154117109296638437667796 n 2 + 72659249736589754455889414176516745 n + 119807024040508327877105420391197588 3 - 13579047588890016386379066591386153 n 4 + 1285822062465925433334346986805514 n 5 6 - 59492157284621535216175990817003 n + 1060602820322515577766476557107 n 6 ) a(n - 1)/((n - 7) %1) + (2196405884907403341280991112421 n 5 - 103362040709802435745579311655200 n 4 + 1901319995061653533346933319973672 n 3 - 17202059822655717843627543698261207 n 2 + 77842435015380204761134672999932792 n - 148729497942766645239281761011763124 n + 38760797670634593564277261139086752) a(n - 2)/((n - 7) %1) + 1/3 ( 99281876889930262008367056824392392 n 2 + 39005530749975516774446901261011094 n - 466671503465177078169836658998000352 3 - 16691479117811553242704389448464767 n 4 + 2307723356499505831080091468597986 n 5 - 138587582417539265618610577724302 n 6 + 3068728616371514477240612116779 n ) a(n - 3)/((n - 7) %1) - 1/3 ( 1055796790211960035673018048960875564 n 2 - 532922676199965682998451782947913607 n - 704165150080587928177102272406215788 3 + 134876757134065865959515522785380741 n 4 - 19132353671772050643921655073453569 n 5 + 1531327991191265215499475103527817 n 6 7 - 63734568565911597527241897045431 n + 1060602820322515577766476557107 n ) a(n - 4)/((n - 7) %1) - 1/3 (942556663165826294787254949011020780 n - 234055068758780281633336891138397868 2 - 604979496389310960332869562506561547 n 3 + 174772004968760261289110954441791747 n 4 - 27480776940638874391500192742932055 n 5 + 2437897851574832342146358798261461 n 6 - 114344070134339452451984267217305 n 7 + 2196405884907403341280991112421 n ) a(n - 5)/((n - 7) %1) - 4/3 ( -239260595048310439777530977275126881 n + 431597356595575720955271493112082618 2 + 43564095558463079209508456350658236 n 3 - 353298717118651691871526584780446 n 4 - 934846792686831271741799680547127 n 5 + 134182618659919565965479056430548 n 6 7 - 7778382149509927261713365948146 n + 167343816337416574956177963306 n ) a(n - 6)/((n - 7) %1) - 1/3 (1117933571160599422875117280409186952 n - 816002803966116993710189733407458428 2 - 543654583463878807835825023422422517 n 3 + 134828561867364133742689954176273853 n 4 - 18917937336197194701076702394846905 n 5 + 1509119288508885613186477802978279 n 6 7 - 63065193300561931227417185192207 n + 1060602820322515577766476557107 n ) a(n - 7)/((n - 7) %1) - 1/3 (940290676019993419372870098913230596 n 2 - 604204857298029287752597270201770371 n - 231818524109542545668096002246058876 3 + 174661166145720057896129258121774515 n 4 - 27475552949287439911106866952668647 n 5 + 2437897851574832342146358798261461 n 6 - 114344070134339452451984267217305 n 7 + 2196405884907403341280991112421 n ) a(n - 8)/((n - 7) %1) - 1/3 ( -1400456509031109230491642211911596720 n 2 + 300437394576186901042779158901200358 n + 2363878678012525918579219740567993456 3 - 20149210571783750301089025759226467 n 4 - 2216571453614417224459047612665572 n 5 + 473071106318029038520422366674968 n 6 7 - 30052925777717193469086987235477 n + 669375265349666299824711853224 n ) a(n - 9)/((n - 7) %1) - 1/3 (-239981712148646842974819815794415776 n 2 + 142370062634114518048243424449927622 n 3 - 33015755779901676732407925621016827 n 4 + 3667088681305734199036118894441254 n 5 - 193147874949390566661101119546256 n 6 + 3851183726317213033124141524545 n + 27932742579275950074663037621907760 6 ) a(n - 10)/((n - 7) %1) - (2196405884907403341280991112421 n 5 - 96772823055080225721736338317937 n 4 + 1643947614170023906300939171706176 n 3 - 13551854893252359779561371134216751 n 2 + 55327056159599712349799726097487587 n - 94456552807262477019205160701993868 n + 23717192942047135531027631645488540) a(n - 11)/((n - 7) %1) - ( 6 5 669375265349666299824711853224 n - 24028548389570196770664580556461 n 4 + 253971601884717817619318164659124 n 3 + 86941805709053169435475944100814 n 2 - 17493080294397375522169246964018067 n + 107815427677779687059319964146911148 n - 209952987152854300941874885575055020) a(n - 12)/((n - 7) %1) - 2 ( 5 4 334687632674833149912355926612 n - 8761537912465969107112158788485 n 3 + 48489398075883427869354122915641 n 2 + 265132733011650670575172186110835 n - 3196975838814333464752684570256398 n + 7915788762952149617128296276311520) a(n - 13)/((n - 7) %1) 4 3 %1 := 1060602820322515577766476557107 n - 49871531657456522830529663804833 n 2 + 835164478483861891838399254925021 n - 5905559959148837334589831126820472 n + 15265453618222364999380535604715140 and in Maple input format: a(n) = (-176306831368154117109296638437667796*n+ 72659249736589754455889414176516745*n^2+119807024040508327877105420391197588-\ 13579047588890016386379066591386153*n^3+1285822062465925433334346986805514*n^4-\ 59492157284621535216175990817003*n^5+1060602820322515577766476557107*n^6)/(n-7) /(1060602820322515577766476557107*n^4-49871531657456522830529663804833*n^3+ 835164478483861891838399254925021*n^2-5905559959148837334589831126820472*n+ 15265453618222364999380535604715140)*a(n-1)+(2196405884907403341280991112421*n^ 6-103362040709802435745579311655200*n^5+1901319995061653533346933319973672*n^4-\ 17202059822655717843627543698261207*n^3+77842435015380204761134672999932792*n^2 -148729497942766645239281761011763124*n+38760797670634593564277261139086752)/(n -7)/(1060602820322515577766476557107*n^4-49871531657456522830529663804833*n^3+ 835164478483861891838399254925021*n^2-5905559959148837334589831126820472*n+ 15265453618222364999380535604715140)*a(n-2)+1/3*( 99281876889930262008367056824392392*n+39005530749975516774446901261011094*n^2-\ 466671503465177078169836658998000352-16691479117811553242704389448464767*n^3+ 2307723356499505831080091468597986*n^4-138587582417539265618610577724302*n^5+ 3068728616371514477240612116779*n^6)/(n-7)/(1060602820322515577766476557107*n^4 -49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-3 )-1/3*(1055796790211960035673018048960875564*n-\ 532922676199965682998451782947913607*n^2-704165150080587928177102272406215788+ 134876757134065865959515522785380741*n^3-19132353671772050643921655073453569*n^ 4+1531327991191265215499475103527817*n^5-63734568565911597527241897045431*n^6+ 1060602820322515577766476557107*n^7)/(n-7)/(1060602820322515577766476557107*n^4 -49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-4 )-1/3*(942556663165826294787254949011020780*n-\ 234055068758780281633336891138397868-604979496389310960332869562506561547*n^2+ 174772004968760261289110954441791747*n^3-27480776940638874391500192742932055*n^ 4+2437897851574832342146358798261461*n^5-114344070134339452451984267217305*n^6+ 2196405884907403341280991112421*n^7)/(n-7)/(1060602820322515577766476557107*n^4 -49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-5 )-4/3*(-239260595048310439777530977275126881*n+ 431597356595575720955271493112082618+43564095558463079209508456350658236*n^2-\ 353298717118651691871526584780446*n^3-934846792686831271741799680547127*n^4+ 134182618659919565965479056430548*n^5-7778382149509927261713365948146*n^6+ 167343816337416574956177963306*n^7)/(n-7)/(1060602820322515577766476557107*n^4-\ 49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-6 )-1/3*(1117933571160599422875117280409186952*n-\ 816002803966116993710189733407458428-543654583463878807835825023422422517*n^2+ 134828561867364133742689954176273853*n^3-18917937336197194701076702394846905*n^ 4+1509119288508885613186477802978279*n^5-63065193300561931227417185192207*n^6+ 1060602820322515577766476557107*n^7)/(n-7)/(1060602820322515577766476557107*n^4 -49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-7 )-1/3*(940290676019993419372870098913230596*n-\ 604204857298029287752597270201770371*n^2-231818524109542545668096002246058876+ 174661166145720057896129258121774515*n^3-27475552949287439911106866952668647*n^ 4+2437897851574832342146358798261461*n^5-114344070134339452451984267217305*n^6+ 2196405884907403341280991112421*n^7)/(n-7)/(1060602820322515577766476557107*n^4 -49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-8 )-1/3*(-1400456509031109230491642211911596720*n+ 300437394576186901042779158901200358*n^2+2363878678012525918579219740567993456-\ 20149210571783750301089025759226467*n^3-2216571453614417224459047612665572*n^4+ 473071106318029038520422366674968*n^5-30052925777717193469086987235477*n^6+ 669375265349666299824711853224*n^7)/(n-7)/(1060602820322515577766476557107*n^4-\ 49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-9 )-1/3*(-239981712148646842974819815794415776*n+ 142370062634114518048243424449927622*n^2-33015755779901676732407925621016827*n^ 3+3667088681305734199036118894441254*n^4-193147874949390566661101119546256*n^5+ 3851183726317213033124141524545*n^6+27932742579275950074663037621907760)/(n-7)/ (1060602820322515577766476557107*n^4-49871531657456522830529663804833*n^3+ 835164478483861891838399254925021*n^2-5905559959148837334589831126820472*n+ 15265453618222364999380535604715140)*a(n-10)-(2196405884907403341280991112421*n ^6-96772823055080225721736338317937*n^5+1643947614170023906300939171706176*n^4-\ 13551854893252359779561371134216751*n^3+55327056159599712349799726097487587*n^2 -94456552807262477019205160701993868*n+23717192942047135531027631645488540)/(n-\ 7)/(1060602820322515577766476557107*n^4-49871531657456522830529663804833*n^3+ 835164478483861891838399254925021*n^2-5905559959148837334589831126820472*n+ 15265453618222364999380535604715140)*a(n-11)-(669375265349666299824711853224*n^ 6-24028548389570196770664580556461*n^5+253971601884717817619318164659124*n^4+ 86941805709053169435475944100814*n^3-17493080294397375522169246964018067*n^2+ 107815427677779687059319964146911148*n-209952987152854300941874885575055020)/(n -7)/(1060602820322515577766476557107*n^4-49871531657456522830529663804833*n^3+ 835164478483861891838399254925021*n^2-5905559959148837334589831126820472*n+ 15265453618222364999380535604715140)*a(n-12)-2*(334687632674833149912355926612* n^5-8761537912465969107112158788485*n^4+48489398075883427869354122915641*n^3+ 265132733011650670575172186110835*n^2-3196975838814333464752684570256398*n+ 7915788762952149617128296276311520)/(n-7)/(1060602820322515577766476557107*n^4-\ 49871531657456522830529663804833*n^3+835164478483861891838399254925021*n^2-\ 5905559959148837334589831126820472*n+15265453618222364999380535604715140)*a(n-\ 13) Just for fun, the number of such permutations of length, 1000, is: 5440270940916427795620790501019929348872986505634963859163496814793721393032\ 975646735910228263562190416660571332341840924638926684962666045524728468\ 655736353141732090019473395400748937429526697386606995419378335171318096\ 106301149167571054919370893124489326731419501449702026342433919755398953\ 612594603550445234849294527106315776466854800883004895086503544641195592\ 980224990890630372706759567592591582739313159498110648743492003096534308\ 938960208301966655426036202037700431703362637967385059671765748426369194\ 142258860302322802336992306537812822150557840707626721299906651622934479\ 928976610540792199405191625640025268433788902448971143866568502725862664\ 111317720910636058655162094423864082211389746769685638412780789699938192\ 329578485503974656356403005801171057435653907188329339632389640064716212\ 467950571896177150473193968667178869169641709667346929682490083334255073\ 713368679669554478935765271377032592383001578525866569416125037963899252\ 624116377007897197433524650288771373945104731097577476117267394340631909\ 811922739042043996832208801864033262948233507024173501397149608896395244\ 568090537457183196538597763829831188417825075829679649255691667489078655\ 277585898990232736891902611965827815291401889322406438327748354864738253\ 783163156913367756698420817385067697870401290590046469501582742006154647\ 995386465634021598097432590129746056447803577956276055865052757087741871\ 322268232814975848414964622940988904121746055423067130196700263144105238\ 777454582746055279930633223556060223005615896020098399983197119362181616\ 216214463212412985613378224406723256435850665249550367862130347276860401\ 823211738429062389183565920156375222731984371049913516484197886656702433\ 771622539924373901733538375474289615031221869604903018823153621909703411\ 525874473540344656158573856267434431010600542460053738792753634630548300\ 393993574172023418845815427940007451290360013654584389890939952610930373\ 661186056146763001103664988486497451825466117077221839360614261219837925\ 586215157672453096114832714610581102844012346175941328668116879092317498\ 910518506512183850129257320485098632325094005470550702914437068729275250\ 123251245560747159257998416534963433651602788864927818638457846671092790\ 770293419767428146874492067502774966707977055545525461183631330051513346\ 897273880016424924951067531630007396818391082872741915831311202927935132\ 876502743871596754826339694516750801994796189772151203096490974963169726\ 657814340588542531950279270504499956018035150724072332411694695448260428\ 553905669079321780780066522722772710112586616603457914322056402867971902\ 1861571057928070111613283936655948656400002 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 1 1 37 329 1501 15677 a(n) = n! exp(-2) |1 - 1/n - ---- + ---- + ----- + ------ + ------ - ------- | 2 3 4 5 6 7 \ 2 n 3 n 24 n 120 n 720 n 2520 n 483989 39284461 737652869 \ - -------- - --------- - -----------| 8 9 10| 13440 n 362880 n 3628800 n / and in Maple input format: a(n) = n!*exp(-2)*(1-1/n-1/2/n^2+1/3/n^3+37/24/n^4+329/120/n^5+1501/720/n^6-\ 15677/2520/n^7-483989/13440/n^8-39284461/362880/n^9-737652869/3628800/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 1, 2}, we have the following Theorem number, 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} The first, 30, terms (for the sake of Sloane) are: [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] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients 2 3 4 (6431397 n - 387535244 + 27153456 n - 4355236 n + 209525 n ) a(n - 1) a(n) = ----------------------------------------------------------------------- %1 2 3 4 - (-767593401 n + 1107648678 + 182073564 n - 18113182 n + 636805 n ) a(n - 2)/(%1) - 2 3 4 (-181211187 n - 216273324 + 90863930 n - 13049248 n + 628575 n ) a(n - 3) /(%1) + 2 2 3 4 (-1515827027 n + 2618069676 + 325603849 n - 30633346 n + 1059970 n ) a(n - 4)/(%1) - 2 3 4 (-770414435 n + 1503639416 + 140365492 n - 10273730 n + 217755 n ) a(n - 5)/(%1) - 2 3 4 (-2067204229 n + 3653627246 + 440990756 n - 41871670 n + 1483135 n ) a(n - 6)/(%1) + 2 3 4 (2076897952 - 1122448055 n + 225659318 n - 19822302 n + 636805 n ) 3 2 (636805 n - 13244727 n + 88630827 n - 198640570) a(n - 8) a(n - 7)/(%1) + ----------------------------------------------------------- %1 2 3 %1 := 43372683 n - 130719614 - 4992041 n + 209525 n and in Maple input format: a(n) = (6431397*n-387535244+27153456*n^2-4355236*n^3+209525*n^4)/(43372683*n-\ 130719614-4992041*n^2+209525*n^3)*a(n-1)-(-767593401*n+1107648678+182073564*n^2 -18113182*n^3+636805*n^4)/(43372683*n-130719614-4992041*n^2+209525*n^3)*a(n-2)- (-181211187*n-216273324+90863930*n^2-13049248*n^3+628575*n^4)/(43372683*n-\ 130719614-4992041*n^2+209525*n^3)*a(n-3)+2*(-1515827027*n+2618069676+325603849* n^2-30633346*n^3+1059970*n^4)/(43372683*n-130719614-4992041*n^2+209525*n^3)*a(n -4)-(-770414435*n+1503639416+140365492*n^2-10273730*n^3+217755*n^4)/(43372683*n -130719614-4992041*n^2+209525*n^3)*a(n-5)-(-2067204229*n+3653627246+440990756*n ^2-41871670*n^3+1483135*n^4)/(43372683*n-130719614-4992041*n^2+209525*n^3)*a(n-\ 6)+(2076897952-1122448055*n+225659318*n^2-19822302*n^3+636805*n^4)/(43372683*n-\ 130719614-4992041*n^2+209525*n^3)*a(n-7)+(636805*n^3-13244727*n^2+88630827*n-\ 198640570)/(43372683*n-130719614-4992041*n^2+209525*n^3)*a(n-8) Just for fun, the number of such permutations of length, 1000, is: 1997357104526440050823670133361393763351343999034986856015347022472209490372\ 312926872572397925675976763606183161877945369176660049398820699233866697\ 062359934605421595970153829913719611211413272639994265788570072593123604\ 169159491896726814196357551240694540802566128522986612467349954124609333\ 349436875803235021899408864874564022949028981622942209294317694260604903\ 757641174429968152150257002402534970651334965436038250585556252098240832\ 958864341746754385637054810018628749912015082921286261669672137900257855\ 560642881983550185844277031713178308397061201061735559900190402392551853\ 045500732923059289005321464839843630204329805742206576601054064586937505\ 069523657473974627137892179126392768266945577913814365973411932382722339\ 059954989361196366570760269874510606677951445449037116066373596424300927\ 189633691964474741328156281034856598645910931632542936162870694629236381\ 252394592881451011338379507498780602747835041517639200058204650241985075\ 882540399588938915209479129002160715886548011779685173997147335051457609\ 628624253212126795180153026634453371262035973213935656087949206396704045\ 339608404256681756008066676356182289898008864667113915048480693624091265\ 314410309114573153065731371079830487739098962909781032608913237665182575\ 568351193632535304696865335448127917594851451777444217489885019215783131\ 770652490060076243111781944621105207652733839674608766562483254374287678\ 044016457294796917635764940322650551221921741651707902006749304874798453\ 950400488399793933885967753289576361997343552357402078379522534111956966\ 108774429861805998735737311680967207907932617404973003027740307891469623\ 865777241546060481536445133029099405194120823126900228242220573159796007\ 661666616656205113480287700750205698138215647824968859779466595523220730\ 693308654126756715881476406212936948547173508211972039202567939090770435\ 157852235373744103237168561432319720051343070224159711816516382947539948\ 809235652656984180349630930239532069704529578842413959197322680749004385\ 921649767641989276562057551465592370622847469412584738721325763689463668\ 404649490626831281802420961801235074934350899618747965707751070245449989\ 558756428606345300005182061738146445926074258991723118550659476192541050\ 621318607687809693921498764910975847553221645142964981502005575019385428\ 578933336319506433094688888577820809046011984042885619162695563737051965\ 787278435083610548596936123162182405688424913863033004438903144658164751\ 303384404186190985835489319220977701798665636165726009013212901211126143\ 617173899872027335352011071266866062794362935056343138994400831264393470\ 0054477692411815408514070783478943605028129 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 1 4 95 1029 12823 9109 a(n) = n! exp(-3) |1 - 3/n - ---- + ---- + ---- + ----- + ------ + ----- | 2 3 4 5 6 7 \ 2 n n 8 n 40 n 240 n 70 n 1883337 21602179 260569179\ + ------- + -------- + ---------| 8 9 10| 4480 n 13440 n 44800 n / and in Maple input format: a(n) = n!*exp(-3)*(1-3/n-1/2/n^2+4/n^3+95/8/n^4+1029/40/n^5+12823/240/n^6+9109/ 70/n^7+1883337/4480/n^8+21602179/13440/n^9+260569179/44800/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 1, 3}, we have the following Theorem number, 5 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, 3} The first, 30, terms (for the sake of Sloane) are: [0, 0, 1, 1, 2, 17, 144, 1249, 12006, 126125, 1441888, 17847657, 238019298, 3404316088, 52001848016, 845154325281, 14564549139574, 265313246182181, 5094530031699980, 102855047082584249, 2178280324043183736, 48288638312758659645, 1118334051990694257716, 27009300638208116324289, 679125639699909648318662, 17750691198601720706675593, 481604000010431373825542604, 13545623306035396933693933256, 394462074687072071543869348906, 11879748361031864591653098871817] -------------------------------------------- If pi[i]-i is never in, {0, 2, 3}, we have the following Theorem number, 6 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, 2, 3} The first, 30, terms (for the sake of Sloane) are: [0, 0, 1, 1, 2, 17, 144, 1249, 12006, 126125, 1441888, 17847657, 238019298, 3404316088, 52001848016, 845154325281, 14564549139574, 265313246182181, 5094530031699980, 102855047082584249, 2178280324043183736, 48288638312758659645, 1118334051990694257716, 27009300638208116324289, 679125639699909648318662, 17750691198601720706675593, 481604000010431373825542604, 13545623306035396933693933256, 394462074687072071543869348906, 11879748361031864591653098871817] -------------------------------------------- If pi[i]-i is never in, {0, 1, 2, 3}, we have the following Theorem number, 7 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} The first, 30, terms (for the sake of Sloane) are: [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] -------------------------------------------------------- This ends this screen-turning book, that took, 769.081, secs. to generate.