Everything you Ever Wanted To Know About the Sequences Enumerating, [1, 2, 3], -Avoiding Words With r 1's, r 2's, ..., r n's, for r=1 to r=, 6 By Shalosh B. Ekhad In this article, dedicated to Neil Sloane (b. Oct. 10, 1939) on the occasion \ of his turning 75-years-old We will find the first, 20, terms of the enumerating sequences described in t\ he title, and, space permitting discover linear recurrence equations with polynomial coefficients and asympt\ otic expressions for them. ------------------------------------------------------------------------- Theorem number, 1 Let , A[1](n), be the number of words,w, of length, n, with exactly, 1, occurrences of the letter i, for i from 1 to n such that you can't find an increasing subsequence of length, 3 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form -2*(1+2*n)/(2+n)+N More versbosely, we have , for n>=1 2 (1 + 2 n) A[1](n) - ------------------- + A[1](1 + n) = 0 2 + n subject to the initial conditions A[1](1) = 1 In Maple input format: -2*(1+2*n)/(2+n)*A[1](n)+A[1](1+n) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 2046105521468021692642519982997827217179245642339057975844538099572176010191891\ 8639649680261564537524490157505694285950973181636343701546373806668828863752033\ 5965324339092971743108044350900750477291297314225320935212694683984479674769763\ 8537600100637918819326569730982083021538057087711176285777909275869648636874856\ 8059565800576731736556668870034939446501641533969109270374063017990525846636110\ 1689727289330553211629214327103714071875162583981207268246434315379295628174858\ 2435751481498598087586998603921577523657477775758899987954012641033870640665444\ 651660246024318184109046864244732001962029120 the asymptotics of, A[1](n), to order, 10, is n 3/2 / 9 145 1155 36939 295911 4735445 4 (1/n) |1 - --- + ------ - ------- + -------- - --------- + ---------- | 8 n 2 3 4 5 6 \ 128 n 1024 n 32768 n 262144 n 4194304 n 37844235 2421696563 19402289907 310496335695 \ / - ----------- + ------------- - -------------- + ----------------| / 7 8 9 10| / 33554432 n 2147483648 n 17179869184 n 274877906944 n / 1/2 Pi and in Maple input format 1/Pi^(1/2)*4^n*(1/n)^(3/2)*(1-9/8/n+145/128/n^2-1155/1024/n^3+36939/32768/n^4-\ 295911/262144/n^5+4735445/4194304/n^6-37844235/33554432/n^7+2421696563/ 2147483648/n^8-19402289907/17179869184/n^9+310496335695/274877906944/n^10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 0.99999999999999999998 Not bad! ------------------------------------------------------------------------- Theorem number, 2 Let , A[2](n), be the number of words,w, of length, 2 n, with exactly, 2, occurrences of the letter i, for i from 1 to n such that you can't find an increasing subsequence of length, 3 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 6, 43, 352, 3114, 29004, 280221, 2782476, 28221784, 291138856, 3045298326, 32222872906, 344293297768, 3709496350512, 40256666304723, 439645950112788, 4828214610825948, 53286643424088024, 590705976259292856, 6574347641664629388] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form -3*(7*n+12)*(1+2*n)*(n+1)/(2*n+5)/(7*n+5)/(2+n)-1/2*(528+1426*n+1215*n^2+329*n^ 3)/(2*n+5)/(7*n+5)/(2+n)*N+N^2 More versbosely, we have , for n>=1 3 (7 n + 12) (1 + 2 n) (n + 1) A[2](n) - -------------------------------------- (2 n + 5) (7 n + 5) (2 + n) 2 3 (528 + 1426 n + 1215 n + 329 n ) A[2](n + 1) - 1/2 --------------------------------------------- + A[2](2 + n) = 0 (2 n + 5) (7 n + 5) (2 + n) subject to the initial conditions A[2](1) = 1, A[2](2) = 6 In Maple input format: -3*(7*n+12)*(1+2*n)*(n+1)/(2*n+5)/(7*n+5)/(2+n)*A[2](n)-1/2*(528+1426*n+1215*n^ 2+329*n^3)/(2*n+5)/(7*n+5)/(2+n)*A[2](n+1)+A[2](2+n) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 7593292178303937816728707609005946647161387588845274690037158838707786359743044\ 7177063903357683809020622645569077809447613630071717860169753006538076594097911\ 6449649663845292417890514498169434155891303506029978474229706193197142445784355\ 7757891920617817019606240089635383343807973904796865989763712497079030149944140\ 0190106054807028676976232278444601268806545873001139422356155041251677905408231\ 0161961984203594782322866051469424736074531828620364999575605087637074413359223\ 5157925345436967595919379507226242221927191329554350768160441177225519485789363\ 7445372630446831796201611624095188175015347404572835611837121937268895931965899\ 4583868742530801201412409606953182855856074434940236704800846830693295661785237\ 3524181602941386412189160857694969557657005809854087923073329654300668751515464\ 6295533359421150422232691749581601158349757050019014608078466177917132484082461\ 1552626198262050573307970487425689073324264845414850506226680159765044693128127\ 1443016750250010726630469084361959403774424958401426816024967042779427538065380\ 81085581790684652924446696583829800892890399436 the asymptotics of, A[2](n), to order, 10, is 1/2 1/2 n 3/2 / 249 13255 2674485 2123737437 3 3 7 12 (1/n) |1 - ----- + -------- - ----------- + -------------- | 392 n 2 3 4 \ 43904 n 17210368 n 26985857024 n 51537243879 30228540821765 10891726901443245 - ---------------- + ------------------- - ---------------------- 5 6 7 1511207993344 n 1184787066781696 n 3251055711248973824 n 62615364801481212149 9811579736414126422323 + -------------------------- - --------------------------- 8 9 10195310710476781912064 n 570937399786699787075584 n 22489456378734622818005985 \ / 1/2 - -------------------------------| / (49 Pi ) 10| / 447614921432772633067257856 n / and in Maple input format 3/49*3^(1/2)*7^(1/2)/Pi^(1/2)*12^n*(1/n)^(3/2)*(1-249/392/n+13255/43904/n^2-\ 2674485/17210368/n^3+2123737437/26985857024/n^4-51537243879/1511207993344/n^5+ 30228540821765/1184787066781696/n^6-10891726901443245/3251055711248973824/n^7+ 62615364801481212149/10195310710476781912064/n^8-9811579736414126422323/ 570937399786699787075584/n^9-22489456378734622818005985/ 447614921432772633067257856/n^10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 0.99999999999999999997 Not bad! ------------------------------------------------------------------------- Theorem number, 3 Let , A[3](n), be the number of words,w, of length, 3 n, with exactly, 3, occurrences of the letter i, for i from 1 to n such that you can't find an increasing subsequence of length, 3 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 20, 374, 8124, 190893, 4727788, 121543500, 3212914524, 86782926068, 2384725558736, 66456350375566, 1873703883228900, 53351152389518550, 1531960347453263112, 44311785923563130392, 1289909841595078198172, 37760636720455988917420, 1110927659386926734186992, 32829851946481173252840184, 974077753606734750485658224] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form -64/3*(4*n+1)*(2*n+3)*(4*n+3)*(14*n+25)*(n+1)/(3*n+5)/(1+2*n)/(3*n+7)/(14*n+11) /(2+n)-8/3*(3975+20322*n+39676*n^2+37144*n^3+16736*n^4+2912*n^5)/(3*n+5)/(1+2*n )/(3*n+7)/(14*n+11)/(2+n)*N+N^2 More versbosely, we have , for n>=1 (4 n + 1) (2 n + 3) (4 n + 3) (14 n + 25) (n + 1) A[3](n) -64/3 --------------------------------------------------------- - (3 n + 5) (1 + 2 n) (3 n + 7) (14 n + 11) (2 + n) 2 3 4 5 (3975 + 20322 n + 39676 n + 37144 n + 16736 n + 2912 n ) A[3](n + 1) 8/3 ----------------------------------------------------------------------- (3 n + 5) (1 + 2 n) (3 n + 7) (14 n + 11) (2 + n) + A[3](2 + n) = 0 subject to the initial conditions A[3](1) = 1, A[3](2) = 20 In Maple input format: -64/3*(4*n+1)*(2*n+3)*(4*n+3)*(14*n+25)*(n+1)/(3*n+5)/(1+2*n)/(3*n+7)/(14*n+11) /(2+n)*A[3](n)-8/3*(3975+20322*n+39676*n^2+37144*n^3+16736*n^4+2912*n^5)/(3*n+5 )/(1+2*n)/(3*n+7)/(14*n+11)/(2+n)*A[3](n+1)+A[3](2+n) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 3148396814492324185490267589988506000043618800104357526673885470352254406512175\ 6084571062922517677846098854261705840633135121837935196265184520313634514324988\ 2704520845926411168890941665247349723254836348286917613920913945895139015298791\ 3723083504516889544574141346575156476530518847794491749903265554453759958273057\ 6069485176275605262753854648553303144676148240268928014716554260966093624930764\ 9268080353516914143376592488537072887937279449169596124243542152775656705928406\ 3571856375624827549886182170955771302252514345144517768731354522034458524485018\ 9403990006631126845598460306192487092744550296561823241403152407142252893100454\ 1906553875490237941573968114376793500244747515572082919440147946980295921423857\ 1988506261197744124072088205939903035918805543294549479381426079037078190065374\ 8592375034694025538195487756365498833991330767963888042002671766041106015678607\ 8327116122718969553595755856507545978092867587737893874927429902588915777564590\ 5183071441268840958998734764753427775831584595060060358867697919835906736127988\ 1498421015285880619690416908127956356333603791666817025100307690746609517321583\ 3570149233286605739848293009889626097352864209235615683397609850179660083390317\ 6914886580548256294359060923242722735413462579066453275758728487844780809176991\ 6900334331672463843722499934969070075405547622534890261964174703900398495561642\ 0508494602006124807324806757323769200121914252657224448406906638002655718701981\ 295348764091550829144266335486122472975291558313991247932041204166605392900480 the asymptotics of, A[3](n), to order, 10, is n 3/2 / 33 1105 27195 3706059 106431633 32 (1/n) |1 - ---- + ------- - --------- + ------------ + ------------- | 64 n 2 3 4 5 \ 8192 n 524288 n 134217728 n 8589934592 n 23307054485 402781435485 1298292658762957 + ---------------- + ----------------- - -------------------- 6 7 8 1099511627776 n 70368744177664 n 36028797018963968 n 291534682060320699 72376629713086669425 \ / 1/2 - ---------------------- - -------------------------| / (8 Pi ) 9 10| / 2305843009213693952 n 295147905179352825856 n / and in Maple input format 1/8/Pi^(1/2)*32^n*(1/n)^(3/2)*(1-33/64/n+1105/8192/n^2-27195/524288/n^3+3706059 /134217728/n^4+106431633/8589934592/n^5+23307054485/1099511627776/n^6+ 402781435485/70368744177664/n^7-1298292658762957/36028797018963968/n^8-\ 291534682060320699/2305843009213693952/n^9-72376629713086669425/ 295147905179352825856/n^10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 0.99999999999999999998 Not bad! ------------------------------------------------------------------------- Theorem number, 4 Let , A[4](n), be the number of words,w, of length, 4 n, with exactly, 4, occurrences of the letter i, for i from 1 to n such that you can't find an increasing subsequence of length, 3 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 70, 3199, 173860, 10203181, 631326526, 40553993125, 2678871322640, 180830423671450, 12418980645870820, 864996624914197495, 60957211831578399100, 4338372535640598835279, 311386494956413595138930, 22513820432313175983170649, 1638226907374445245497453464, 119879437233268054455643664540, 8816310717018695747221495985704, 651283473782492244839579091820690, 48305712720059582761530066305796370] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form 125*(4*n+1)*(4*n+3)*(2+n)*(n+1)*(833881955628195101*n^2+4334440398787864643*n+ 5570920248415028320)/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/(117658749964922315*n^2+ 573464473150578931*n+754134476884609344)-25/2*(2+n)*(6797590926192864096514*n^5 +52313495069544026232773*n^4+146976870497476539918782*n^3+ 185798998559603713597083*n^2+105551389385700444982568*n+21400378032198247784160 )/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/(117658749964922315*n^2+573464473150578931*n+ 754134476884609344)*N-5/4*(899390725561332510596160+2237132112030660367540892*n +2665788097113018431658294*n^2+1890016298687795509670590*n^3+ 797828129908309346140155*n^4+182271724749385461273198*n^5+ 17187566185694281417071*n^6)/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/( 117658749964922315*n^2+573464473150578931*n+754134476884609344)*N^2-1/8*( 3981439903977825736232960*n+3006331443897965320930044*n^2+ 1149414158136510413874416*n^3+223085148216213565033949*n^4+ 18124931746162005181496*n^5+155019126659173713655*n^6+2142982572383955409843200 )/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/(117658749964922315*n^2+573464473150578931*n+ 754134476884609344)*N^3+N^4 More versbosely, we have , for n>=1 125 (4 n + 1) (4 n + 3) (2 + n) (n + 1) 2 (833881955628195101 n + 4334440398787864643 n + 5570920248415028320) A[4](n)/((2 n + 7) (4 n + 17) (n + 4) (4 n + 15) %1) - 25/2 (2 + n) ( 5 4 6797590926192864096514 n + 52313495069544026232773 n 3 2 + 146976870497476539918782 n + 185798998559603713597083 n + 105551389385700444982568 n + 21400378032198247784160) A[4](n + 1)/( (2 n + 7) (4 n + 17) (n + 4) (4 n + 15) %1) - 5/4 (899390725561332510596160 2 + 2237132112030660367540892 n + 2665788097113018431658294 n 3 4 + 1890016298687795509670590 n + 797828129908309346140155 n 5 6 + 182271724749385461273198 n + 17187566185694281417071 n ) A[4](2 + n)/( (2 n + 7) (4 n + 17) (n + 4) (4 n + 15) %1) - 1/8 ( 2 3981439903977825736232960 n + 3006331443897965320930044 n 3 4 + 1149414158136510413874416 n + 223085148216213565033949 n 5 6 + 18124931746162005181496 n + 155019126659173713655 n + 2142982572383955409843200) A[4](n + 3)/((2 n + 7) (4 n + 17) (n + 4) (4 n + 15) %1) + A[4](n + 4) = 0 2 %1 := 117658749964922315 n + 573464473150578931 n + 754134476884609344 subject to the initial conditions A[4](1) = 1, A[4](2) = 70, A[4](3) = 3199, A[4](4) = 173860 In Maple input format: 125*(4*n+1)*(4*n+3)*(2+n)*(n+1)*(833881955628195101*n^2+4334440398787864643*n+ 5570920248415028320)/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/(117658749964922315*n^2+ 573464473150578931*n+754134476884609344)*A[4](n)-25/2*(2+n)*( 6797590926192864096514*n^5+52313495069544026232773*n^4+146976870497476539918782 *n^3+185798998559603713597083*n^2+105551389385700444982568*n+ 21400378032198247784160)/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/(117658749964922315*n^ 2+573464473150578931*n+754134476884609344)*A[4](n+1)-5/4*( 899390725561332510596160+2237132112030660367540892*n+2665788097113018431658294* n^2+1890016298687795509670590*n^3+797828129908309346140155*n^4+ 182271724749385461273198*n^5+17187566185694281417071*n^6)/(2*n+7)/(4*n+17)/(n+4 )/(4*n+15)/(117658749964922315*n^2+573464473150578931*n+754134476884609344)*A[4 ](2+n)-1/8*(3981439903977825736232960*n+3006331443897965320930044*n^2+ 1149414158136510413874416*n^3+223085148216213565033949*n^4+ 18124931746162005181496*n^5+155019126659173713655*n^6+2142982572383955409843200 )/(2*n+7)/(4*n+17)/(n+4)/(4*n+15)/(117658749964922315*n^2+573464473150578931*n+ 754134476884609344)*A[4](n+3)+A[4](n+4) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 1492715564681093362354625290815937249763830246110807525436034559988662184209311\ 2724134781383392540979020110037048475561492282289352605671972825849606397095071\ 2510756123178219023165167231272387109718166181126882965169058569618011276401527\ 3355018579340280512357113491805038633401811319740046042136735752942821699391672\ 5218771638029994988344287689844804826680987745649682108480000033477013573658602\ 6684275495821310862880948865199147931688350751816785445845184696137805342695922\ 2465447196188163861409258843727430793373625114068782224030593468025972177923017\ 3060659247379453777466314265610980326814115901837516912031817354291587840415849\ 7956428214418920949461695696881625850681035094715093794335833747546538932002172\ 4689605420979057471910664961847592806900332457345296131628889374189794565852452\ 0432819130936762527667987670589306377274990700867410579279885679907388102118773\ 3387185910250049036303014721067952218894922021105802667045568995001620795006733\ 2589554365619907838205340729244573545020826021646479560956274418680878858458910\ 8949946938726726227437057728946283036231271097728377769031144162279459674967625\ 6140740215176274976609172644410305040397787259398193257026528345414884779014909\ 1248502021691086122513331095183468877828807660053514470313934318931222428132456\ 6414978014885131028992295353042789271728967436624551651436013812310012285416514\ 0049750584187427324814008637755088233703993241229349426708087475971096064311936\ 2205693466903338952531107498735147475738777263829816152691112057469203664554422\ 3709456536970650147708036644426744693659162130326454814078950750907478856942341\ 6689260511711110775015133918424338563519330003529085563991951970257337852237630\ 6627191560030701782443973543171028995057554840229335800841780507025571141653192\ 0552900313466084890051516558476308951920894554172602205802252240881885245436679\ 1133129628030383652073227858849788936171465431659469052313555337149966325349728\ 90 the asymptotics of, A[4](n), to order, 10, is 1/2 1/2 n 3/2 / 23 1621 339199 90153721 2 3 80 (1/n) |1 - ---- + -------- - ----------- + ------------- | 48 n 2 3 4 \ 23040 n 16588800 n 3185049600 n 115691883461 85715303805703 241601559266639 + ---------------- + ------------------- - -------------------- 5 6 7 3822059520000 n 3302259425280000 n 17612050268160000 n 3738435978767080019 11599209716905911829729 - ----------------------- - -------------------------- 8 9 33815136514867200000 n 43824416923267891200000 n 33059950112526556216235693 \ / 1/2 - -------------------------------| / (36 Pi ) 10| / 105178600615842938880000000 n / and in Maple input format 1/36*2^(1/2)*3^(1/2)/Pi^(1/2)*80^n*(1/n)^(3/2)*(1-23/48/n+1621/23040/n^2-339199 /16588800/n^3+90153721/3185049600/n^4+115691883461/3822059520000/n^5+ 85715303805703/3302259425280000/n^6-241601559266639/17612050268160000/n^7-\ 3738435978767080019/33815136514867200000/n^8-11599209716905911829729/ 43824416923267891200000/n^9-33059950112526556216235693/ 105178600615842938880000000/n^10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 0.99999999999999999998 Not bad! ------------------------------------------------------------------------- Theorem number, 5 Let , A[5](n), be the number of words,w, of length, 5 n, with exactly, 5, occurrences of the letter i, for i from 1 to n such that you can't find an increasing subsequence of length, 3 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 252, 26945, 3526452, 496632627, 73755038148, 11370526112831, 1802608455113988, 292025514204152288, 48132038318610945704, 8045664273096259377006, 1360731282747421987390812, 232420615523852127542961849, 40035835234057533413467195836, 6947049574459144345767787409913, 1213187850694192250327775433235876, 213060112278129023804263616188583292, 37605243443507557948999352634024956784, 6667087906942820489159477434013368910307, 1186778630445927739902666146716602793786296] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form 62208/5*(6*n+5)*(1+2*n)*(6*n+1)*(2+n)*(n+1)*( 35977691436282616399086887407277643058634025605978329*n^3+ 285882535463552943501778893605943560545220539172834079*n^2+ 755218087425054140665508730353269605836994287699299859*n+ 663122757025440444830512129264481540684096097544780704)/(5*n+17)/(5*n+18)/(5*n+ 19)/(n+4)/(5*n+21)/(656486228393872890174481440882766370514517335421243*n^3+ 4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)-32/5*(2+n)*( 20682684343672990248675921454525852394126840880865728920473*n^7+ 226076397769416093823469437214429668818022608615134944119039*n^6+ 989141990028801923402652198518478623543762416699711640062534*n^5+ 2215331772907630412598027898571234055990101587943071535282136*n^4+ 2699753141594777779063196188413842514302630943219781222823683*n^3+ 1750137631280573754613484109135599575411604050492497705294477*n^2+ 522989525986658558341401546479984526706622250418715407572342*n+ 40000155312544514937662720961472986570958636653479478948180)/(5*n+17)/(5*n+18)/ (5*n+19)/(n+4)/(5*n+21)/(656486228393872890174481440882766370514517335421243*n^ 3+4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*N-4/15*( 13546723537496159728679589343564800515837105581551686677389120+ 43026467762530033758757910360252017155096355626744649145629200*n+ 62093386273070321879112434836477898901595368415230194969611200*n^2+ 54979652352359707014806136905612866479429876459833833415847602*n^3+ 33272510943721755943228273765790569323089611199046955439849581*n^4+ 13967170527470476918668627867572792035442076635439088562672390*n^5+ 3859884503061997345293540231301004197399264431781078596638680*n^6+ 622932367305579826963523831325425375893894893380744023095368*n^7+ 43989103350760216022917286270729410533054122441680010268619*n^8)/(5*n+17)/(5*n+ 18)/(5*n+19)/(n+4)/(5*n+21)/( 656486228393872890174481440882766370514517335421243*n^3+ 4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*N^2-4/15*( 1281262653546018385206479186451143604169100362060407138693120+ 3740002353099313876646241205051099454225669464204109779223832*n+ 4646506441120530834658707963309109108492410521664152698766862*n^2+ 3200989570122994869943753872807218886042821668518908202724581*n^3+ 1326770011771513987079582576031790639924795105682821537064314*n^4+ 333260310210039489422524375967301246303349396525422229415308*n^5+ 47834413146485695738972605784085185027192044502840653887268*n^6+ 3272664364499983113393427994769622222057126079121041718719*n^7+ 52860675555434422710899931418441981798739782573908924956*n^8)/(5*n+17)/(5*n+18) /(5*n+19)/(n+4)/(5*n+21)/(656486228393872890174481440882766370514517335421243*n ^3+4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*N^3+N^4 More versbosely, we have , for n>=1 62208/5 (6 n + 5) (1 + 2 n) (6 n + 1) (2 + n) (n + 1) ( 3 35977691436282616399086887407277643058634025605978329 n 2 + 285882535463552943501778893605943560545220539172834079 n + 755218087425054140665508730353269605836994287699299859 n + 663122757025440444830512129264481540684096097544780704) A[5](n)/( (5 n + 17) (5 n + 18) (5 n + 19) (n + 4) (5 n + 21) %1) - 32/5 (2 + n) ( 7 20682684343672990248675921454525852394126840880865728920473 n 6 + 226076397769416093823469437214429668818022608615134944119039 n 5 + 989141990028801923402652198518478623543762416699711640062534 n 4 + 2215331772907630412598027898571234055990101587943071535282136 n 3 + 2699753141594777779063196188413842514302630943219781222823683 n 2 + 1750137631280573754613484109135599575411604050492497705294477 n + 522989525986658558341401546479984526706622250418715407572342 n + 40000155312544514937662720961472986570958636653479478948180) A[5](n + 1) /((5 n + 17) (5 n + 18) (5 n + 19) (n + 4) (5 n + 21) %1) - 4/15 ( 13546723537496159728679589343564800515837105581551686677389120 + 43026467762530033758757910360252017155096355626744649145629200 n 2 + 62093386273070321879112434836477898901595368415230194969611200 n 3 + 54979652352359707014806136905612866479429876459833833415847602 n 4 + 33272510943721755943228273765790569323089611199046955439849581 n 5 + 13967170527470476918668627867572792035442076635439088562672390 n 6 + 3859884503061997345293540231301004197399264431781078596638680 n 7 + 622932367305579826963523831325425375893894893380744023095368 n 8 + 43989103350760216022917286270729410533054122441680010268619 n ) A[5](2 + n)/((5 n + 17) (5 n + 18) (5 n + 19) (n + 4) (5 n + 21) %1) - 4/15 (1281262653546018385206479186451143604169100362060407138693120 + 3740002353099313876646241205051099454225669464204109779223832 n 2 + 4646506441120530834658707963309109108492410521664152698766862 n 3 + 3200989570122994869943753872807218886042821668518908202724581 n 4 + 1326770011771513987079582576031790639924795105682821537064314 n 5 + 333260310210039489422524375967301246303349396525422229415308 n 6 + 47834413146485695738972605784085185027192044502840653887268 n 7 + 3272664364499983113393427994769622222057126079121041718719 n 8 + 52860675555434422710899931418441981798739782573908924956 n ) A[5](n + 3) /((5 n + 17) (5 n + 18) (5 n + 19) (n + 4) (5 n + 21) %1) + A[5](n + 4) = 0 3 %1 := 656486228393872890174481440882766370514517335421243 n 2 + 4233692976503708702734111422895970338832268857096474 n + 8840701043349298040442216716805990644287291130165063 n + 5874384960324293748126718637456945145115359526097272 subject to the initial conditions A[5](1) = 1, A[5](2) = 252, A[5](3) = 26945, A[5](4) = 3526452 In Maple input format: 62208/5*(6*n+5)*(1+2*n)*(6*n+1)*(2+n)*(n+1)*( 35977691436282616399086887407277643058634025605978329*n^3+ 285882535463552943501778893605943560545220539172834079*n^2+ 755218087425054140665508730353269605836994287699299859*n+ 663122757025440444830512129264481540684096097544780704)/(5*n+17)/(5*n+18)/(5*n+ 19)/(n+4)/(5*n+21)/(656486228393872890174481440882766370514517335421243*n^3+ 4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*A[5](n)-32/5*(2+n)*( 20682684343672990248675921454525852394126840880865728920473*n^7+ 226076397769416093823469437214429668818022608615134944119039*n^6+ 989141990028801923402652198518478623543762416699711640062534*n^5+ 2215331772907630412598027898571234055990101587943071535282136*n^4+ 2699753141594777779063196188413842514302630943219781222823683*n^3+ 1750137631280573754613484109135599575411604050492497705294477*n^2+ 522989525986658558341401546479984526706622250418715407572342*n+ 40000155312544514937662720961472986570958636653479478948180)/(5*n+17)/(5*n+18)/ (5*n+19)/(n+4)/(5*n+21)/(656486228393872890174481440882766370514517335421243*n^ 3+4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*A[5](n+1)-4/15*( 13546723537496159728679589343564800515837105581551686677389120+ 43026467762530033758757910360252017155096355626744649145629200*n+ 62093386273070321879112434836477898901595368415230194969611200*n^2+ 54979652352359707014806136905612866479429876459833833415847602*n^3+ 33272510943721755943228273765790569323089611199046955439849581*n^4+ 13967170527470476918668627867572792035442076635439088562672390*n^5+ 3859884503061997345293540231301004197399264431781078596638680*n^6+ 622932367305579826963523831325425375893894893380744023095368*n^7+ 43989103350760216022917286270729410533054122441680010268619*n^8)/(5*n+17)/(5*n+ 18)/(5*n+19)/(n+4)/(5*n+21)/( 656486228393872890174481440882766370514517335421243*n^3+ 4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*A[5](2+n)-4/15*( 1281262653546018385206479186451143604169100362060407138693120+ 3740002353099313876646241205051099454225669464204109779223832*n+ 4646506441120530834658707963309109108492410521664152698766862*n^2+ 3200989570122994869943753872807218886042821668518908202724581*n^3+ 1326770011771513987079582576031790639924795105682821537064314*n^4+ 333260310210039489422524375967301246303349396525422229415308*n^5+ 47834413146485695738972605784085185027192044502840653887268*n^6+ 3272664364499983113393427994769622222057126079121041718719*n^7+ 52860675555434422710899931418441981798739782573908924956*n^8)/(5*n+17)/(5*n+18) /(5*n+19)/(n+4)/(5*n+21)/(656486228393872890174481440882766370514517335421243*n ^3+4233692976503708702734111422895970338832268857096474*n^2+ 8840701043349298040442216716805990644287291130165063*n+ 5874384960324293748126718637456945145115359526097272)*A[5](n+3)+A[5](n+4) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 1483272866638701923151738439852443066155558520312446850795108676973371060613332\ 2562635619143794191725373540429731931292182612362554854562449578156077661669074\ 8533151899895683543875423242586067357896053033712191410263670877038296875727649\ 9363947710432581950499478262843952974397010318061319916356972436289203691691671\ 4354477460328426491341208508345194438620807891010224093386321541333356859916706\ 3809262623947977615726179206964433145245366698011761737304934573557734682787311\ 6090094460847937277025705900471197856066120621090971396345647894667449986290776\ 6836582519783858482358758895049306496039968208022639908745806012712821199052545\ 0953978067484753048200864197679177566145538638739352893698193913549478199425779\ 8196042545316708068226839807773653361704268082339111067391878758574625502895128\ 1091359234326784947956023706554154307677576030703999978099265575111100937917005\ 6253984156719695083006340838372734539908314560970167128684579800074824604200914\ 1559008104265909048243660872456342811590027383023942733178530093251422641873828\ 2703054808162519936115839223026270464833749012748736662011372070710853706097661\ 4489147823807338581069917659820917915411245255153894865320187847745170057582994\ 1404748194380418345070460846736893263293217819850449478826927344838189783014151\ 5547270670390755305220379699342420005790455694307552352397241000789339246712030\ 5019650614469992248658478380193172918470496925962216066677300416148592731252004\ 8502595150712674805671015972074452763761123812508912478242860942155595747847715\ 8554394666813424544977728800966895912444702073127351386866887235314596755562688\ 0763976000523937721317577718693679201039017946184062337158907721123022047703273\ 2029412954816785341084391047341422416664010548599831001150494231543918833454741\ 1552852569471262986447143665240035639065239741687895871736975284001840251817248\ 2550569486956737506715780928330841620950455390698023141105124242771094073710368\ 0815910014908672840425329901406927176741694555886054682496959435297162933785679\ 3116733572745309994597543716777209159255865278769362313248488581108622367404987\ 0745220774037800557678556113275492010744758469966114783652305581265957945893914\ 0849364154283974547924489651235127316318679304263569964632200242984965991520147\ 877187003093031684558354103573198621903976221740926839882907991080 the asymptotics of, A[5](n), to order, 10, is 1/2 n 3/2 / 471 389141 162387477 3 3 192 (1/n) |1 - ------ + ----------- - -------------- | 1000 n 2 3 \ 10000000 n 50000000000 n 7335332569299 207687570285951063 46925230488922877377 + ------------------ + ---------------------- + ------------------------- 4 5 6 200000000000000 n 5000000000000000000 n 2000000000000000000000 n 473287385487519792168837 77245429101665520357608716913 - ----------------------------- - --------------------------------- 7 8 10000000000000000000000000 n 400000000000000000000000000000 n 143011717148259996658844142089169 - ------------------------------------ 9 400000000000000000000000000000000 n 3002390876448566050836318179074114653 \ / 1/2 - ------------------------------------------| / (125 Pi ) 10| / 20000000000000000000000000000000000000 n / and in Maple input format 3/125*3^(1/2)/Pi^(1/2)*192^n*(1/n)^(3/2)*(1-471/1000/n+389141/10000000/n^2-\ 162387477/50000000000/n^3+7335332569299/200000000000000/n^4+207687570285951063/ 5000000000000000000/n^5+46925230488922877377/2000000000000000000000/n^6-\ 473287385487519792168837/10000000000000000000000000/n^7-\ 77245429101665520357608716913/400000000000000000000000000000/n^8-\ 143011717148259996658844142089169/400000000000000000000000000000000/n^9-\ 3002390876448566050836318179074114653/20000000000000000000000000000000000000/n^ 10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 1.0000000000000000000 Not bad! ------------------------------------------------------------------------- Theorem number, 6 Let , A[6](n), be the number of words,w, of length, 6 n, with exactly, 6, occurrences of the letter i, for i from 1 to n such that you can't find an increasing subsequence of length, 3 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 924, 224296, 68828116, 22619133819, 7840755500452, 2821028048006603, 1043673407323512960, 394551874880408537236, 151749451337207342474968, 59191195004960808189336132, 23359564825963961462206920238, 9310230304742966356087780274902, 3742184732645984883297637337792220, 1515182996136698989281708688737300921, 617418136793688883947547938404326669496, 253010619509679454635265004463269593801324, 104200345779805693626261213308002480528201600, 43106244042531101079648780270683655649580658004, 17904253173637280078594453906289176519883657918216] There is no recurrence with ORDER+DEGREE<=, 15 This ends this article, that took, 131.879, seconds to generate have a great day This concludes this article, that took, 131.879, to generate.