|
| |
|
|
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 an n X n grid.
(Formerly M1816)
|
|
28
| |
|
|
2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783, 52521741712869136440040654451875316861275
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,1
|
|
|
COMMENTS
| A two-dimensional generalization of the Fibonacci numbers.
|
|
|
REFERENCES
| S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 342-349.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
B. D. Stosic, T. Stosic, I. P. Fittipaldi and J. J. P. Veerman, Residual entropy of the square Ising antiferromagnet in the maximum critical field: the Fibonacci matrix, Journal of Physics A: Mathematical and General, Volume 30, Number 10, 1997, pp. L331-L337.
|
|
|
LINKS
| Robert Gerbicz, Table of n, a(n) for n = 1..33
S. R. Finch, Hard Square Entropy Constant
Peter Tittmann, Enumeration in Graphs
Eric Weisstein's World of Mathematics, (0,1)-Matrix
Eric Weisstein's World of Mathematics, Hard Square Entropy Constant
Index entries for sequences related to binary matrices
|
|
|
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:
|
|
|
MATHEMATICA
| a[n_] := a[n] = (p = 1 + x[1, 1];
Do[q = p - Select[p, ! FreeQ[#, x[i-1, 1]] &];
p = p + Expand[q*x[i, 1]], {i, 2, n}];
Do[q = p - Select[p, ! FreeQ[#, x[1, j-1]] &];
p = (p /. x[i, j-1] :> 1) + Expand[q*x[1, j]];
Do[q = p - Select[ p, ! FreeQ[#, x[i-1, j]] || ! FreeQ[#, x[i, j-1]] &];
p = (p /. x[i, j-1] :> 1) + Expand[q*x[i, j]], {i, 2, n}], {j, 2, n}]; p /. x[_, _] -> 1);
a /@ Range[14]
(* From Jean-François Alcover, May 25 2011, after Maple prog. *)
|
|
|
PROG
| (PARI) a(n)=L=fibonacci(n+2); p=v=vector(L, i, 1); c=0;
for(i=0, 2^n-1, j=i; while(j&&j%4<3, j\=2); if(j%4<3, p[c++]=i));
for(i=2, n, w=vector(L, j, 0);
for(j=1, L, for(k=1, L, if(bitand(p[j], p[k])==0, w[j]+=v[k]))); v=w);
return(sum(i=1, L, v[i])) (From Robert Gerbicz, Jun 17 2011)
|
|
|
CROSSREFS
| Cf. A027683 for toroidal version.
Table of values for n x m matrices: A089934.
Cf. also A191779.
Sequence in context: A153694 A100523 A181030 * A011821 A117263 A046855
Adjacent sequences: A006503 A006504 A006505 * 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
Maple program updated and sequence extended by Robert Israel (israel(AT)math.ubc.ca), Jun 16 2011
|
| |
|
|
