--------------------------------------------------------------- Let , G[1](n), be the quantity of interest in David Applegate's and Neil Sloane's article "The Gift Exchange Problem , arXiv:0907.0513". It follows from Eq.(8) and Euler's integral representation formula infinity / | k k! = | y exp(-y) dy | / 0 that , G[1](n), can be expressed in terms of the integral infinity / 1 | 2 n ---- | (y + 1/2 y ) exp(-y) dy n! | / 0 It follows from the (discrete) Almkvist-Zeilberger algorithhm that G[1](n), satisfies the linear recurrence of order, 2 G[1](n) = (2 n - 1) G[1](n - 1) + G[1](n - 2) It follows from the Poincare-Birkhoff-Trijinski method that the asymptotics is / 1 3 1 361 12799 377221 \ e (2 n)! |1 - --- - ----- - ------ + ------- + --------- + ----------| | 4 n 2 3 4 5 6| \ 32 n 384 n 6144 n 122880 n 2949120 n / ---------------------------------------------------------------------- n n! 2 --------------------------------------------------------------- Let , G[2](n), be the quantity of interest in David Applegate's and Neil Sloane's article "The Gift Exchange Problem , arXiv:0907.0513". It follows from Eq.(8) and Euler's integral representation formula infinity / | k k! = | y exp(-y) dy | / 0 that , G[2](n), can be expressed in terms of the integral infinity / 1 | 2 3 n ---- | (y + 1/2 y + 1/6 y ) exp(-y) dy n! | / 0 It follows from the (discrete) Almkvist-Zeilberger algorithhm that G[2](n), satisfies the linear recurrence of order, 3 2 n (9 n - 27 n + 17) G[2](n - 1) G[2](n) = 1/2 -------------------------------- n - 2 2 (12 n - 30 n + 13) G[2](n - 2) (n - 1) G[2](n - 3) + 1/2 ------------------------------- + 5/2 ------------------- n - 2 n - 2 It follows from the Poincare-Birkhoff-Trijinski method that the asymptotics is / 1 1 8 929 2023 1198831 \ e (3 n)! |1 + --- + ----- - ----- - ------- - ------- - ----------| | 3 n 2 3 4 5 6| \ 54 n 81 n 5832 n 9720 n 4723920 n / ------------------------------------------------------------------- n n! 6 --------------------------------------------------------------- Let , G[3](n), be the quantity of interest in David Applegate's and Neil Sloane's article "The Gift Exchange Problem , arXiv:0907.0513". It follows from Eq.(8) and Euler's integral representation formula infinity / | k k! = | y exp(-y) dy | / 0 that , G[3](n), can be expressed in terms of the integral infinity / 1 | 2 3 4 n ---- | (y + 1/2 y + 1/6 y + 1/24 y ) exp(-y) dy n! | / 0 It follows from the (discrete) Almkvist-Zeilberger algorithhm that G[3](n), satisfies the linear recurrence of order, 4 G[3](n) = 1/3 3 6 4 2 5 (-58384 n - 10888 n + 2048 n + 2381 + 42304 n + 36972 n - 14592 n ) G[3](n - 1)/(%1) + 1/3 3 2 5 4 (92200 n - 110788 n + 54186 n + 5376 n - 5365 - 35616 n ) G[3](n - 2) ------------------------------------------------------------------------ %1 3 4 2 (5257 - 13776 n - 22810 n + 2688 n + 26308 n ) G[3](n - 3) + 2/3 ------------------------------------------------------------ %1 2 3 (-168 n + 234 n - 81 + 64 n ) G[3](n - 4) + 29/3 ------------------------------------------ %1 2 3 %1 := -547 + 762 n - 360 n + 64 n It follows from the Poincare-Birkhoff-Trijinski method that the asymptotics is / 3 37 153 1619 37519 7432897 \ e (4 n)! |1 + --- + ------ + ------- + -------- - ---------- - -----------| | 8 n 2 3 4 5 6| \ 128 n 1024 n 32768 n 1310720 n 62914560 n / / n / (n! 24 ) / --------------------------------------------------------------- Let , G[4](n), be the quantity of interest in David Applegate's and Neil Sloane's article "The Gift Exchange Problem , arXiv:0907.0513". It follows from Eq.(8) and Euler's integral representation formula infinity / | k k! = | y exp(-y) dy | / 0 that , G[4](n), can be expressed in terms of the integral infinity / 1 | 2 3 4 5 n ---- | (y + 1/2 y + 1/6 y + 1/24 y + 1/120 y ) exp(-y) dy n! | / 0 It follows from the (discrete) Almkvist-Zeilberger algorithhm that G[4](n), satisfies the linear recurrence of order, 5 9 10 7 G[4](n) = 1/24 (-151578125000 n + 10429687500 n - 3360600703125 n 8 3 4 + 940637109375 n - 5745014557625 n + 10210711281250 n - 19116101136 5 6 2 - 11061919934375 n + 7593706062500 n - 233542621190 n + 1827680807975 n 7 ) G[4](n - 1)/(%1) + 5/72 (239559579693 + 2344877312500 n 8 9 2 - 398108125000 n + 28368750000 n + 547555507700 n - 6645071560500 n 3 4 5 + 16902774470200 n - 21502628035125 n + 16301149045625 n 6 2 - 7815795818750 n ) G[4](n - 2)/(%1) + 5/72 (9489183125080 n 4 6 + 16018187528250 n - 1338779968890 n + 3225420081250 n 3 8 7 - 17223070667425 n + 50563125000 n - 521974389203 - 633724500000 n 5 - 9109655690000 n ) G[4](n - 3)/(%1) + 5/72 (160550621036 2 4 5 - 3532864575055 n + 879345818773 n - 3398012350250 n + 1551445167500 n 7 3 6 + 39849750000 n + 4792022496575 n - 399825825000 n ) G[4](n - 4)/(%1) + 3487 6 3 4 5 ---- (16687500 n - 497359875 n + 274594375 n - 109025000 n 72 2 - 164423585 n + 464922400 n - 13947399) G[4](n - 5)/(%1) 6 3 4 5 %1 := 16687500 n - 3019737375 n + 1070031875 n - 209150000 n - 4329975510 n 2 + 1513065336 + 4945130775 n It follows from the Poincare-Birkhoff-Trijinski method that the asymptotics is / 2 8 103 2002 2451 153389 \ e (5 n)! |1 + --- + ----- + ------ + ------- + -------- + ----------| | 5 n 2 3 4 5 6| \ 25 n 375 n 9375 n 15625 n 1406250 n / --------------------------------------------------------------------- n n! 120 --------------------------------------------------------------- Let , G[5](n), be the quantity of interest in David Applegate's and Neil Sloane's article "The Gift Exchange Problem , arXiv:0907.0513". It follows from Eq.(8) and Euler's integral representation formula infinity / | k k! = | y exp(-y) dy | / 0 that , G[5](n), can be expressed in terms of the integral infinity / 1 | 2 3 4 5 6 n ---- | (y + 1/2 y + 1/6 y + 1/24 y + 1/120 y + 1/720 y ) exp(-y) n! | / 0 dy It follows from the (discrete) Almkvist-Zeilberger algorithhm that G[5](n), satisfies the linear recurrence of order, 6 2 G[5](n) = 1/10 (-3927796242314878 n + 601414874178421 n 6 7 9 - 126287253397834362 n + 123447613931897580 n + 47610647981908992 n 8 15 14 - 88878376039543236 n + 514990420992 n - 13518498551040 n 13 12 11 + 161639066630880 n - 1157449348369296 n + 5555276809387344 n 10 3 4 - 18976364678515608 n + 17027867800922722 n - 48445334745124845 n 5 + 93336368449334730 n - 53266368627436) G[5](n - 1)/(%1) + 1/20 ( 10 11 12 71194712815628766 n - 15423916022381700 n + 2223207493615620 n 7 3 4 - 975759237259513956 n - 315288233216151396 n + 738177553638994775 n 5 6 - 1160347867827350322 n + 1258343605471967166 n - 28406377920205085 n 2 13 14 + 97475616975872859 n - 190626923020320 n + 7402987301760 n 9 8 - 232392143935472742 n + 554183381881790667 n + 6208530420097828) 5 4 G[5](n - 2)/(%1) + 1/20 (1585023869107437767 n - 1200513143327711374 n 7 6 8 + 917323232430335862 n - 1428461135949559782 n - 429879940196409468 n 9 12 10 + 146251508723071164 n - 502624292981760 n - 34871433402152160 n 13 2 + 20726774968320 n + 52253767376295647 n - 193272181839672330 n 11 3 + 5462888264779680 n - 13171366757534368 + 594058663446441737 n ) 6 7 G[5](n - 3)/(%1) + 1/20 (532075953684942216 n - 291940871880135096 n 8 10 3 + 116246119142800872 n + 5827830061592520 n - 351666498042606063 n 2 + 125708863909880179 n - 26782168451155776 n + 5449543012707526 4 9 12 + 610961392195439703 n - 32335386402105360 n + 27871472321280 n 11 5 - 606204522987840 n - 692369608128288786 n ) G[5](n - 4)/(%1) + 1/20 ( 6 9 10 -71871162523332120 n + 2633878509671520 n - 330690608294400 n 8 7 11 - 11878029824951520 n + 34573250181794436 n + 18120033331200 n 3 4 5 + 71987063372648007 n - 108624173043783384 n + 107893127691393750 n 2 - 29522930081294745 n - 472185035896918 + 5336504985482459 n) G[5](n - 5) 5771 5 9 /(%1) + ---- (-893376871074 n - 1764366570 - 10927651680 n 20 10 8 7 4 + 794738304 n + 66598003980 n - 225426620052 n + 1008301923489 n 2 6 3 + 358055255840 n - 61871981677 n + 520297655418 n - 756150302388 n ) G[5](n - 6)/(%1) 9 10 8 7 %1 := -18875034720 n + 794738304 n + 200710092780 n - 1246974708852 n 3 4 5 - 36761791077744 n + 27375222246069 n - 14055768211842 n 2 6 + 3900036637332 + 32442413062640 n - 16885378002719 n + 5047845892182 n It follows from the Poincare-Birkhoff-Trijinski method that the asymptotics is e (6 n)! / 5 295 3085 407323 495035 877389625 \ |1 + ---- + ------ + -------- + ---------- + ---------- + -------------| | 12 n 2 3 4 5 6| \ 864 n 10368 n 1492992 n 1990656 n 3869835264 n / / n / (n! 720 ) / --------------------------------------------------------------- Let , G[6](n), be the quantity of interest in David Applegate's and Neil Sloane's article "The Gift Exchange Problem , arXiv:0907.0513". It follows from Eq.(8) and Euler's integral representation formula infinity / | k k! = | y exp(-y) dy | / 0 that , G[6](n), can be expressed in terms of the integral infinity / 1 | ---- | n! | / 0 2 3 4 5 6 7 n (y + 1/2 y + 1/6 y + 1/24 y + 1/120 y + 1/720 y + 1/5040 y ) exp(-y) dy It follows from the (discrete) Almkvist-Zeilberger algorithhm that G[6](n), satisfies the linear recurrence of order, 7 21 G[6](n) = 1/720 (4665136164248580016317904800 n 20 19 - 201933751109617106420617879200 n + 4000076080078240675208490728850 n 18 - 48066064759207293853083506227485 n 17 + 388802265269824387211314152821949 n 16 - 2209692448851817005445605678358749 n 15 + 8881299700342875424887714811748600 n 14 - 24340182662352676107454131996716610 n 13 + 38604562670144904221815366077566192 n 9 - 1118291740638776432579800311596748668 n 8 + 1431646683347100315768082961287897104 n 7 - 1340219864804730554143029337514162630 n 6 + 927022545569685821883026523644556259 n 5 - 470162040992365320608855568078372275 n 4 + 170644180333299433418836044426856891 n 3 - 42173314973323989129275782509412056 n 2 + 6351723073307155280082300494345674 n - 375566254928475592849424223836592 n 12 + 1968061622865176107563813263588466 n 11 - 198547303929257892832698981491888182 n 10 + 610889429231490149166468268100051058 n - 37250405810701530341847448144296) G[6](n - 1)/(%1) + 1/7200 ( 14 774150039551156197753330144265854170 n 13 - 1778064985068363227897074780445252019 n 12 + 1170324557899038017005119432976333354 n 11 + 8194736877376898799569995661866822703 n 20 + 491838641316493150291801963200 n 17 - 4843426555724924105060877851120640 n 16 + 38140055627648220212479481671722621 n 15 - 207844806028204081772253304475886063 n 19 - 21043667582041385501770669711200 n 18 + 410829785025891337490615263979100 n 10 - 36878164831363182789587610238771980949 n 9 + 85801543848062602863620055284558893419 n 8 - 132808723921136480410810905571671648400 n 7 + 145338094687124632182309354534091127223 n 6 - 114693867312319881453883814232021858410 n 5 + 65444148781090020010511033765297559785 n 4 - 26120043261397896741301398054778746296 n 3 + 5740065353103228037649696317546656910 n 2 + 809656916107827709257023139759293532 n - 1072990480715306849886086811881435352 n + 253270295256788949334095598276096512) G[6](n - 2)/(%1) + 7/7200 ( 9 -19190441343792190778849641291337360685 n 8 + 35090822772025736518663230453723184769 n 10 + 6457069893704295139506915941587964131 n 11 - 759788423741356655206171899577122344 n 7 - 43462877817987206345406951680860144514 n 6 + 37797694401855873965095774284565807984 n 2 - 270645735804611485270286512810324600 n + 450604131836779130239312260063248404 n 5 - 23645262215671447540411575491223740998 n 4 + 10546984617534318188590712901467894824 n 3 - 2689975528292681656545419958160630694 n 12 - 445324801539887270020442632340215644 n 14 - 91735712637011185845963569496901407 n 15 + 18430907423092840502595036781760205 n 13 + 293045870635010819380520714052794178 n 16 - 2496436126083252690214086252947925 n 17 + 222768543654214624338600666299850 n 18 - 11901547325847922051583906604000 n 19 + 288272772598392575643900852000 n - 94275477745702614408264859619627704 ) G[6](n - 3)/(%1) + 1/7200 (-2305192195317904352974062232224517412 n 2 + 1022572839503401648768244398300181124 n 3 + 18801786018813773950096375408722882406 n 14 + 190711169190973700754990623065763235 n 15 - 28702177406934197528364640699754700 n 16 + 2787557845977920291532312171124800 n 7 + 205088376225056525126124013920265399302 n 6 - 191915460851027005958761781101184816701 n 8 - 148704479852876637285723882298357150701 n 17 - 160071799729282984640205587808000 n 9 + 68939837155590056939114189771755542718 n 10 - 17273329825791238843414538288934473221 n 18 + 4127081392651863324056865984000 n 11 - 245504838298232678407378255054535544 n 12 + 1975685967893432105465244995175988927 n 13 - 818119880358451108941615293871048366 n 4 - 64123129873954436352310509469825226017 n 5 + 129118702605950010412387826537505084464 n + 219578431090395860864986539131957796) G[6](n - 4)/(%1) + 1/7200 ( 615835040189245473213164325203385136 n 2 - 184505466052074912646348500697970816 n 4 + 21163256532894226292823386795742239299 n 3 - 7081475308033712709235442922211403686 n 5 - 38293961551615732066000479144741784479 n 6 + 53878643967088246825483341634294919560 n 7 - 54489986494051626495593759242085580251 n 8 + 35691242915562103531909321474992125450 n 9 - 13832460027831964268731722534368486912 n 10 + 2268580043536524475488129770504983311 n 11 + 545724714401148171772584402506511111 n 12 - 434377906359582905646950284529149854 n 13 + 128311974784578780575329398199382205 n 14 - 22570452115880591892216622445368200 n 15 + 2482660684892177318243964684040200 n 16 - 158764490179149037645949956560000 n 17 + 4499398507101389730856881360000 n + 89615486993870445134564468919281156) G[6](n - 5)/(%1) + 1/7200 ( 8 -3481341193564453729784153400737670734 n 6 - 6076344758485619696050800750989366160 n 9 + 1094172489499856538629164889769025692 n 11 - 79289278984731625065299145363060366 n 15 - 77207705922525571951571388564000 n 12 + 35859805223534700570798265329585480 n 13 - 7915966646822385809201301897890100 n 10 - 74620253837002322483999232674024745 n 16 + 2507906920917303961303943016000 n 14 + 1036485949039982761267068848313300 n 5 + 4478544561302837412374471987258276612 n 3 + 1049198408658167182733738984485931744 n 2 + 8126426043160596029061753375226240 n 4 - 2752404179841166513573746924800078983 n 7 + 5895942643907493377151130452088424434 n - 66221703437831083859873593481455688 n 14202031 - 35737641225810954385127227554543196) G[6](n - 6)/(%1) + -------- ( 7200 3 173842370881072042342606392 n - 3558638898185510001550800812 n 5 9 - 12035214751064090368015499994 n - 1918972258949063488267347670 n 2 4 + 20179977602426689217421124 n + 8212210590539406583015819957 n 7 6 - 15087896128180997171065916670 n + 16054187749515229786746707545 n 10 - 101849019788629811486943567 n + 183871910693354408394396900 14 8 - 1002654507502338873487200 n + 7960500089640406742059967754 n 12 15 - 65458211103643938697753965 n + 39653003121561424375200 n 13 11 + 10882384859381027681452050 n + 208390402999366040273262876 n ) G[6](n - 7)/(%1) 5 14 %1 := -922867425614456250200196739752 n - 1597449554325760239115200 n 10 15 - 10949482585789020295199295993 n + 39653003121561424375200 n 12 13 - 316212890878620584134681815 n + 29083113292177721469668850 n 6 11 + 305725478321997779333662508785 n + 2261807545266596158021059156 n 8 9 - 63409954336645663709888212896 n + 34948479325804565501094884630 n 2 4 + 1008647995359827190988814548234 n + 1504905345649898666970790403977 n 7 + 64470207657227768477553997176 + 7349170154574951713095142778 n 3 - 382210114712934712414011250776 n - 1548398947279940871053862895454 n It follows from the Poincare-Birkhoff-Trijinski method that the asymptotics is / 3 5 108 5559 186491 53849101 \ e (7 n)! |1 + --- + ----- + ------ + -------- + --------- + ------------| | 7 n 2 3 4 5 6| \ 14 n 343 n 19208 n 672280 n 197650320 n / ------------------------------------------------------------------------- n n! 5040 This took, 86.597, seconds