On the Enumeration of Generalized Menages Numbers for sets containg 0 and largest element, 1



                              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, 6, 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, 6, is

                            /     1      1      3      67      245  \
          a(n) = n! exp(-2) |1 - ---- - ---- + ---- + ----- + ------|
                            |       2      3      4       5        6|
                            \    2 n    6 n    8 n    60 n    144 n /

                           and in Maple input format:

a(n) = n!*exp(-2)*(1-1/2/n^2-1/6/n^3+3/8/n^4+67/60/n^5+245/144/n^6)
            --------------------------------------------------------

          This ends this screen-turning book, that took, 0.588, secs.

                                  to generate.