[seqfan] Re: Matrix defined sequence count

[israel at math.ubc.ca]

There is a graph-theoretic interpretation of this. An m x m matrix M of 0's 
and 1's is the adjacency matrix of a directed graph (not necessarily 
simple, i.e. loops are allowed) of m vertices, and (M^n)_{1,1} is the 
number of n-step walks starting and ending at vertex 1. Variants of this 
would include restricting the matrix to be symmetric (corresponding to an 
undirected graph) and having all 0's on the diagonal (so the (directed) 
graph is simple).

Robert Israel
University of British Columbia and D-Wave Systems


On Jan 25 2014, Jay Anderson wrote:

>The fibonacci sequence can be found in powers of the matrix M=[0 1; 1
>1] (equivalent to a system of recursive equations). The upper left
>position of M^n is fib(n-1). This is well known, but it got me
>thinking how many different sequences can be defined like this for
>matrices of size NxN having only 0's and 1's.
>
>For example N=2 gives these matrices and resulting sequences:
>[0 0; 0 0] => 0 0 0 0 0 ...
>[1 0; 0 0] => 1 1 1 1 1 ...
>[0 1; 0 0] => 0 0 0 0 0 ...
>[1 1; 0 0] => 1 1 1 1 1 ...
>[0 0; 1 0] => 0 0 0 0 0 ...
>[1 0; 1 0] => 1 1 1 1 1 ...
>[0 1; 1 0] => 0 1 0 1 0 ...
>[1 1; 1 0] => 1 2 3 5 8 ...
>[0 0; 0 1] => 0 0 0 0 0 ...
>[1 0; 0 1] => 1 1 1 1 1 ...
>[0 1; 0 1] => 0 0 0 0 0 ...
>[1 1; 0 1] => 1 1 1 1 1 ...
>[0 0; 1 1] => 0 0 0 0 0 ...
>[1 0; 1 1] => 1 1 1 1 1 ...
>[0 1; 1 1] => 0 1 1 2 3 ...
>[1 1; 1 1] => 1 2 4 8 16 ...
>
>Of these there are 6 distinct sequences. (Also note that you only need
>to go through the first 3 values of each sequence to verify
>uniqueness. More generally you need to go through the first 2N-1
>values to verify uniqueness. I found this by trial and error so I
>don't have any proof for why this might be the case.)
>
>For other values of N a quick program gives 2, 6, 50, 1140, 86052, ...
>for N = 1, 2, ...
>
>Going further than the 5th term was too much for my brute force
>program. Any ideas on what the next term is or a better than brute
>force way of calculating?
>
>I didn't see this in OEIS, but it seems appropriate (a sequence about
>sequences). Is this of interest or is it too contrived?
>
>-----Jay Anderson
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>