On the Enumeration of Generalized Menages Numbers for sets containg 0 and largest element, 3 By Shalosh B. Ekhad -------------------------------------------- If pi[i]-i is never in, {0}, we have the following Theorem number, 1 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0} The first, 30, terms (for the sake of Sloane) are: [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] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients a(n) = (n - 1) a(n - 1) + (n - 1) a(n - 2) and in Maple input format: a(n) = (n-1)*a(n-1)+(n-1)*a(n-2) Just for fun, the number of such permutations of length, 1000, is: 1480300003716690803639166141189660542377872467716834615546918460898888171222\ 360711813189873910548675459590726189130673952565926739378359567722411682\ 225282955956835967209806662206094278319048852420295993918145867464929632\ 177223403177771955752603660100590106551721447382848788617582081310047350\ 358184775693687864320616320161884468076859109403218325729966499814817722\ 523251910400861544265546575384584445357657178710339466137717023503056252\ 650043203882433860978792626830828468703859597819544889563899703925789442\ 886604592950312345074787367168818241367836225845351388059822881452853157\ 092920449246805492179297901159845450144415217557357263061954571997705726\ 917546636177873914180435642912954635442323456238142340910752454816552406\ 177681946008016133704545795503609904692149425055853719332957948207301824\ 597654871393025676689264387133050350749500959081818757218706290284427041\ 888179306280825957697116463097109027133895778139249850841954896876020466\ 195020089609619793369712000118458329727664968204252323090144241603833525\ 494325871758045995132242953876207932374921331061948547816753352642454433\ 684063497786265771541539361657951764142802467082096842550210948234219667\ 949312586019262378885020630611799089203891224372800966941803187567295401\ 877435229552876934033446271920081932431500479266831162067898087375203299\ 321759266896310398013332052717730686941198866814394082086345366161621254\ 849682464332990866189720387263201435245301591551228160672094793591589751\ 046761756899429729095389819155186104380589668134545521358106176432683265\ 088847400075630578125577568721198279481770124987200028465843200836028835\ 056752239304157102409433831420876970912375704827813522561628095930489973\ 076363690716903735444753347277222269644018381058041040336988590465080726\ 362211212847672561792613846955758001267778719146087997403331351690780850\ 403018707387007219860265183241445978545343939401105488747714567335488196\ 900148911502998833745690361445040756502842471542911226022625777386345023\ 944680666372606015155904126779976563721389884798926297873448554696259931\ 889022153417439765913357861346124264844165570744850851379226488885571276\ 189802041073412065174561117871776566686203971568747523655416897364591156\ 339098482517035347569029493318500822966694103069801757199864821884463334\ 464508239561580295442683950514237400428199863686124549042552063736848425\ 988571362282393268539068601119113908474985451813508750353980668686219599\ 738700364731082064708908051255917660356516602631662560718590665234944049\ 328739892430338853873103631687347396881324950657650842869854703810748598\ 52651721482664917019227944750044815550686001 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is a(n) = n! exp(-1) and in Maple input format: a(n) = n!*exp(-1) -------------------------------------------- If pi[i]-i is never in, {0, 1}, we have the following Theorem number, 2 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 1} The first, 30, terms (for the sake of Sloane) are: [0, 0, 1, 3, 16, 96, 675, 5413, 48800, 488592, 5379333, 64595975, 840192288, 11767626752, 176574062535, 2825965531593, 48052401132800, 865108807357216, 16439727718351881, 328839946389605643, 6906458590966507696, 151957709012196732000, 3495340527215980878955, 83894765891839051559661, 2097514511766332975258784, 54538727281981516651340080, 1472626181403335929343130125, 41235550049015337374825954319, 1195883473179004834033385704512, 35877924299793988306767481236224] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients a(n) = (n - 1) a(n - 1) + (n - 1) a(n - 2) + a(n - 3) and in Maple input format: a(n) = (n-1)*a(n-1)+(n-1)*a(n-2)+a(n-3) Just for fun, the number of such permutations of length, 1000, is: 5445716657568539716376786127516629098007154277792761372775511628662023389080\ 425024144303622656884674772955106122638956063353006039290843186424138279\ 292299907647288824111961857344911212411916103477301586915281935717830926\ 306482349192926697910649723612830138514885829304111381257160654172100763\ 480076782860725482912645993444877447133015643752999237799817344031077949\ 216776091206502340188373063723499623736995384138933438676160348089115726\ 718242738666112217322705070054507219792636552614306337740312463474245454\ 147557313359700444561506777750216903349264090829854983908944697845217997\ 331491081764599066886243114374164891374785780741214768205421601422644978\ 261861024567061653295461414673384981463359272089220686270542400537736929\ 936491298556962363866489362504736854265851891983633133205030611049420959\ 123367753874172248395466133009661534735233423516792203879095205704385958\ 040828540510160963939507751931327936612071781101659669918846072529709133\ 617683159148086984954815854976297875405762187177699861954238442662167963\ 246005657739794465954068429790582169500465754814750413439681336469833673\ 399895376719821525140108789424992557287818955951719420955360489644534186\ 041309419659269173842288238013687494526972842784640090171423810580506280\ 550894081323203264057282032481227032548415076759204823957872119956017816\ 109641860722654760680094796423997569907137699671776942137887975552016139\ 246477007351789915702069884402278021673452111028779244610966065436208483\ 301876065500700701703915179144226971122339534218868720261904572051054923\ 285491017850454218528169824483814229101242930992650582314481132655637858\ 450760367921871712157037083631864170353210646784681961130243064752168413\ 058434087258306604398111745057735234076915797847293664277139617705592752\ 197547836024380292540791244419490162476961381810536310566774444806294614\ 914646719260722951489275296454795325540471786725310000708938610565272450\ 330363730429206745464044978062695038882768707753375026991751487976597696\ 574993834824015172324087418478350884357981902231846035639248903506080154\ 303742722841966359621339695615990826895820782564148772251415637162279500\ 299159452138979073705354684763363314050097619705646469276135782146317415\ 647339780531202694715691352809965277890559990648024668359049752164044538\ 772836114569461167391224699163866935072856756165369194896082977801120553\ 121971858565819290114090120647136655421697388046752523612848505940909683\ 029311176387719820873433927910328293399345574906392889598014966975954467\ 817611389637940928963150701174052356241172754924527504415540850210812132\ 4990218879587910639341682838820267263006101 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 1 1 3 67 245 1087 a(n) = n! exp(-2) |- ---- + 1 - ---- + ---- + ----- + ------ + ------- | 2 3 4 5 6 7 \ 2 n 6 n 8 n 60 n 144 n 1680 n 12299 2648707 32185541 \ - ------- - -------- - ----------| 8 9 10| 1920 n 90720 n 403200 n / and in Maple input format: a(n) = n!*exp(-2)*(-1/2/n^2+1-1/6/n^3+3/8/n^4+67/60/n^5+245/144/n^6+1087/1680/n ^7-12299/1920/n^8-2648707/90720/n^9-32185541/403200/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 2}, we have the following Theorem number, 3 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 2} The first, 30, terms (for the sake of Sloane) are: [0, 1, 1, 5, 20, 117, 791, 6205, 55004, 543597, 5922929, 70518905, 910711192, 12678337945, 189252400479, 3015217932073, 51067619064872, 916176426422089, 17355904144773969, 346195850534379613, 7252654441500887308, 159210363453697619309, 3654550890669678498263, 87549316782508730057925, 2185063828548841705316708, 56723791110530358356656789, 1529349972513866287699786913, 42764900021529203662525741233, 1238648373200534037695911445744, 37116572672994522344463392681969] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients a(n) = (n - 1) a(n - 1) + (n - 1) a(n - 2) + (-n + 2) a(n - 3) + (-n + 2) a(n - 4) - a(n - 5) and in Maple input format: a(n) = (n-1)*a(n-1)+(n-1)*a(n-2)+(-n+2)*a(n-3)+(-n+2)*a(n-4)-a(n-5) Just for fun, the number of such permutations of length, 1000, is: 5451167830856042117052092122553903305542295555332908757571075178216031018599\ 825538846829527474261181730731573910251273870401185402682757927535183037\ 202836429093066122954992588396588867136232949554491015050587974201365810\ 559025947270150875431448219490385053861753989645625182436559578632333233\ 475897979537670149809349626180909509614484224932352196439733856151422295\ 280271997512539341629594007353072704266618402493303815968647815491700078\ 072410939564642839683729698463070782895761260225790690588332971635476644\ 468021193463022434552882542597808153938775955324975929848352578546597815\ 631345207149146691256228384725201320419754980949617318984585830155195114\ 520652563902775842295772767597890905227344386063062120134122986957198054\ 090295352255614667372308255153955082484456825229295836053097915261123394\ 456657507985586922044754241750063506948436811944196244139530811327868950\ 093094971902499143340564898166221089710814615010437008535010634325325198\ 924587615945728730867155585838799798456306971160488427066858595963200084\ 904166501031572809731044680087410790136013730038172163663956067563266584\ 337386859611588420220399959210262757164049546052196437842630713754588388\ 077616610348209398916268817869373706807661378672581205135841285209511955\ 160067025294849290314520493307691035468007709492461323636889029642908589\ 876955840213018512865482916894767720842157342639576907957192774530370805\ 474399229243233138925261065095469754995705017162968274084603131667468234\ 117813379491578463916797515490575299028624646635805777171556243210377232\ 427302564452755989843799968291020274704257946912694979604785618983270379\ 678967118094214835695920106943358444067650767285113273707745106693524084\ 441315912136205316420187358646990336629417625983601596140466329463288573\ 899955319578859072725821498340009936691782323813527901396699352625733212\ 287883654092611873073257176400856312214900822175132065438303257371874823\ 483758093588060985801805041906183993658257008791492162666635642045773454\ 823462641220825890156674972769330175392726777412521633505741432511337858\ 445255525831599677051143198736556676117865452530591884593829935999066255\ 589658856171689588876054942229179353210785437109726180588996160052384360\ 425223842073496678986227531284918561431231884985119545046624237896067461\ 693261894415651093639851824872395248570412765962854492721736669198036152\ 335412921691685302746255181449822401793356188370195448240044964816467347\ 667056759858952721156960581733919017175408060304165113712625096050547784\ 113513114361846080774676300335039301577323057305726967392706775587074375\ 6453848757444538301164528690697506288181101 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 1 4 89 453 27979 189061 a(n) = n! exp(-2) |1 + 1/n + ---- + ---- + ----- + ----- + ------ + ------- | 2 3 4 5 6 7 \ 2 n 3 n 24 n 40 n 720 n 1260 n 26000057 1103411357 56391087941\ + -------- + ---------- + -----------| 8 9 10| 40320 n 362880 n 3628800 n / and in Maple input format: a(n) = n!*exp(-2)*(1+1/n+1/2/n^2+4/3/n^3+89/24/n^4+453/40/n^5+27979/720/n^6+ 189061/1260/n^7+26000057/40320/n^8+1103411357/362880/n^9+56391087941/3628800/n^ 10) -------------------------------------------- If pi[i]-i is never in, {0, 3}, we have the following Theorem number, 4 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 3} The first, 30, terms (for the sake of Sloane) are: [0, 1, 2, 6, 26, 142, 933, 7136, 62141, 605735, 6528661, 77047567, 987758752, 13666096679, 202918497170, 3218136429206, 54285755493978, 970462181916142, 18326366326689899, 364522216861068816, 7617176658361956683, 166827540112059574525, 3821378430781738067259, 91370695213290468129805, 2276434523762132173434896, 59000225634292490530042093, 1588350198148158778229871602, 44353250219677362440755509030, 1283001623420211400136666459978, 38399574296414733744600059575534] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients 5 4 3 2 a(n) = (3909357 n - 89175465 n + 749970393 n - 2832899472 n + 4368099775 n - 1091350208) a(n - 1)/(%1) - 2 4 3 2 (4649103 n - 92982060 n + 631045254 n - 1664202846 n + 1398036335) 5 4 3 a(n - 2)/(%1) - 1/3 (7818714 n - 221882976 n + 2353993905 n 2 - 11543448525 n + 25210182275 n - 18031037218) a(n - 3)/(%1) - 1/3 ( 6 5 4 3 2 3909357 n - 100903536 n + 1029224859 n - 5284407096 n + 14111593573 n 5 - 17366452322 n + 6007302558) a(n - 4)/(%1) + 2/3 (4649103 n 4 3 2 - 119397186 n + 1181324424 n - 5677546950 n + 13499524565 n 6 5 - 12983017492) a(n - 5)/(%1) + 1/3 (3909357 n - 106292385 n 4 3 2 + 1146618537 n - 6258180447 n + 17731999468 n - 22795039061 n 6 5 + 7813232190) a(n - 6)/(%1) - 1/3 (3909357 n - 128269035 n 4 3 2 + 1696034787 n - 11501316033 n + 41437408258 n - 71859914199 n 5 4 + 41186211380) a(n - 7)/(%1) + 2/3 (4649103 n - 113057964 n 3 2 + 1054539984 n - 4614904170 n + 9212318765 n - 6520397158) a(n - 8)/(%1) 6 5 4 3 + 1/3 (3909357 n - 133657884 n + 1848083559 n - 13168191264 n 2 + 50482486093 n - 96880126338 n + 70347030638) a(n - 9)/(%1) - 1/3 ( 5 4 3 2 7818714 n - 169052724 n + 1297388865 n - 4133723025 n + 3943179275 n + 3238521968) a(n - 10)/(%1) + 2 4 3 2 (4649103 n - 92982060 n + 631045254 n - 1658496234 n + 1369503275) 5 4 3 2 a(n - 11)/(%1) + (3909357 n - 106292385 n + 1092308793 n - 5254503318 n + 11467218235 n - 8451143342) a(n - 12)/(%1) + 4 3 2 (3909357 n - 67198815 n + 414931794 n - 1045521039 n + 831191410) a(n - 13)/(%1) 4 3 2 %1 := 3909357 n - 89175465 n + 744581544 n - 2730898341 n + 3763915420 and in Maple input format: a(n) = (3909357*n^5-89175465*n^4+749970393*n^3-2832899472*n^2+4368099775*n-\ 1091350208)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a( n-1)-2*(4649103*n^4-92982060*n^3+631045254*n^2-1664202846*n+1398036335)/( 3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a(n-2)-1/3*( 7818714*n^5-221882976*n^4+2353993905*n^3-11543448525*n^2+25210182275*n-\ 18031037218)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a (n-3)-1/3*(3909357*n^6-100903536*n^5+1029224859*n^4-5284407096*n^3+14111593573* n^2-17366452322*n+6007302558)/(3909357*n^4-89175465*n^3+744581544*n^2-\ 2730898341*n+3763915420)*a(n-4)+2/3*(4649103*n^5-119397186*n^4+1181324424*n^3-\ 5677546950*n^2+13499524565*n-12983017492)/(3909357*n^4-89175465*n^3+744581544*n ^2-2730898341*n+3763915420)*a(n-5)+1/3*(3909357*n^6-106292385*n^5+1146618537*n^ 4-6258180447*n^3+17731999468*n^2-22795039061*n+7813232190)/(3909357*n^4-\ 89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a(n-6)-1/3*(3909357*n^6-\ 128269035*n^5+1696034787*n^4-11501316033*n^3+41437408258*n^2-71859914199*n+ 41186211380)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a (n-7)+2/3*(4649103*n^5-113057964*n^4+1054539984*n^3-4614904170*n^2+9212318765*n -6520397158)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a (n-8)+1/3*(3909357*n^6-133657884*n^5+1848083559*n^4-13168191264*n^3+50482486093 *n^2-96880126338*n+70347030638)/(3909357*n^4-89175465*n^3+744581544*n^2-\ 2730898341*n+3763915420)*a(n-9)-1/3*(7818714*n^5-169052724*n^4+1297388865*n^3-\ 4133723025*n^2+3943179275*n+3238521968)/(3909357*n^4-89175465*n^3+744581544*n^2 -2730898341*n+3763915420)*a(n-10)+2*(4649103*n^4-92982060*n^3+631045254*n^2-\ 1658496234*n+1369503275)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+ 3763915420)*a(n-11)+(3909357*n^5-106292385*n^4+1092308793*n^3-5254503318*n^2+ 11467218235*n-8451143342)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+ 3763915420)*a(n-12)+(3909357*n^4-67198815*n^3+414931794*n^2-1045521039*n+ 831191410)/(3909357*n^4-89175465*n^3+744581544*n^2-2730898341*n+3763915420)*a(n -13) Just for fun, the number of such permutations of length, 1000, is: 5456624466252000569460768798583929061984258177552625841074461812877735828328\ 682584994668235323381014952046284789105339540499872546016917414834677601\ 000090541616978923247798423008709305889646703563210989510803629881259407\ 770285424889241929615874476329469152768361963922387377266467329465994590\ 424252589951578871602761366061102062412856635652435237610616340907300824\ 151089177675630291087514928670328405211140313840859123817902004697194730\ 574640149618423715997209501260620509905972439573641791753828091299374030\ 536348599849746495539482519803502290608501320661752909068604429535415977\ 141356589705909335158899363641664078229874024874135466566055261203542080\ 361238999921790007200848214690373682420227814356045809337402078647367071\ 524011755390046240895712832991390349631360487689487273436580391855316597\ 740505535889748650415005336154426095392186617050534720094495154589752783\ 554227862925914962394457356326886000458069457853974456870795666262661473\ 497558758886522692285666016433293819346916255048174363190171116359304103\ 168907599387781845518271148748246676580539055219818024319310037304070072\ 688199322110635685908364813234858722769151018043607480726088469897572347\ 925566747254094091009611050727864833781643439255454188239589259410847463\ 445864044772116473143806513016232123142943096832521097313896464842249837\ 174692757743481661882589161477119520991062212325143019788853484736467830\ 275557583859981478663069685081702299136640310812312436998354378446109250\ 256187206400806462068343211891461680139319255311702223937432811932100389\ 263095474798788946181604111951967060382364103513988446971523336918830983\ 622423273978043432412468465946104365001920397632716058480491925115567261\ 886221879151589574395020409243276732092402561204805567177127406347430945\ 995184354563232891253661200176631861892317876916825671265170747809324228\ 926334085835141445423815805179260283916212409932899507835640588833958690\ 435675448293674206362514219375854636799686080611866712639111041815849999\ 688058756053103011230324488137678003775810193627751733692609934079541648\ 381280387608403951615217286078153698572052268911734548346101280943758424\ 034684714308185489563121670294820959758599551335691587497411586892622827\ 691964581362541042006355583898716768799218662823793240010718489758261624\ 801712517306199113504636370166415953631937766307759451901296402549632000\ 730561259948442019555043084667528404861113303513114969656027488103563374\ 832997855297918779578730234174611716100073663673380522275046535122402862\ 352303108005583298476146528735574243248548397442898514319037235196648234\ 6409983625754419592664733459475463150665414 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 5 35 397 823 148963 876481 a(n) = n! exp(-2) |1 + 2/n + ---- + ---- + ----- + ----- + ------ + ------- | 2 3 4 5 6 7 \ 2 n 6 n 24 n 15 n 720 n 1008 n 3596597 3651930787 56331867943\ + ------- + ---------- + -----------| 8 9 10 | 896 n 181440 n 518400 n / and in Maple input format: a(n) = n!*exp(-2)*(1+2/n+5/2/n^2+35/6/n^3+397/24/n^4+823/15/n^5+148963/720/n^6+ 876481/1008/n^7+3596597/896/n^8+3651930787/181440/n^9+56331867943/518400/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 1, 2}, we have the following Theorem number, 5 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 1, 2} The first, 30, terms (for the sake of Sloane) are: [0, 0, 0, 1, 5, 33, 236, 1918, 17440, 175649, 1942171, 23396353, 305055960, 4280721564, 64330087888, 1030831875953, 17545848553729, 316150872317105, 6012076099604308, 120330082937778554, 2528525819886170112, 55657855167451780993, 1280736404605380413303, 30750394025631567131329, 769039694784998460886896, 20001468420258808491667512, 540194118569060356429415712, 15129297070110498161942887009, 438850019810675038935803418941, 13168211505240199345047950457921] a(n) satisfies the following homogeneous linear recurrence with polynomial coefficients 2 (n - 8 n - 1) a(n - 1) 4 (n - 6) a(n - 2) a(n) = ----------------------- + ------------------ n - 8 n - 8 2 2 (3 n - 33 n + 76) a(n - 3) (n - 15 n + 48) a(n - 4) - --------------------------- + ------------------------- n - 8 n - 8 2 2 (n - 11 n + 28) a(n - 5) (n - 7) a(n - 7) + --------------------------- + (-n + 6) a(n - 6) - ---------------- n - 8 n - 8 and in Maple input format: a(n) = (n^2-8*n-1)/(n-8)*a(n-1)+4*(n-6)/(n-8)*a(n-2)-(3*n^2-33*n+76)/(n-8)*a(n-\ 3)+(n^2-15*n+48)/(n-8)*a(n-4)+2*(n^2-11*n+28)/(n-8)*a(n-5)+(-n+6)*a(n-6)-(n-7)/ (n-8)*a(n-7) Just for fun, the number of such permutations of length, 1000, is: 2003363189347380095441059218164748868753847578241876252639013607465336441399\ 088480902398950134996547262608677730668664688914491328155389393398582007\ 376912048373427072244520329934246227399443603283223160547133766579846396\ 464305106507481055842147058330406001983660741624052950297320585774152473\ 246607349570586528523876951089149598092316016488912193683196216482402564\ 384296601873886566445074232487376995632939983535610608599169773080117926\ 139410995739718807814999860080616204027043795553108575471753363777205224\ 459062858229278497602695703265525605336617438876071414479525962606160060\ 220004885952100976168380800933445955623698586024993484426216524979834797\ 224397344416191611779413664967143989143238830965180856635881422489265548\ 752467005774122814087582247447658387580454221778924269604684303253449387\ 026754833991959980269693274831177943424983247679655067894366747139271087\ 761207866535001274335356123499573427903095230294173698614457170251782201\ 152199275682052210377676843223638881732381422450866210456292393768765360\ 362883523611032717394642717659666635226757253917090416303156345089816131\ 216745015810273306616765621783521027662225421702414513430052860798607842\ 706303479830402430345613893906045445913409055350803929354755908924444849\ 189354151530163679008845633382131566581256167325554556654010615844173365\ 136896283637212724991208152746445338513142738948361891255691948276331661\ 904947526019699594331421085279765270044834932313468108541849175064302227\ 966180848968391456849733876388074479398981629430935448045069186092666379\ 158687923893030006220625240114553507142912105061818441477113899145264771\ 115193241951031828564798603322508511758538697176229351330700267610253559\ 422417206233819018698859328973529983509439839358314776617782546149004244\ 758093535000562481472769454750266640745952281369215861682328277935239066\ 101075142479804055069733293726668489667930526821808615362384068824787693\ 763342662108940394633966937797455171816759167246752047359146848492569978\ 999097015307908021118381173105919604906459255558897191776139563158733879\ 167742023364444544670829743024973847882451806483006164618586278177396969\ 390862933717267881344191179983475418327523744921888074853023598127609211\ 608867717722625250799207132180871678086233024225949331150616840381356671\ 946443904674392897996965476259610763481505106380097309937020546980232123\ 810033658917468992990688721248354161654072703897303871950694385547310465\ 721398636745342062812319033172194212621712002920342591558670177199956879\ 790509835782313284744186369446103679755750444283454384103521237606095633\ 4171565787362291013216447141953850779768401 you will NEVER be able to compute this number via permanents! The asymptotic to order, 10, is / 5 5 21 53 59 4367 118945 a(n) = n! exp(-3) |1 - ---- - ---- - ---- - ----- + ----- + ------ + ------ | 2 3 4 5 6 7 8 \ 2 n 2 n 8 n 20 n 48 n 112 n 384 n 2311663 1755471197\ + ------- + ----------| 9 10| 1120 n 134400 n / and in Maple input format: a(n) = n!*exp(-3)*(1-5/2/n^2-5/2/n^3-21/8/n^4-53/20/n^5+59/48/n^6+4367/112/n^7+ 118945/384/n^8+2311663/1120/n^9+1755471197/134400/n^10) -------------------------------------------- If pi[i]-i is never in, {0, 1, 3}, we have the following Theorem number, 6 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 1, 3} The first, 30, terms (for the sake of Sloane) are: [0, 0, 1, 2, 8, 42, 288, 2253, 20011, 198134, 2162155, 25773521, 333162807, 4641560373, 69327814782, 1105102025586, 18724508100833, 336044153177536, 6367866406431062, 127051402116491580, 2662259051363248294, 58453140616739510341, 1341971468714262316063, 32153334543865782065588, 802590406853932189323407, 20837487620446093129879529, 561864831084483193060306391, 15712765766879959016828837537, 455144588089900193511983196340, 13639607460640506533471321283404] -------------------------------------------- If pi[i]-i is never in, {0, 2, 3}, we have the following Theorem number, 7 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 2, 3} The first, 30, terms (for the sake of Sloane) are: [0, 1, 1, 2, 10, 50, 328, 2531, 22216, 217822, 2357787, 27913673, 358720299, 4972382065, 73941631358, 1174073012953, 19824660666533, 354695019635120, 6702740707876840, 133399507433906492, 2788956778838172554, 61108714318502818355, 1400291523526756563994, 33492523026679914758628, 834682752278498798146191, 21638680250444684858376841, 582668881564532691138459759, 16273797190205027441989582473, 470835745801281915234342473572, 14094170146013671925762298570361] -------------------------------------------- If pi[i]-i is never in, {0, 1, 2, 3}, we have the following Theorem number, 8 Let a(n) be the number of permutations of length n such that pi[i]-i is NEVER in the set, {0, 1, 2, 3} The first, 30, terms (for the sake of Sloane) are: [0, 0, 0, 0, 1, 9, 71, 631, 5908, 60742, 680306, 8270568, 108565771, 1531308449, 23104905759, 371422720165, 6338437553728, 114453513638652, 2180373683657156, 43704909320353752, 919550120097523565, 20263181601637593289, 466712716540319046439, 11214917137256989930715, 280676029510974671628708, 7304532214657542967752146, 197388953505971674879553510, 5531047356219002893323431408, 160508257020682827152534960119, 4818155857723833428240982809729] -------------------------------------------------------- This ends this screen-turning book, that took, 276.170, secs. to generate.