[seqfan] Re: Matrix defined sequence count

[Neil Sloane]

Certainly it is of interest!
Neil


On Sat, Jan 25, 2014 at 9:09 PM, Jay Anderson <horndude77 at gmail.com> 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/
>



-- 
Dear Friends, I have now retired from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com