|
Search: id:A006506
|
|
|
| A006506 |
|
Number of n X n binary matrices with no 2 adjacent 1's, or configurations of non-attacking princes on an n X n board, where a "prince" attacks the four adjacent (non-diagonal) squares. Also number of independent sets of vertices in n X n lattice.
(Formerly M1816)
|
|
+0
20
|
|
| 2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783
(list; graph; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
A two-dimensional generalization of the Fibonacci numbers.
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
|
|
LINKS
|
S. R. Finch, Hard Square Entropy Constant
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Index entries for sequences related to binary matrices
Peter Tittmann, Enumeration in Graphs
|
|
FORMULA
|
Limit n ->infty (a(n))^(1/n^2) =c1=1.50304... is the hard square entropy constant A085850. - Benoit Cloitre, Nov 16 2003
a(n) appears to behave like A * c3^n * c1^(n^2) where c1 is as above, c3 = 1.143519129587 approximately A = 1.0660826 approximately. This is based on numerical analysis of a(n) for n up to 19. - Brendan McKay, Nov 16 2003
|
|
MAPLE
|
A006506 := proc(N) local i, j, p, q; p := 1+x11;
for i from 2 to N do q := p-select(has, p, x.(i-1).1); p := p+expand(q*x.i.1) od; for j from 2 to N do
q := p-select(has, p, x1.(j-1)); p := subs(x1.(j-1)=1, p)+expand(q*x1.j);
for i from 2 to N do q := p-select(has, p, {x.(i-1).j, x.i.(j-1)});
p := subs(x.i.(j-1)=1, p)+expand(q*x.i.j); od od; map(icontent, p) end:
|
|
CROSSREFS
|
Cf. A027683 for toroidal version.
Table of values for n x m matrices: A089934
Sequence in context: A132524 A153694 A100523 this_sequence A011821 A117263 A046855
Adjacent sequences: A006503 A006504 A006505 this_sequence A006507 A006508 A006509
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), R. H. Hardin, Paul.Zimmermann(AT)loria.fr
|
|
EXTENSIONS
|
Sequence extended by Paul Zimmermann Mar 15 1996.
|
|
|
Search completed in 0.002 seconds
|
