Automata Matrix Formulation

Sun Apr 3 21:10:58 CEST 2005

Dear SeqFans,  
I would like to share with you a surprising matrix formulation
for the enumeration of acyclic automata (with i inputs).

I would never have found these results without Valery Liskovets' 
sequences on automata and the formulas he derived for them. 

Below I give a peculiar matrix equation and the amazing solution, 
followed by a few examples (several more examples exist in OEIS). 

For the love of sequences, 
Paul
----------------------------------------------------------------

MATRIX EQUATION.  
Given a polynomial function F(x) with integer coefficients, 
find the infinite lower triangular matrix T that satisfies: 
   F(T) = SHIFT_UP(T) 
with diagonal(T) = {1,2,3,4,...} 
where SHIFT_UP(T) shifts each column of T up 1 row. 

SOLUTION. 
Let the infinite lower triangular matrix P be defined by: 
   P(n,k) = (-1)^(n-k)*F(k)^(n-k)/(n-k)!  for n>=k>=1
and D be the infinite diagonal matrix: 
   diagonal(D) = {1,2,3,4,...} 
then the integer matrix T is given by the diagonalization: 
   T = P*D*P^-1 
and also satisfies: 
   F(T)*T^n = SHIFT_UP( T^(n+1) - D*T^n ) 
for all n.
----------------------------------------------------------------

EXAMPLES.
In the following examples, the polynomials are:  F(k) = (k+1)^i -1 
thus the resultant matrices M = P*D*P^-1 are solutions to:
     (M + I)^i - I  = SHIFT_UP(M)
where the first column of M will enumerate: 
"Deterministic completely defined acyclic automata with i inputs and
n+1 transient labeled states including a unique state having all
transitions to the absorbing state." (Liskovets)

For i=2. 
Sequences: A082159, A082163, A082171.

Define P to be the recurrence coefficients in Liskovets' formula for
A082171:
     P(n,k) = (-1)^(n-k)*((k+1)^2-1)^(n-k)/(n-k)!
Thus P =
1/0!,
-7/1!, 1/0!,
49/2!, -26/1!, 1/0!,
-343/3!, 676/2!, -63/1!, 1/0!,
2401/4!, -17576/3!, 3969/2!, -124/1!, 1/0!,
-16807/5!, 456976/4!, -250047/3!, 15376/2!, -215/1!, 1/0!,
117649/6!, -11881376/5!, 15752961/4!, -1906624/3!, 46225/2!, -342/1!,
1/0!,
...

Now P^-1 = A082171 (as a triangular matrix, with terms divided by
factorials) 
with A082159 found in the left-most column: 
P^-1 = 
1/0!,
3/1!, 1/0!,
39/2!, 8/1!, 1/0!,
1206/3!, 176/2!, 15/1!, 1/0!,
69189/4!, 7784/3!, 495/2!, 24/1!, 1/0!,
6416568/5!, 585408/4!, 29430/3!, 1104/2!, 35/1!, 1/0!,
881032059/6!, 67481928/5!, 2791125/4!, 84600/3!, 2135/2!, 48/1!, 1/0!,
... 
Let D be the infinite diagonal matrix where diagonal(D) = {1,2,3,...}.

Then M = P*D*P^-1  satisfies the matrix equation:

    (M + I)^2 - I = SHIFT_UP(M)  where diag(M) = {1,2,3,...}.

This M is a triangle with A082163 as the left-most column:
http://www.research.att.com/projects/OEIS?Anum=A103236

M = P*D*P^-1  = 
1,
3,2,
15,8,3,
114,56,15,4,
1191,568,135,24,5,
15993,7536,1710,264,35,6,
263976,123704,27495,4008,455,48,7,
5189778,2425320,533565,75696,8050,720,63,8,
...
where  (M + I)^2 - I  = SHIFT_UP(M) =
3,
15,8,
114,56,15,
1191,568,135,24,
15993,7536,1710,264,35,
...
==============================================
For i=3. 
Sequences: A082160, A082164, A082172.

Define P to be the recurrence coefficients in Liskovets' formula for
A082172:
     P(n,k) = (-1)^(n-k)*((k+1)^3-1)^(n-k)/(n-k)!
Thus P = 
1/0!,
-7/1!, 1/0!,
49/2!, -26/1!, 1/0!,
-343/3!, 676/2!, -63/1!, 1/0!,
2401/4!, -17576/3!, 3969/2!, -124/1!, 1/0!,
-16807/5!, 456976/4!, -250047/3!, 15376/2!, -215/1!, 1/0!,
117649/6!, -11881376/5!, 15752961/4!, -1906624/3!, 46225/2!, -342/1!,
1/0!,
...

where P^-1 = A082172 (as a triangular matrix, with terms divided by
factorials) 
with A082160 found in the left-most column: 
P^-1 = 
1/0!,
7/1!, 1/0!,
315/2!, 26/1!, 1/0!,
45682/3!, 2600/2!, 63/1!, 1/0!,
15646589/4!, 675194/3!, 11655/2!, 124/1!, 1/0!,
10567689552/5!, 366349152/4!, 4861458/3!, 37944/2!, 215/1!, 1/0!,
...
Let D be the infinite diagonal matrix where diagonal(D) = {1,2,3,...}.

Then M = P*D*P^-1  satisfies the matrix equation:

    (M + I)^3 - I = SHIFT_UP(M)  where diag(M) = {1,2,3,...}.

This M is a triangle with A082164 as the left-most column:
http://www.research.att.com/projects/OEIS?Anum=A103237

M = P*D*P^-1  = 
1,
7, 2,
133, 26, 3,
5362, 962, 63, 4,
380093, 66794, 3843, 124, 5,
42258384, 7380100, 409248, 11284, 215, 6,
6830081860, 1190206134, 65160081, 1709836, 27305, 342, 7,
1520132414241, 264665899160, 14416260516, 371199704, 5585270, 57798, 511,
8,
...
where  (M + I)^3 - I  = SHIFT_UP(M) =
7,
133, 26,
5362, 962, 63,
380093, 66794, 3843, 124,
42258384, 7380100, 409248, 11284, 215,
...
==============================================
END.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050403/f51b6afb/attachment.htm>