OEIS/DFSA

Counts of arrays

More than 20000 sequences in the OEIS enumerate arrays with special properties. The sequences were defined by Ron Hardin, often with conjectured ordinary (rational) generating functions. Such o.g.f.s and/or linear recurrences with constant coefficients were also contributed by Colin Barker. We want to derive such g.f.s. systematically. As a first example, we take:

A223615 Number of n X 3 0..1 arrays with rows and columns unimodal.
Column 3 of A223620
G.f.: x*(7 + 44*x^2 - 20*x^3 + 20*x^4 - 6*x^5 + x^6) / (1 - x)^7.
a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n > 7.

Unimodal words

A unimodal word w_i has one "plateau" - first the symbols are increasing (w_i <= w_i+1), then they are decreasing (w_i >= w_i+1).

For the alphabet {0, 1} the unimodal words of length n are:

 n=1   2    3     4
   0  00  000  0000
   1  01  001  0001
      10  010  0010
      11  011  0011
          100  0100
          110  0110
          111  0111
               1000
               1100
               1110
               1111
 ------------------
 # 2   4    7    11 -> (central polygonal numbers)

A word is unimodal iff it does not match the regular expression pattern 100*1. Words of length 1 or 2 are always unimodal.

Deterministic Finite State Automaton (DFSA)

The DFSA for unimodal words over the alphabet {0, 1} has a simple transition table with 3 states:

         symbol
 state|   0   1 
 -----+--------- 
    s1|  s1  s2
    s2|  s3  s2
    s3|  s3  x0

We always use a start state of 1. Successor state 0 is "forbidden", since it would lead to a non-unimodal word.

Matrices of words

Now we arrange the words in columns of an n X k matrix, with a specified number k of parallel columns of length n, and we ask for the number of such arrangeents depending on n. In addition, we require that the rows in the matrix also have the unimodal property. Then we get the following DFSA table for k=2 :

We begin with 2 columns, and we denote the states by pairs of substates sit_j.

      |  0 0   0 1   1 0   1 1   # valid inputs
 -----+-------------------------
1 s1t1|  s1t1  s1t2  s2t1  s2t2  4
2 s1t2|  s1t3  s1t2  s2t3  s2t2  4
3 s1t3|  s1t3  s1x0  s2t3  s2x0  2
4 s2t1|  s3t1  s3t2  s2t1  s2t2  4
5 s2t2|  s3t3  s3t2  s2t3  s2t2  4
6 s2t3|  s3t3  s3x0  s2t3  s2x0  2
7 s3t1|  s3t1  s3t2  x0t1  x0t2  2
8 s3t2|  s3t3  s3t2  x0t3  x0t2  2
9 s3t3|  s3t3  s3x0  x0t3  x0x0  1

When the states are numbered 1, 2, 3, ..., the table reduces to:

   |  00 01 10 11  #vi
 -----+-------------------------
  1|  1  2  4  5    4
  2|  3  2  6  5    4
  3|  3  0  6  0    2
  4|  7  8  4  5    4
  5|  9  8  6  5    4
  6|  9  0  6  0    2
  7|  7  8  0  0    2
  8|  9  8  0  0    2
  9|  9  0  0  0    1

There is a Perl program that evaluates such DFSAs:

perl dfsa.pl -d 1 4 "1,2,4,5,3,2,6,5,3,0,6,0,7,8,4,5,9,8,6,5,9,0,6,0,7,8,0,0,9,8,0,0,9,0,0,0"

Other regular languages

A124696 is another example of a finite state machine, as explained in the OEIS wiki article.