[seqfan] Matrix defined sequence count
Jay Anderson
horndude77 at gmail.com
Sun Jan 26 03:09:23 CET 2014
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
More information about the SeqFan
mailing list