Everything you Ever Wanted To Know About the Sequences Enumerating, [1, 2], -Avoiding Words With r 1's, r 2's, ..., r n's, for r=1 to r=, 1 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, 2 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form -1+N More versbosely, we have , for n>=1 -A[1](n) + A[1](n + 1) = 0 subject to the initial conditions A[1](1) = 1 In Maple input format: -A[1](n)+A[1](n+1) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 1 the asymptotics of, A[1](n), to order, 10, is 1 and in Maple input format 1 As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 1. Not bad! This concludes this article, that took, 0.467, to generate. 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=, 1 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! This concludes this article, that took, 4.673, to generate. Everything you Ever Wanted To Know About the Sequences Enumerating, [1, 2, 3, 4], -Avoiding Words With r 1's, r 2's, ..., r n's, for r=1 to r=, 1 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, 4 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, 3763290, 24792705, 167078577, 1148208090, 8026793118, 56963722223, 409687815151, 2981863943718, 21937062144834, 162958355218089] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form 9*(n+1)^2/(n+4)^2-(41+42*n+10*n^2)/(n+4)^2*N+N^2 More versbosely, we have , for n>=1 2 2 9 (n + 1) A[1](n) (41 + 42 n + 10 n ) A[1](n + 1) ------------------ - ------------------------------- + A[1](2 + n) = 0 2 2 (n + 4) (n + 4) subject to the initial conditions A[1](1) = 1, A[1](2) = 2 In Maple input format: 9*(n+1)^2/(n+4)^2*A[1](n)-(41+42*n+10*n^2)/(n+4)^2*A[1](n+1)+A[1](2+n) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 4851753471160837150100300689481738747282810823435772276699885757739766237576813\ 9706393118048700712834036603207534481309985871061408321989079078988935829791023\ 6790827091815421998004133429412064001549773864549292530555692170260055084850744\ 6810191739350963213289281146935841599295425192565111572019016701952448307619615\ 4885766134114580829781616036335866077474564826355633032229435596743564993583088\ 0254520833144203625613914584760867352611861279269941856316176801536507226423616\ 2595043072334485842235160250618056732381345247311150115401618320770913835876356\ 7043430452142414201158359179874140540912044112890992097940848981668858990422177\ 0184245312971766072458648156402183109685681642684629545670776057108586141188886\ 1010002528243116123672367706302341264893794105731652385157483548070407116912231\ 5799236606158558109055982705888332378630930754505638268850234248902654808661677\ 00686435555862421208935360873154986758416971467081973443041280895798852009 the asymptotics of, A[1](n), to order, 10, is 1/2 n / 11 20 965 42021 53529 522635 4937465 81 3 9 |1 - --- + ---- - ----- + ------ - ------ + ------ - ------- | 2 n 2 3 4 5 6 7 \ n 16 n 256 n 128 n 512 n 2048 n 365592491 1653397471 7457444085\ / 4 + --------- - ---------- + ----------| / (16 Pi n ) 8 9 10| / 65536 n 131072 n 262144 n / and in Maple input format 81/16*3^(1/2)/Pi*9^n/n^4*(1-11/2/n+20/n^2-965/16/n^3+42021/256/n^4-53529/128/n^ 5+522635/512/n^6-4937465/2048/n^7+365592491/65536/n^8-1653397471/131072/n^9+ 7457444085/262144/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! This concludes this article, that took, 18.819, to generate. Everything you Ever Wanted To Know About the Sequences Enumerating, [1, 2, 3, 4, 5], -Avoiding Words With r 1's, r 2's, ..., r n's, for r=1 to r=, 1 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, 5 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 2, 6, 24, 119, 694, 4582, 33324, 261808, 2190688, 19318688, 178108704, 1705985883, 16891621166, 172188608886, 1801013405436, 19274897768196, 210573149141896, 2343553478425816, 26525044132374656] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form 64*(2+n)*(n+1)^2/(n+6)/(n+5)^2-2*(214+255*n+91*n^2+10*n^3)/(n+6)/(n+5)^2*N+N^2 More versbosely, we have , for n>=1 2 2 3 64 (2 + n) (n + 1) A[1](n) 2 (214 + 255 n + 91 n + 10 n ) A[1](n + 1) --------------------------- - ------------------------------------------- 2 2 (n + 6) (n + 5) (n + 6) (n + 5) + A[1](2 + n) = 0 subject to the initial conditions A[1](1) = 1, A[1](2) = 2 In Maple input format: 64*(2+n)*(n+1)^2/(n+6)/(n+5)^2*A[1](n)-2*(214+255*n+91*n^2+10*n^3)/(n+6)/(n+5)^ 2*A[1](n+1)+A[1](2+n) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 1130657789098141045073591225728815901284063159474543779647102271803524035595163\ 6503650285306398420518285604894609675709709857289431807799330348060844503196852\ 1420283657898678716307847430987718112639480380239601490998287960118071762618436\ 5072712163272878991500098693501867893233922298056005013299990148151284625311895\ 2599904143505457102019016039807991317096610342940933112949213241222030056555307\ 3714004972355067252646168951159163613191526472199377387518425944903807442870290\ 2605364472788761459370886295611906877109748278944648690646675586008523473119914\ 1546897312593499000861422495869004414557938933331774778172925806665740417887637\ 6489184524455748121290458085449056245486208299551403413100644484554791895527955\ 2287174306771372100511868526646263521049804928202282842255734213679632378096401\ 3193909249871699840261790310222395132931822821514432018257584906977448666962048\ 5724788654571856063748234163592583154118551529817630448232265633553041682543366\ 1633182765331467855374453272829120336115848634126049669070905723244398630943312\ 5232661370117119964405720693552752744533337415381360544596971920774856285689602\ 6353006563950892182683891072930896357244572805655736802238539797995105367752704 the asymptotics of, A[1](n), to order, 10, is n 15/2 / 135 21425 1303245 269500427 12479023305 1536 16 (1/n) |1 - --- + ------ - ------- + --------- - ----------- | 8 n 2 3 4 5 \ 128 n 1024 n 32768 n 262144 n 1068121267125 43095951627525 13300809703073715 495210628215092925 + ------------- - -------------- + ----------------- - ------------------ 6 7 8 9 4194304 n 33554432 n 2147483648 n 17179869184 n 35883069723970515375\ / 3/2 + --------------------| / Pi 10 | / 274877906944 n / and in Maple input format 1536/Pi^(3/2)*16^n*(1/n)^(15/2)*(1-135/8/n+21425/128/n^2-1303245/1024/n^3+ 269500427/32768/n^4-12479023305/262144/n^5+1068121267125/4194304/n^6-\ 43095951627525/33554432/n^7+13300809703073715/2147483648/n^8-495210628215092925 /17179869184/n^9+35883069723970515375/274877906944/n^10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 0.99999999999999999999 Not bad! This concludes this article, that took, 179.754, to generate. Everything you Ever Wanted To Know About the Sequences Enumerating, [1, 2, 3, 4, 5, 6], -Avoiding Words With r 1's, r 2's, ..., r n's, for r=1 to r=, 1 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, 6 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 2, 6, 24, 120, 719, 5003, 39429, 344837, 3291590, 33835114, 370531683, 4285711539, 51990339068, 657723056000, 8636422912277, 117241501095189, 1639974912709122, 23570308719710838, 347217077020664880] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form -225*(2+n)^2*(n+1)^2/(n+9)^2/(n+7)^2+(259*n^2+2176*n+4242)*(2+n)^2/(n+9)^2/(n+7 )^2*N-(19941+17932*n+5631*n^2+742*n^3+35*n^4)/(n+9)^2/(n+7)^2*N^2+N^3 More versbosely, we have , for n>=1 2 2 2 2 225 (2 + n) (n + 1) A[1](n) (259 n + 2176 n + 4242) (2 + n) A[1](n + 1) - ----------------------------- + --------------------------------------------- 2 2 2 2 (n + 9) (n + 7) (n + 9) (n + 7) 2 3 4 (19941 + 17932 n + 5631 n + 742 n + 35 n ) A[1](2 + n) - -------------------------------------------------------- + A[1](n + 3) 2 2 (n + 9) (n + 7) = 0 subject to the initial conditions A[1](1) = 1, A[1](2) = 2, A[1](3) = 6 In Maple input format: -225*(2+n)^2*(n+1)^2/(n+9)^2/(n+7)^2*A[1](n)+(259*n^2+2176*n+4242)*(2+n)^2/(n+9 )^2/(n+7)^2*A[1](n+1)-(19941+17932*n+5631*n^2+742*n^3+35*n^4)/(n+9)^2/(n+7)^2*A [1](2+n)+A[1](n+3) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 8133113626583361817440891242233287333064534828497447842622813416228804415486056\ 1257940498775933215563330574076975060673902585835132304033165108288880666890940\ 5676149847325934289020823291470014868045043238087818050405655103979607762111841\ 9182285855735789689328509127446158407903724631791055130044699331034938127396908\ 1618705802113489707238956755837007089624573785944206004591272178166368567228210\ 1868379193730972704609597911386840938581285952236294897705968311928067811462770\ 7761031371796994844046446816113394438387142105159047818173098675433217852263148\ 3691927159664045723619563407363135034111873310158988179688068914216821866780581\ 8242721591548715639332128599329295224390739200494714359954114950359268999609169\ 6873125433336962238726652359864475405775409035756903859957040507709825533235857\ 2898688910917027498465068887179066787657712369680736728009537180997574759812236\ 3724492392026582582630729660071441568675170420106909252894626563298652080303055\ 3907161629546521755866047467570042156149466209920014057844920921392599582570442\ 5828519684005477418602871704143520227426988282049215347317773205831154922445316\ 7958665766122123668132048774377366199879110277600276563884630631237299096305532\ 3122628629025421726243450661986416834289324256366464416054697389672274379947458\ 3888421771956853671486217116167807725845256154416047189827589783858973524418537\ 9096668933801988561034625 the asymptotics of, A[1](n), to order, 10, is n / 81 3643 240345 51963583 609935319 972294.5631337 25 |1 - --- + ---- - ------ + -------- - --------- | 2 n 2 3 4 5 \ 4 n 16 n 256 n 256 n 25778930909 125534262375 36666814319519 635007253978629 + ----------- - ------------ + -------------- - --------------- 6 7 8 9 1024 n 512 n 16384 n 32768 n 21059097274151839\ / 12 + -----------------| / n 10 | / 131072 n / and in Maple input format 972294.5631337*25^n/n^12*(1-81/2/n+3643/4/n^2-240345/16/n^3+51963583/256/n^4-\ 609935319/256/n^5+25778930909/1024/n^6-125534262375/512/n^7+36666814319519/ 16384/n^8-635007253978629/32768/n^9+21059097274151839/131072/n^10) As a check, the ratio of the actual value at, 1000, to the one predicted by this formula is, 1.0000000000000479338 Not bad! This concludes this article, that took, 1652.362, to generate.