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=, 4 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](n + 2) = 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](n+2) = 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! ------------------------------------------------------------------------- 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, 4 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 6, 90, 1879, 47024, 1331664, 41250519, 1367533365, 47808569835, 1744233181074, 65905305836049, 2564220925607625, 102277575120518170, 4167486279986250932, 172988069360147449566, 7298137818882637998561, 312349784398279829229533, 13539988681466075755541070, 593697458037818682683254284, 26302053106583451923036304267] The sequence is annihilated by the following linear recurrence operator with\ polynomial coefficients, written in Maple input form -2916*(n+2)*(125877543736438014048*n^2+556752649373633349814*n+ 583919439330734442963)*(n+1)^2*(2*n+1)^2/(n+4)/(146949290712243118000*n^2+ 566799365756217693062*n+536211454725376896021)/(n+5)^2/(2*n+9)^2+12*(n+2)*( 41902292735037258217056*n^6+222400160207160320989872*n^5-\ 372576915924923774963448*n^4-5004686704133134689081742*n^3-\ 13339000727009521968574551*n^2-14986457712461886248227631*n-\ 6260352162234160006794906)/(n+4)/(146949290712243118000*n^2+ 566799365756217693062*n+536211454725376896021)/(n+5)^2/(2*n+9)^2*N-(n+3)*( 23820522077322908587584*n^6-874611930230451974378360*n^5-\ 12128754785712762702441820*n^4-59126186636214456667623502*n^3-\ 139212803851345113506421497*n^2-160738903071163960487438043*n-\ 73058321754432872829600630)/(n+4)/(146949290712243118000*n^2+ 566799365756217693062*n+536211454725376896021)/(n+5)^2/(2*n+9)^2*N^2-1/3*( 94389117512395618060544*n^6+1845614744877322376921936*n^5+ 14701170203109958120493520*n^4+60967565848461695994431074*n^3+ 138559796127345966348598225*n^2+163234731158382314977549563*n+ 77687338677422990393736594)/(146949290712243118000*n^2+566799365756217693062*n+ 536211454725376896021)/(n+5)^2/(2*n+9)^2*N^3+N^4 More versbosely, we have , for n>=1 - 2916 (n + 2) ( 2 125877543736438014048 n + 556752649373633349814 n + 583919439330734442963) 2 2 / 2 2 (n + 1) (2 n + 1) A[2](n) / ((n + 4) %1 (n + 5) (2 n + 9) ) + 12 / 6 5 (n + 2) (41902292735037258217056 n + 222400160207160320989872 n 4 3 - 372576915924923774963448 n - 5004686704133134689081742 n 2 - 13339000727009521968574551 n - 14986457712461886248227631 n / 2 - 6260352162234160006794906) A[2](n + 1) / ((n + 4) %1 (n + 5) / 2 6 (2 n + 9) ) - (n + 3) (23820522077322908587584 n 5 4 - 874611930230451974378360 n - 12128754785712762702441820 n 3 2 - 59126186636214456667623502 n - 139212803851345113506421497 n - 160738903071163960487438043 n - 73058321754432872829600630) A[2](n + 2) / 2 2 6 / ((n + 4) %1 (n + 5) (2 n + 9) ) - 1/3 (94389117512395618060544 n / 5 4 + 1845614744877322376921936 n + 14701170203109958120493520 n 3 2 + 60967565848461695994431074 n + 138559796127345966348598225 n + 163234731158382314977549563 n + 77687338677422990393736594) A[2](n + 3) / 2 2 / (%1 (n + 5) (2 n + 9) ) + A[2](n + 4) = 0 / %1 := 2 146949290712243118000 n + 566799365756217693062 n + 536211454725376896021 subject to the initial conditions A[2](1) = 1, A[2](2) = 6, A[2](3) = 90, A[2](4) = 1879 In Maple input format: -2916*(n+2)*(125877543736438014048*n^2+556752649373633349814*n+ 583919439330734442963)*(n+1)^2*(2*n+1)^2/(n+4)/(146949290712243118000*n^2+ 566799365756217693062*n+536211454725376896021)/(n+5)^2/(2*n+9)^2*A[2](n)+12*(n+ 2)*(41902292735037258217056*n^6+222400160207160320989872*n^5-\ 372576915924923774963448*n^4-5004686704133134689081742*n^3-\ 13339000727009521968574551*n^2-14986457712461886248227631*n-\ 6260352162234160006794906)/(n+4)/(146949290712243118000*n^2+ 566799365756217693062*n+536211454725376896021)/(n+5)^2/(2*n+9)^2*A[2](n+1)-(n+3 )*(23820522077322908587584*n^6-874611930230451974378360*n^5-\ 12128754785712762702441820*n^4-59126186636214456667623502*n^3-\ 139212803851345113506421497*n^2-160738903071163960487438043*n-\ 73058321754432872829600630)/(n+4)/(146949290712243118000*n^2+ 566799365756217693062*n+536211454725376896021)/(n+5)^2/(2*n+9)^2*A[2](n+2)-1/3* (94389117512395618060544*n^6+1845614744877322376921936*n^5+ 14701170203109958120493520*n^4+60967565848461695994431074*n^3+ 138559796127345966348598225*n^2+163234731158382314977549563*n+ 77687338677422990393736594)/(146949290712243118000*n^2+566799365756217693062*n+ 536211454725376896021)/(n+5)^2/(2*n+9)^2*A[2](n+3)+A[2](n+4) = 0 Just for fun, the number of ways of doing it with n=, 1000, is 2688844639803243684123211100701545181641716252967026849063873147150773467898853\ 9706977106339198923607271935673607395567156537846584871637570293157755420212122\ 3457002361121930342736419915334712379931039086683034496398182169695760185291167\ 6918965567860549806538343596092600064578024371175156518635606595507332975447882\ 1227668011891189305176282256031667360687605652452364490956359483876423067764834\ 0254967856286621757580603162616577144330282475739759181678231840180170138302552\ 4409257053492106223267398718702322652280678460596926535075120794051791592610898\ 0064604821872704934346119986108215861143538147554152646329350114871713482527748\ 5023125656514879223121989761239658416019822342664522854921726328279657357601572\ 8020392862517638146821691340188969888351994089622767986286787830747195308266300\ 2721129230545584872725718168508700187796741023078490479344147383859382918938017\ 9384303033566912774287815785302122900505759703658797466352507015557670633175990\ 2533340912167789924277399521897741436044552611014977396870264657869801772273733\ 5036032632189538697087997230838414785634101843555359148477399352220767066323841\ 7960146915273223951890984307689554995317608005807866986608178914179181319459387\ 5023481051991638953054643258240208925657898799439953863897108450788520807840445\ 9886653621555701355004422253179908442391533119457534251779368258483803333685793\ 2984864647216282648039957603453456061736363248268491671389240184426195420492463\ 0503101408059170383196579429553437650556217468138024361647337635731923364141046\ 9307412601328636666395401493835115191399640074772075889209135097459947952041456\ 4282756053850453509585182010710558121924004642552831475757581704865288030544229\ 1329993033231444922110364140647448815448007361552119826445749 the asymptotics of, A[2](n), to order, 10, is 1/2 n / 694 308705 343262750 112960428623 16 3 54 |1 - ----- + -------- - ----------- + -------------- | 243 n 2 3 4 \ 59049 n 43046721 n 10460353203 n 35517030635842 30803592734708705 9381848950087200050 - ---------------- + ------------------- - --------------------- 5 6 7 2541865828329 n 1853020188851841 n 450283905890997363 n 2275912381021000592629 7941357376938381648955054 + ------------------------ - --------------------------- 8 9 109418989131512359209 n 239299329230617529590083 n 531468266062905735487854385 \ / 4 + ------------------------------| / (81 Pi n ) 10| / 58149737003040059690390169 n / and in Maple input format 16/81*3^(1/2)/Pi*54^n/n^4*(1-694/243/n+308705/59049/n^2-343262750/43046721/n^3+ 112960428623/10460353203/n^4-35517030635842/2541865828329/n^5+30803592734708705 /1853020188851841/n^6-9381848950087200050/450283905890997363/n^7+ 2275912381021000592629/109418989131512359209/n^8-7941357376938381648955054/ 239299329230617529590083/n^9+531468266062905735487854385/ 58149737003040059690390169/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, 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, 4 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 20, 1680, 173891, 21347262, 2977892253, 455912368540, 74876841353159, 12990339123973119, 2354973430941967605, 442587722191655715108, 85717352536181708342445, 17029266882947116165470103, 3457866959157770598680361537, 715559803849259851987691458500, 150551218551130203662620787992583, 32142433864805658006358724788905375, 6952245776854966150188862330300561056, 1521352773314475957928865900786243945640 , 336425217352069009616581283985388825084233] There is no recurrence with ORDER+DEGREE<=, 15 ------------------------------------------------------------------------- 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, 4 For the sake of Sloane's OEIS, the first, 20, terms of this sequence are [1, 70, 34650, 16140983, 8854463421, 5532980565456, 3798011394008444, 2798461806432513085, 2179251644112128926809, 1774029308605731224234922, 1497612094060753803137726582, 1303178757814574200714348639251, 1163471249071555286949793002571005, 1061855751542748987658894786275614548, 987782284350242764771833528063298286256, 934347073922599172485027979820932703181401, 896920771124692119469714569436435897896032337, 872344761827372239609582067450327869949604599310, 858443797096732666126199560092160533779016423423858, 853721670141491635889318300245321802861301277299323117] There is no recurrence with ORDER+DEGREE<=, 15 This concludes this article, that took, 784.351, to generate.