login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix. 6
1, 2, 11, 172, 6327, 474286, 67147431, 17080038508 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
Comments from Brendan McKay, Aug 21 2006: Equivalently, directed graphs (simple but loops allowed) without a few small forbidden subgraphs (those allowing 2 distinct paths of length 2 from vertex x to vertex y for some x,y; I think there are 6 possibilities). One can also consider isomorphism classes of those digraphs.
Comment from Rob Pratt, Aug 03 2008: A121294 provides a lower bound on the maximum number of 1's in such a matrix M. There are cases where a higher number is reached; the following 5 X 5 matrix has 11 ones and its square is binary:
0 0 1 0 0
0 0 0 0 1
1 1 0 0 1
1 1 0 1 0
1 1 0 1 0.
The optimal values seem to match A070214, verified for n <= 7.
Term (5,1) of the n-th power of the 5 X 5 matrix shown is A001045(n), the Jacobsthal sequence. - Gary W. Adamson, Oct 03 2008
a(n) >= A226321(n).
LINKS
Eric Weisstein's World of Mathematics, Background information about adjacency matrices
E. W. Weisstein, (0,1)-Matrix, MathWorld. [P. Petsie, Aug 03 2008]
CROSSREFS
Sequence in context: A051255 A120445 A003088 * A122527 A039747 A049531
KEYWORD
nonn,more
AUTHOR
Dan Dima, Aug 21 2006
EXTENSIONS
Edited by R. J. Mathar, Oct 01 2008
a(7) from R. H. Hardin, Jun 19 2012. This makes it clear that the old A122527 was really a badly-described version of this sequence, and that a(7) was earlier found by Balakrishnan (bvarada2(AT)jhu.edu), Sep 17 2006. - N. J. A. Sloane, Jun 19 2012
Entry revised by N. J. A. Sloane, Jun 19 2012
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:25 EDT 2024. Contains 370953 sequences. (Running on oeis4.)