<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2600.0" name=GENERATOR></HEAD>
<BODY bottomMargin=0 leftMargin=3 topMargin=0 rightMargin=3>
<DIV></DIV>
<DIV>Dear SeqFans, <BR>I would like to share with you a surprising matrix
formulation<BR>for the enumeration of acyclic automata (with i
inputs).<BR> <BR>I would never have found these results without Valery
Liskovets' <BR>sequences on automata and the formulas he derived for them.
</DIV>
<DIV> <BR>Below I give a peculiar matrix equation and the amazing
solution, <BR>followed by a few examples (several more examples exist in
OEIS). <BR> <BR>For the love of sequences,
<BR>Paul<BR>----------------------------------------------------------------<BR> <BR>MATRIX
EQUATION. <BR>Given a polynomial function F(x) with integer coefficients,
<BR>find the infinite lower triangular matrix T that satisfies: <BR>
F(T) = SHIFT_UP(T) <BR>with diagonal(T) = {1,2,3,4,...} <BR>where SHIFT_UP(T)
shifts each column of T up 1 row. <BR> <BR>SOLUTION. <BR>Let the infinite
lower triangular matrix P be defined by: <BR> P(n,k) =
(-1)^(n-k)*F(k)^(n-k)/(n-k)! for n>=k>=1<BR>and D be the infinite
diagonal matrix: <BR> diagonal(D) = {1,2,3,4,...} <BR>then the
integer matrix T is given by the diagonalization: <BR> T =
P*D*P^-1 <BR>and also satisfies: </DIV>
<DIV> F(T)*T^n = SHIFT_UP( T^(n+1) - D*T^n ) </DIV>
<DIV>for all
n.<BR>----------------------------------------------------------------<BR> <BR>EXAMPLES.<BR>In
the following examples, the polynomials are: F(k) = (k+1)^i -1 <BR>thus
the resultant matrices M = P*D*P^-1 are solutions
to:<BR> (M + I)^i - I = SHIFT_UP(M)<BR>where the
first column of M will enumerate: <BR>"Deterministic completely defined acyclic
automata with i inputs and<BR>n+1 transient labeled states including a unique
state having all<BR>transitions to the absorbing state."
(Liskovets)<BR> <BR>For i=2. <BR>Sequences: A082159, A082163,
A082171.<BR> <BR>Define P to be the recurrence coefficients in Liskovets'
formula for A082171:<BR> P(n,k) =
(-1)^(n-k)*((k+1)^2-1)^(n-k)/(n-k)!<BR>Thus P =<BR>1/0!,<BR>-7/1!,
1/0!,<BR>49/2!, -26/1!, 1/0!,<BR>-343/3!, 676/2!, -63/1!, 1/0!,<BR>2401/4!,
-17576/3!, 3969/2!, -124/1!, 1/0!,<BR>-16807/5!, 456976/4!, -250047/3!,
15376/2!, -215/1!, 1/0!,<BR>117649/6!, -11881376/5!, 15752961/4!, -1906624/3!,
46225/2!, -342/1!, 1/0!,<BR>...</DIV>
<DIV> </DIV>
<DIV>Now P^-1 = A082171 (as a triangular matrix, with terms divided by
factorials) <BR>with A082159 found in the left-most column: <BR>P^-1 =
<BR>1/0!,<BR>3/1!, 1/0!,<BR>39/2!, 8/1!, 1/0!,<BR>1206/3!, 176/2!, 15/1!,
1/0!,<BR>69189/4!, 7784/3!, 495/2!, 24/1!, 1/0!,<BR>6416568/5!, 585408/4!,
29430/3!, 1104/2!, 35/1!, 1/0!,<BR>881032059/6!, 67481928/5!, 2791125/4!,
84600/3!, 2135/2!, 48/1!, 1/0!,<BR>... <BR>Let D be the infinite diagonal matrix
where diagonal(D) = {1,2,3,...}.</DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV>Then M = P*D*P^-1 satisfies the matrix equation:</DIV>
<DIV> </DIV>
<DIV> (M + I)^2 - I = SHIFT_UP(M) where diag(M) =
{1,2,3,...}.</DIV>
<DIV> </DIV>
<DIV>This M is a triangle with A082163 as the left-most column:</DIV>
<DIV><A
href="http://www.research.att.com/projects/OEIS?Anum=A103236">http://www.research.att.com/projects/OEIS?Anum=A103236</A></DIV>
<DIV> </DIV>
<DIV>M = P*D*P^-1 =
<BR>1,<BR>3,2,<BR>15,8,3,<BR>114,56,15,4,<BR>1191,568,135,24,5,<BR>15993,7536,1710,264,35,6,<BR>263976,123704,27495,4008,455,48,7,<BR>5189778,2425320,533565,75696,8050,720,63,8,<BR>...<BR>where
(M + I)^2 - I = SHIFT_UP(M)
=<BR>3,<BR>15,8,<BR>114,56,15,<BR>1191,568,135,24,<BR>15993,7536,1710,264,35,<BR>...<BR>==============================================<BR>For
i=3. <BR>Sequences: A082160, A082164, A082172.</DIV>
<DIV> </DIV>
<DIV>Define P to be the recurrence coefficients in Liskovets' formula for
A082172:<BR> P(n,k) =
(-1)^(n-k)*((k+1)^3-1)^(n-k)/(n-k)!<BR>Thus P = <BR>1/0!,<BR>-7/1!,
1/0!,<BR>49/2!, -26/1!, 1/0!,<BR>-343/3!, 676/2!, -63/1!, 1/0!,<BR>2401/4!,
-17576/3!, 3969/2!, -124/1!, 1/0!,<BR>-16807/5!, 456976/4!, -250047/3!,
15376/2!, -215/1!, 1/0!,<BR>117649/6!, -11881376/5!, 15752961/4!, -1906624/3!,
46225/2!, -342/1!, 1/0!,<BR>...<BR> <BR>where P^-1 = A082172 (as a
triangular matrix, with terms divided by factorials) <BR>with A082160 found in
the left-most column: <BR>P^-1 = <BR>1/0!,<BR>7/1!, 1/0!,<BR>315/2!, 26/1!,
1/0!,<BR>45682/3!, 2600/2!, 63/1!, 1/0!,<BR>15646589/4!, 675194/3!, 11655/2!,
124/1!, 1/0!,<BR>10567689552/5!, 366349152/4!, 4861458/3!, 37944/2!, 215/1!,
1/0!,<BR>...</DIV>
<DIV>Let D be the infinite diagonal matrix where diagonal(D) =
{1,2,3,...}.</DIV>
<DIV> </DIV>
<DIV> </DIV>
<DIV>Then M = P*D*P^-1 satisfies the matrix equation:</DIV>
<DIV> </DIV>
<DIV> (M + I)^3 - I = SHIFT_UP(M) where diag(M) =
{1,2,3,...}.</DIV>
<DIV> </DIV>
<DIV>This M is a triangle with A082164 as the left-most column:</DIV>
<DIV><A
href="http://www.research.att.com/projects/OEIS?Anum=A103237">http://www.research.att.com/projects/OEIS?Anum=A103237</A></DIV>
<DIV> </DIV>
<DIV>M = P*D*P^-1 = <BR>1,<BR>7, 2,<BR>133, 26, 3,<BR>5362, 962, 63,
4,<BR>380093, 66794, 3843, 124, 5,<BR>42258384, 7380100, 409248, 11284, 215,
6,<BR>6830081860, 1190206134, 65160081, 1709836, 27305, 342,
7,<BR>1520132414241, 264665899160, 14416260516, 371199704, 5585270, 57798, 511,
8,<BR>...<BR>where (M + I)^3 - I = SHIFT_UP(M) =<BR>7,<BR>133,
26,<BR>5362, 962, 63,<BR>380093, 66794, 3843, 124,<BR>42258384, 7380100, 409248,
11284,
215,<BR>...<BR>==============================================<BR>END.</DIV></BODY></HTML>