Enumerating 123-avoiding words of lentgth n in the alphabet {1, ...,n}



                              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:

 Let  A(n), be the number of words,w, of length n, in the alphabet {1,...,n}\


that avoid the pattern 123, i.e., you can't find 1<=i1<i2<i3<=, n,

    such that w[i1]<w[i2]<w[i3]

           For the sake of Sloane's OEIS, the first, 20,  terms are

[1, 4, 26, 210, 1897, 18368, 186636, 1965414, 21277685, 235493544, 2653779856,
30357956720, 351719984280, 4119552129280, 48708104589368, 580682799531822, 
6973356315752445, 84286657672243880, 1024694111031383100, 12522664914160322460]


The sequence is annihilated by the following linear recurrence operator with\
     polynomial coefficients, written in Maple input form



3/2*(n-1)*(3*n+2)*(5*n+6)*(3*n+1)*(n+1)/n^2/(5*n+1)/(n+3)/(n+2)-1/2*(-24-92*n+6
*n^2+427*n^3+474*n^4+145*n^5)/n^2/(5*n+1)/(n+3)/(n+2)*N+N^2


                      More versbosely, we have , for n>=1

    (n - 1) (3 n + 2) (5 n + 6) (3 n + 1) (n + 1) A(n)
3/2 --------------------------------------------------
                2
               n  (5 n + 1) (n + 3) (n + 2)

                            2        3        4        5
           (-24 - 92 n + 6 n  + 427 n  + 474 n  + 145 n ) A(n + 1)
     - 1/2 ------------------------------------------------------- + A(n + 2)
                         2
                        n  (5 n + 1) (n + 3) (n + 2)

     = 0



                       subject to the initial conditions



                               A(1) = 1, A(2) = 4



                            In Maple input format:

3/2*(n-1)*(3*n+2)*(5*n+6)*(3*n+1)*(n+1)/n^2/(5*n+1)/(n+3)/(n+2)*A(n)-1/2*(-24-\
92*n+6*n^2+427*n^3+474*n^4+145*n^5)/n^2/(5*n+1)/(n+3)/(n+2)*A(n+1)+A(n+2) = 0


        Just for fun, the number of ways of doing it with n=, 1000, is

2832451294834195438895066281158989884903275868717693046645158843991391281739583\
5408702462351580097335027150265388341588688808464390872168496651821336639058734\
5828401757989758978565140648502872778400605849155058772320417599712297829974114\
9713721812684650931361225378095429420217328353416778420818587621819380349860486\
2979823519352629981517469687565666070621887139349095312320990426173981513654276\
1285922386368568782256250818252832967586183066170476677692873883756363434978259\
3005352156042828652327039070779847851969407846941854901389903458181804031624678\
4603870686102463163091606216418247250471516197781078157377169835581026965968364\
3487823326471961943482632371351347760938890584267439378758028584023853804427309\
9068151444080694994270183655453387145218134112198645360966017624019143271619845\
9418124240861015539848201950449564576227861980486153937371244251254691253231940\
7048664029187424216359147104016589563060858329879404388070971852714161368626831\
2835128741160451545805200635417927827938019692885956832264398184700964268554543\
4326154632320940468332634591049264184322675746678450878176469616355546958072146\
236250748447844352


                   the asymptotics of, A(n), to order, 6, is

   1/2  1/2   n  (-n) /    11     14083      7961993      473105189
8 3    5    27  2     |1 - --- + -------- - ---------- + ------------
                      |    9 n          2            3              4
                      \          10125 n    6834375 n    307546875 n

        287764850017      109009569569639 \   /         2
     - --------------- + -----------------|  /  (75 Pi n )
                     5                   6| /
       345990234375 n    46708681640625 n /



                           and in Maple input format

8/75*3^(1/2)*5^(1/2)/Pi*27^n*2^(-n)/n^2*(1-11/9/n+14083/10125/n^2-7961993/
6834375/n^3+473105189/307546875/n^4-287764850017/345990234375/n^5+
109009569569639/46708681640625/n^6)


As a check, the ratio of the actual value at, 1000,

    to the one predicted by this formula is, 1.00000000000000000000132302881

                                    Not bad!

          This concludes this article, that took, 28.527, to generate.