1. Peter Br\"and\'en and Toufik mansour, Finite automata and pattern avoidance in words,
2. Seregy Kitaev, Toufik Mansour, Antoine Vella, On avoidance of numbered polyomino patterns.

The program gives a complete answer (up to how fast your computer) to the problems which are related to the above papers, namely to find a formula for |M_{m,n}^k(p)| where given m,k and p. (See below the examples and applications for these programs).

For example, when m=1 we get a formula for the number of words on k letters of length n that avoid a pattern p. When m=2 we get a formula for the number of matrices with two rows and n columns that avoid a pattern p (which could be a matrix of size 2x2 or shape L of three elements). To avoid 2x2 matrix M is equivalent to there no submatrix 2x2 order-isomorphic to M. To avoid a shape L=(L11,L21,L22) is equivalent to there no three element (P_{i1,j1}, p_{i2,j1},p_{i2,j2}) order-isomorphic to L, where i2>i1 and j2>j1.

To find the formula for |[k]^n(p)| we use the ideas from the paper titled "Finite automaton and pattern avoidance in words" authored by Toufik Mansour and Peter Br\"and\"en.

This program divided to two parts: the first part construct in C++, and the second part construct in MAPLE.

/*Program to find the automaton A_m(p,k) for given p,k,m*/
/*                                    by                                              */
/*                           Toufik Mansour                                   */
/*Start*/
#include <stdio.h>

/*Definitions*/
#define MAXCLASSES 4000  /*Maximum classes of the states of the graph Au(p,k)*/

#define MAXLCLASS 100  /*Maximum columns in one class */

int NUMBERLETTER;  /*Number of the letters k in the automaton*/

#define MAXROWS 10  /* maximum rows in the matrices*/

#define MAXCOLS 10 /*maximum columns in the pattern*/

#define MAXBIN 5000  /*sum(k^i,'i'=0...MAXROWS)*/

int mat[MAXBIN][MAXROWS][MAXCOLS];
/*list of all the possiblities to extend a state of length equals number columns in the pattern -1*/

int lmat[MAXBIN];  /*number column of the mat[MAXBIN]*/

int nallmat;  /*number of all the possibilties in mat[MAXBIN]*/

/* The pattern*/
int pattern[MAXROWS][MAXCOLS];
int numbercolumn,numberrow,kindpattern;
/* kindpattern=1d if vector length d,   kindpattern=22 if matrix 2x2,   kindpattern=12 if the pattern of the form L*/

/*three different states and the length*/
int state1[MAXROWS][MAXLCLASS],lstate1;
int state2[MAXROWS][MAXLCLASS],lstate2;
int state0[MAXROWS][MAXLCLASS],lstate0;

/*the Automaton Au(p,k) and the size*/
int Au[MAXCLASSES][MAXCLASSES],sizeAu=0;

int setclass[MAXCLASSES][MAXROWS][MAXLCLASS];
/*the set E(p,k), the set of equivalence classes for given a pattern p, and k letters*/
/*every element in E(p,k) is a state as a matrix of  maximum size maxrows x maxlclass*/

int lsetclass[MAXCLASSES];   /* number column for every state in E(p,k)*/

int nclass;   /*cardinality of |E(p,k)|*/

FILE *fout;    /*output file*/

/*built all the matrices that possibly to extend a state */
/*matrices of rows x d where 0\leq d\leq numbercolumn*/
void extendbymat()
{
 int nc,i,j,i1,j1,ii,nu;
 nallmat=0;
 for(nc=1;nc<1+numbercolumn;nc++)
 {
  nu=1; for(i=0;i<nc*(numberrow);i++) nu=nu*NUMBERLETTER;
  lmat[nallmat]=nc; for(i=0;i<numberrow;i++) for(j=0;j<nc;j++) mat[nallmat][i][j]=0; nallmat++;
  for(ii=0;ii<nu-1;ii++)
  {
   for(i=0;i<numberrow;i++) for(j=0;j<nc;j++) mat[nallmat][i][j]=mat[nallmat-1][i][j];
   i=0; j=0; while(mat[nallmat][i][j]==(NUMBERLETTER-1)) {i++; if(i==numberrow) {j++; i=0;} }
   mat[nallmat][i][j]++;  for(j1=0;j1<j;j1++) for (i1=0;i1<numberrow;i1++) mat[nallmat][i1][j1]=0;
   for(i1=0;i1<i;i1++) mat[nallmat][i1][j]=0; lmat[nallmat]=nc; nallmat++;
  }
 }
}

/*checking that two matrices 2x2,
  or two vectors of length 4, are order-isomorphic*/
int order22(int a,  int b,  int c,  int d,
   int a1, int b1, int c1, int d1)
{
 if ((a<b)&&(a1>=b1)) return(0); if ((a==b)&&(a1!=b1)) return(0); if ((a>b)&&(a1<=b1)) return(0);
 if ((a<c)&&(a1>=c1)) return(0); if ((a==c)&&(a1!=c1)) return(0); if ((a>c)&&(a1<=c1)) return(0);
 if ((a<d)&&(a1>=d1)) return(0);if ((a==d)&&(a1!=d1)) return(0); if ((a>d)&&(a1<=d1)) return(0);
 if ((b<c)&&(b1>=c1)) return(0); if ((b==c)&&(b1!=c1)) return(0); if ((b>c)&&(b1<=c1)) return(0);
 if ((b<d)&&(b1>=d1)) return(0); if ((b==d)&&(b1!=d1)) return(0); if ((b>d)&&(b1<=d1)) return(0);
 if ((c<d)&&(c1>=d1)) return(0); if ((c==d)&&(c1!=d1)) return(0); if ((c>d)&&(c1<=d1)) return(0);
 return(1);
}

/*checking if two vectors of length 3 are order-isomorphic*/
int order3(int a, int b, int c, int a1, int b1, int c1)
{
 if ((a<b)&&(a1>=b1)) return(0); if ((a==b)&&(a1!=b1)) return(0); if ((a>b)&&(a1<=b1)) return(0);
 if ((a<c)&&(a1>=c1)) return(0); if ((a==c)&&(a1!=c1)) return(0); if ((a>c)&&(a1<=c1)) return(0);
 if ((b<c)&&(b1>=c1)) return(0); if ((b==c)&&(b1!=c1)) return(0); if ((b>c)&&(b1<=c1)) return(0);
 return(1);
}

/*checking if two vectors of length 5 are order-isomorphic*/
int order5(int a, int b, int c, int d, int e, int a1, int b1, int c1, int d1, int e1)
{
 if ((a<b)&&(a1>=b1)) return(0); if ((a==b)&&(a1!=b1)) return(0); if ((a>b)&&(a1<=b1)) return(0);
 if ((a<c)&&(a1>=c1)) return(0); if ((a==c)&&(a1!=c1)) return(0); if ((a>c)&&(a1<=c1)) return(0);
 if ((a<d)&&(a1>=d1)) return(0); if ((a==d)&&(a1!=d1)) return(0); if ((a>d)&&(a1<=d1)) return(0);
 if ((a<e)&&(a1>=e1)) return(0); if ((a==e)&&(a1!=e1)) return(0); if ((a>e)&&(a1<=e1)) return(0);
 if ((b<c)&&(b1>=c1)) return(0); if ((b==c)&&(b1!=c1)) return(0); if ((b>c)&&(b1<=c1)) return(0);
 if ((b<d)&&(b1>=d1)) return(0); if ((b==d)&&(b1!=d1)) return(0); if ((b>d)&&(b1<=d1)) return(0);
 if ((b<e)&&(b1>=e1)) return(0); if ((b==e)&&(b1!=e1)) return(0); if ((b>e)&&(b1<=e1)) return(0);
 if ((c<d)&&(c1>=d1)) return(0); if ((c==d)&&(c1!=d1)) return(0); if ((c>d)&&(c1<=d1)) return(0);
 if ((c<e)&&(c1>=e1)) return(0); if ((c==e)&&(c1!=e1)) return(0); if ((c>e)&&(c1<=e1)) return(0);
 if ((d<e)&&(d1>=e1)) return(0); if ((d==e)&&(d1!=e1)) return(0); if ((d>e)&&(d1<=e1)) return(0);
 return(1);
}

/*checking if two vectors of length 6 are order-isomorphic*/
int order6(int a,  int b,  int c,  int d,  int e,  int f,  int a1, int b1, int c1, int d1, int e1, int f1)
{
 if ((a<b)&&(a1>=b1)) return(0); if ((a==b)&&(a1!=b1)) return(0); if ((a>b)&&(a1<=b1)) return(0);
 if ((a<c)&&(a1>=c1)) return(0); if ((a==c)&&(a1!=c1)) return(0); if ((a>c)&&(a1<=c1)) return(0);
 if ((a<d)&&(a1>=d1)) return(0); if ((a==d)&&(a1!=d1)) return(0); if ((a>d)&&(a1<=d1)) return(0);
 if ((a<e)&&(a1>=e1)) return(0); if ((a==e)&&(a1!=e1)) return(0); if ((a>e)&&(a1<=e1)) return(0);
 if ((a<f)&&(a1>=f1)) return(0); if ((a==f)&&(a1!=f1)) return(0); if ((a>f)&&(a1<=f1)) return(0);
 if ((b<c)&&(b1>=c1)) return(0); if ((b==c)&&(b1!=c1)) return(0); if ((b>c)&&(b1<=c1)) return(0);
 if ((b<d)&&(b1>=d1)) return(0); if ((b==d)&&(b1!=d1)) return(0); if ((b>d)&&(b1<=d1)) return(0);
 if ((b<e)&&(b1>=e1)) return(0); if ((b==e)&&(b1!=e1)) return(0); if ((b>e)&&(b1<=e1)) return(0);
 if ((b<f)&&(b1>=f1)) return(0); if ((b==f)&&(b1!=f1)) return(0); if ((b>f)&&(b1<=f1)) return(0);
 if ((c<d)&&(c1>=d1)) return(0); if ((c==d)&&(c1!=d1)) return(0); if ((c>d)&&(c1<=d1)) return(0);
 if ((c<e)&&(c1>=e1)) return(0); if ((c==e)&&(c1!=e1)) return(0); if ((c>e)&&(c1<=e1)) return(0);
 if ((c<f)&&(c1>=f1)) return(0); if ((c==f)&&(c1!=f1)) return(0); if ((c>f)&&(c1<=f1)) return(0);
 if ((d<e)&&(d1>=e1)) return(0); if ((d==e)&&(d1!=e1)) return(0); if ((d>e)&&(d1<=e1)) return(0);
 if ((d<f)&&(d1>=f1)) return(0); if ((d==f)&&(d1!=f1)) return(0); if ((d>f)&&(d1<=f1)) return(0);
 if ((e<f)&&(e1>=f1)) return(0); if ((e==f)&&(e1!=f1)) return(0); if ((e>f)&&(e1<=f1)) return(0);
 return(1);
}

/*if the state0 avoids a 2x2 pattern*/
int avoid22matrix()
{
 int i1,i2,j1,j2,lm,rm;
 rm=numberrow; lm=lstate0; if (lstate0==0) return(1);
 for(i1=0;i1<lm-1;i1++)
 for(i2=i1+1;i2<lm;i2++)
 for(j1=0;j1<rm-1;j1++)
 for(j2=j1+1;j2<rm;j2++)
  if (order22(state0[j1][i1],state0[j2][i1],state0[j1][i2],state0[j2][i2],
   pattern[0][0],pattern[0][1],pattern[1][0],pattern[1][1])==1) return(0);
 return(1);
}

/*if the stae avoids a L pattern*/
int avoid12mat()
{
 int i1,i2,j1,j2,lm,rm;
 rm=numberrow; lm=lstate0; if (lstate0==0) return(1);
 for(i1=0;i1<lm-1;i1++)
 for(i2=i1+1;i2<lm;i2++)
 for(j1=0;j1<rm-1;j1++)
 for(j2=j1+1;j2<rm;j2++)
  if (order3(state0[j1][i1],state0[j2][i1],state0[j2][i2],
   pattern[0][0],pattern[1][0],pattern[1][1])==1) return(0);
 return(1);
}

/*if the state0 avoids pattern of length 3*/
int avoid13vec()
{
 int i1,i2,i3;
 for(i1=0;i1<lstate0-2;i1++)
 for(i2=i1+1;i2<lstate0-1;i2++)
 for(i3=i2+1;i3<lstate0;i3++)
  if(order3(state0[0][i1],state0[0][i2],state0[0][i3],
   pattern[0][0],pattern[0][1],pattern[0][2])==1)
       return(0);
 return(1);
}

/*if the state0 avoids pattern of length 4*/
int avoid14vec()
{
 int i1,i2,i3,i4;
 for(i1=0;i1<lstate0-3;i1++)
 for(i2=i1+1;i2<lstate0-2;i2++)
 for(i3=i2+1;i3<lstate0-1;i3++)
 for(i4=i3+1;i4<lstate0;i4++)
  if(order22(state0[0][i1],state0[0][i2],state0[0][i3],state0[0][i4],
   pattern[0][0],pattern[0][1],pattern[0][2],pattern[0][3])==1)
    return(0);
 return(1);
}

/*if the state0 avoids pattern of length 5*/
int avoid15vec()
{
 int i1,i2,i3,i4,i5;

 for(i1=0;i1<lstate0-4;i1++)
 for(i2=i1+1;i2<lstate0-3;i2++)
 for(i3=i2+1;i3<lstate0-2;i3++)
 for(i4=i3+1;i4<lstate0-1;i4++)
    for(i5=i4+1;i5<lstate0;i5++)
  if(order5(state0[0][i1],state0[0][i2],state0[0][i3],state0[0][i4],state0[0][i5],
   pattern[0][0],pattern[0][1],pattern[0][2],pattern[0][3],pattern[0][4])==1)
    return(0);
 return(1);
}

/*if the state0 avoids pattern of length 6*/
int avoid16vec()
{
 int i1,i2,i3,i4,i5,i6;

 for(i1=0;i1<lstate0-5;i1++)
 for(i2=i1+1;i2<lstate0-4;i2++)
 for(i3=i2+1;i3<lstate0-3;i3++)
 for(i4=i3+1;i4<lstate0-2;i4++)
    for(i5=i4+1;i5<lstate0-1;i5++)
 for(i6=i5+1;i6<lstate0;i6++)
   if(order6(state0[0][i1],state0[0][i2],state0[0][i3],state0[0][i4],
    state0[0][i5],state0[0][i6],pattern[0][0],pattern[0][1],pattern[0][2],
    pattern[0][3],pattern[0][4],pattern[0][5])==1)
   return(0);
 return(1);
}

/*different kinds of configuration of the pattern*/
int avoiding()
{
 if (kindpattern==13) return(avoid13vec());     if (kindpattern==14) return(avoid14vec());
 if (kindpattern==15) return(avoid15vec());     if (kindpattern==16) return(avoid16vec());
 if (kindpattern==22) return(avoid22matrix()); if (kindpattern==12) return(avoid12mat());
 return(-1);
}

/*checking tif the states state1 and state2 are equivalent */
int equivstates()
{
 int i,j,i1,j1,ans1,ans2;
 int statea[MAXROWS][MAXLCLASS],lstatea,stateb[MAXROWS][MAXLCLASS],lstateb;

 lstate0=lstate1;  lstatea=lstate1;
 for(i=0;i<numberrow;i++) for(j=0;j<lstate1;j++)   {state0[i][j]=state1[i][j]; statea[i][j]=state1[i][j];}
 ans1=avoiding();

 lstate0=lstate2;  lstateb=lstate2;
 for(i=0;i<numberrow;i++) for(j=0;j<lstate2;j++) {state0[i][j]=state2[i][j]; stateb[i][j]=state2[i][j];}
 ans2=avoiding();

 if(ans1!=ans2) return(0);

 for(j=0;j<nallmat;j++)
 {
  lstatea=lstate1; lstateb=lstate2;
  for(i1=0;i1<numberrow;i1++) for(j1=0;j1<lmat[j];j1++)
   { statea[i1][j1+lstatea]=mat[j][i1][j1]; stateb[i1][j1+lstateb]=mat[j][i1][j1]; }
  lstatea=lstate1+lmat[j]; lstateb=lstate2+lmat[j];
  lstate0=lstatea;
  for(i1=0;i1<numberrow;i1++) for(j1=0;j1<lstatea;j1++)  {state0[i1][j1]=statea[i1][j1]; }
  ans1=avoiding();
  lstate0=lstateb;
  for(i1=0;i1<numberrow;i1++) for(j1=0;j1<lstateb;j1++)  {state0[i1][j1]=stateb[i1][j1];}
  ans2=avoiding();
  if(ans1!=ans2) return(0);
 }
 return(1);
}

/*check if there a state in E(p,k) that equivalent to state1 which is given*/
int checkequivstates()
{
 int i,i1,j1,ans;
 for(i=0;i<nclass;i++)
 {
  lstate2=lsetclass[i];
  for(i1=0;i1<numberrow;i1++) for(j1=0;j1<lstate2;j1++)  state2[i1][j1]=setclass[i][i1][j1];
  ans=equivstates();  if (ans==1) return(i);
 }
 return(nclass);
}

/*finding the automaton A(p,k) and the set of all the classes E(p,k)*/
void automat()
{
 int i,j,flag=1,nst=1,i1,j1,ans,pns,ans1,numvec;

 numvec=1; for(i=0;i<numberrow;i++) numvec=numvec*NUMBERLETTER;
 /*number possiblities to extend by vector a state*/

 lsetclass[0]=0;  nclass=1; /*first state, the empty state*/
 printf("%d) empty state\n",nclass);
 sizeAu=1; Au[0][0]=0;
 pns=1;
 while(flag==1) /*find another state, if there*/
 {
 flag=0;
 for(i=nst-1;i<pns;i++)
 {
  lstate1=lsetclass[i]; /*take old state*/
  for(i1=0;i1<numberrow;i1++) for(j1=0;j1<lstate1;j1++) state1[i1][j1]=setclass[i][i1][j1];

  lstate1++; /*extend the state by a vector*/
  for(j=0;j<numvec;j++)
  {
   for(i1=0;i1<numberrow;i1++) state1[i1][lstate1-1]=mat[j][i1][0];

   ans=checkequivstates();
   /*check after the extension there old state equivelent to it*/

   if (ans==nclass) /*if no*/
   {
    lstate0=lstate1; /*check if avoiding the pattern*/
    for(i1=0;i1<numberrow;i1++) for(j1=0;j1<lstate0;j1++) state0[i1][j1]=state1[i1][j1];
    ans1=avoiding();

    if(ans1==1) /*if a new state avoid the pattern*/
    {
     flag=1; /*put it as a new state in E(p,k) and extend the automaton*/

     printf("%d) ",nclass+1);
     for(i1=0;i1<numberrow;i1++)
     {
            for(j1=0;j1<lstate1;j1++) {setclass[nclass][i1][j1]=state1[i1][j1];  printf("%d",state1[i1][j1]+1);}
            printf(" , ");
     }
     printf("\n");
     lsetclass[nclass]=lstate1;nclass++;
     for(i1=0;i1<sizeAu+1;i1++) {Au[sizeAu][i1]=0; Au[i1][sizeAu]=0;}
     Au[i][sizeAu]++; sizeAu++;
    }
   }
   else  Au[i][ans]++;
  }
 }
 nst=pns+1; pns=nclass;
 }
}

/*print the automaton A(p,k) to output file*/
void printautomaton()
{
 int i,j;
 printf("The Automaton of the problem of matrices of size");
 printf("%dxN on %d letters avoiding the pattern\n",numberrow,NUMBERLETTER);
 fprintf(fout,"The Automaton of the problem of matrices of size");
 fprintf(fout,"%dxN on %d letters avoiding the pattern\n",numberrow,NUMBERLETTER);
 if (kindpattern==22)
 {
  printf("                                 %d %d\n",pattern[0][0],pattern[0][1]);
  printf("                                 %d %d\n",pattern[1][0],pattern[1][1]);
  fprintf(fout,"                                 %d %d\n",pattern[0][0],pattern[0][1]);
  fprintf(fout,"                                 %d %d\n",pattern[1][0],pattern[1][1]);
 }
 else if ((13<=kindpattern)&&(kindpattern<=16))
 {
  printf("                                 ");
  fprintf(fout,"                                 ");
  for(i=0;i<kindpattern-10;i++) {printf("%d ",pattern[0][i]);fprintf(fout,"%d ",pattern[0][i]);}
  printf("\n");fprintf(fout,"\n");
 }
 else if (kindpattern==12)
 {
  printf("                                 %d",pattern[0][0]);
  printf("                                 %d %d",pattern[1][0],pattern[1][1]);
  fprintf(fout,"                                 %d",pattern[0][0]);
  fprintf(fout,"                                 %d %d",pattern[1][0],pattern[1][1]);
 }
 printf("                     is given by the following matrix\n");
 fprintf(fout,"                     is given by the following matrix\n\n");
 fprintf(fout,"Au:=matrix([[");
 for(i=0;i<sizeAu-1;i++)
 {
  for(j=0;j<sizeAu-1;j++) {printf("%d",Au[i][j]); fprintf(fout,"%d,",Au[i][j]);}
  printf("%d\n",Au[i][sizeAu-1]); fprintf(fout,"%d],\n[",Au[i][sizeAu-1]);
 }
 for(j=0;j<sizeAu-1;j++) {printf("%d",Au[sizeAu-1][j]); fprintf(fout,"%d,",Au[sizeAu-1][j]);}
 printf("%d\n",Au[sizeAu-1][sizeAu-1]); fprintf(fout,"%d]]);\n",Au[sizeAu-1][sizeAu-1]);
}

/*the main procedure*/
void main()
{
int i,ch;
printf("Kind of pattern:\n");
printf("(1) 1x3=***\n\n");
printf("(2) 1x4=****\n\n");
printf("(3) 1x5=*****\n\n");
printf("(10) L= *\n");
printf("       **\n\n");
printf("(11) S= **\n");
printf("       **\n\n");
printf("Enter your choice 1-6 : "); scanf("%d",&ch);
printf("Enter the number of the letters : "); scanf("%d",&NUMBERLETTER);

if ((ch<=3)&&(ch>=1))
 {
 ch++; ch++;
 numberrow=1; numbercolumn=ch; kindpattern=10+ch;
 printf("Enter the pattern: ");
 for(i=0;i<ch;i++) scanf("%d",&pattern[0][i]);
 }
else if(ch==10)
 {
    numbercolumn=2; kindpattern=12;
    printf("Enter the number rows"); scanf("%d",&numberrow);
    printf("Enter the pattern: matrix([[*],[*,*]])");
    scanf("%d",&pattern[0][0]);  scanf("%d",&pattern[1][0]); scanf("%d",&pattern[1][1]);
 }
else if(ch==11)
 {
    numbercolumn=2; kindpattern=22;
    printf("Enter the number rows"); scanf("%d",&numberrow);
    printf("Enter the pattern: matrix([[*,*],[*,*]])");
    scanf("%d",&pattern[0][0]); scanf("%d",&pattern[0][1]); scanf("%d",&pattern[1][0]); scanf("%d",&pattern[1][1]);
 }

extendbymat(); nclass=0; sizeAu=0; automat();
fout=fopen("test.dat","w"); printautomaton(); fclose(fout);
}

formula:=proc()
local S,Au,sizeAu,J,i,j,ii,jj,nn,Values,A,size,B,b,w,form,M:

Au:=args[1]: the input

with(linalg):
J:=factor(minpoly(Au,x)):
S:=roots(J): sizeAu:=rowdim(Au): nn:=nops(S):

Values:={}: size:=0: for i from 1 to nn do Values:=Values union {S[i][1]}: size:=size+S[i][2]: od:

A:=matrix(size,size,[]): w:=linalg[vector](sizeAu,[]): b:=vector(size,[]): B:=linalg[vector](size,[]):

for i from 1 to sizeAu do w[i]:=1: od:

b[1]:=1: B[2]:=evalm(Au): b[2]:=evalm(B[2]&*w)[1]:

for i from 2 to size-1 do B[i+1]:=evalm(B[i]&*Au): b[i+1]:=evalm(B[i+1]&*w)[1]: od:

for i from 1 to size do jj:=0:
     for ii from 1 to nops(Values) do
         for j from 0 to S[ii][2]-1 do
            jj:=jj+1: if i-1>=j then A[i,jj]:=(S[ii][1])^(i-1-j)*binomial(i-1,j): else A[i,jj]:=0: fi:
od: od: od:

w:=linsolve(A,b); printf("First values n=0...12"); M:=vector(13,[]):
for i from 0 to 12 do
   form:=0: jj:=0:
     for ii from 1 to nops(Values) do
        for j from 0 to S[ii][2]-1 do
            jj:=jj+1:  form:=form+w[jj]*(S[ii][1])^(i-j)*binomial(i,j):
     od: od:
  M[i+1]:=form:
od: print(M):

printf("The formula is");
form:=0: jj:=0:
for ii from 1 to nops(Values) do
  for j from 0 to S[ii][2]-1 do jj:=jj+1:  form:=form+w[jj]*(S[ii][1])^(n-j)*binomial(n,j):
od: od: print(form):
end:

Now we give a several examples how to use these two programs and several applications.

Example 1: find a formula for the number of words on k=5 letters of length n that avoid the pattern 1324.
We use the program TOU_AUTO with input k=5 number the letters, and the pattern is a vector of size 4 which is 1 3 2 4, then the output will be in the file test.dat. Now, we take from this file the matrix Au which is
Au:=matrix([[3,1,1,0,0,0,0,0,0,0,0,0],
[0,3,0,1,1,0,0,0,0,0,0,0],
[0,1,3,0,0,1,0,0,0,0,0,0],
[0,0,0,3,0,0,1,1,0,0,0,0],
[0,0,0,0,3,0,0,0,1,1,0,0],
[0,0,0,0,0,3,0,0,0,0,1,1],
[0,0,0,0,0,0,3,0,0,0,0,0],
[0,0,0,0,0,0,1,3,0,1,0,0],
[0,0,0,0,0,0,0,0,3,1,0,0],
[0,0,0,0,0,0,1,0,0,3,0,0],
[0,0,0,0,1,0,0,0,0,1,3,0],
[0,0,0,0,0,0,0,0,1,0,0,3]]);
we put it in Maple, and apply our second step which is TOU_FORMULA by "formula(Au);" so we get the following formula
3^n+2*3^(n-1)*n+4*3^(n-2)*binomial(n,2)+8*3^(n-3)*binomial(n,3)
      +11*3^(n-4)*binomial(n,4)+10*3^(n-5)*binomial(n,5)+5*3^(n-6)*binomial(n,6)
      +3^(n-7)*binomial(n,7).
Besdies that if we apply our remark, then we get that the generating function for this number of words is given by

Example 2: find a formula for the number of matrices with 3 rows on 2 letters avoiding the 2x2 submatrix defined by T_11=1, T_12=2, T_21=2, and T_22=1.
First we apply the first part TOU_AUTO with input avoiding a matrix 2x2 pattern , k=2 number the letters, and m=3 number rows, and the pattern as defined.  Then we get in the output file (test.dat) the automaton which is given by the following matrix:
Au:=matrix([[4,1,1,1,1,0],
[0,4,0,0,1,1],
[0,0,4,0,0,1],
[0,0,1,4,0,1],
[0,0,0,0,4,1],
[0,0,0,0,0,4]]);
Now, we apply the second part TOU_FORMULA by formula(Au); , so we get the following formula