cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A006506 Number of n X n binary matrices with no 2 adjacent 1's, or number of 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 vertex sets in an n X n grid.

Original entry on oeis.org

1, 2, 7, 63, 1234, 55447, 5598861, 1280128950, 660647962955, 770548397261707, 2030049051145980050, 12083401651433651945979, 162481813349792588536582997, 4935961285224791538367780371090, 338752110195939290445247645371206783, 52521741712869136440040654451875316861275
Offset: 0

Views

Author

N. J. A. Sloane, R. H. Hardin, Paul Zimmermann

Keywords

Comments

A two-dimensional generalization of the Fibonacci numbers.
Also the number of vertex covers in the n X n grid graph P_n X P_n.
A181030 (Number of n X n binary matrices with no leading bitstring in any row or column divisible by 4) is the same sequence. Proof from Steve Butler, Jan 26 2015: This is trivially true. A181030 is equivalent to this sequence by interchanging the roles of 0 and 1. In particular, A181030 looks for binary matrices with no leading bitstring divisible by 4, but a bitstring is divisible by 4 if and only if its last two digits is 0; in a binary matrix this can only be avoided if there are no two adjacent 0's (i.e., for any two adjacent 0's take the bitstring starting in that row or column and we are done); the present sequence looks for no two adjacent 1's. Similar reasons show that the array A181031 is equivalent to the array A089980.
Let R(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y| <= n+1, and let S(n) be the set of squares that have vertices at integer coordinates and lie in the region of the plane |x|+|y-1/2| <= n+2. Further let T be the collection of rectangular tiles with dimensions i X 1 or 1 X i with i arbitrary. Then a(2n) is the number of ways to tile R(n) using tiles from T and a(2n+1) is the number of ways to tile S(n) using tiles from T. (Note R(n) is the Aztec diamond of order n.) - Steve Butler, Jan 26 2015

References

  • Steven 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).

Links

Crossrefs

Cf. A027683 for toroidal version.
Table of values for n x m matrices: A089934.
Cf. A232833 for refinement by number of 1's.
Cf. also A191779.
Cf. A201511, A212270.

Programs

  • Maple
    A006506 := proc(N) local i,j,p,q; p := 1+x11;
if n=0 then return 1 fi;
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:
seq(A006506(n), n=0..15);
  • 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] (* Jean-François Alcover, May 25 2011, after Maple prog. *)
Table[With[{g = GridGraph[{n, n}]}, Count[Subsets[Range[n^2], Length @ First @ FindIndependentVertexSet[g]], ?(IndependentVertexSetQ[g, #] &)]], {n, 5}] (* _Eric W. Weisstein, May 28 2017 *)
  • 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); sum(i=1,L,v[i]) \\ Robert Gerbicz, Jun 17 2011

Formula

Limit_{n->oo} 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
From n up to 39 we have A = 1.06608266035... - Vaclav Kotesovec, Jan 29 2024

Extensions

Sequence extended by Paul Zimmermann, Mar 15 1996
Maple program updated and sequence extended by Robert Israel, Jun 16 2011
a(0)=1 prepended by Alois P. Heinz, Jan 29 2024

A027683 Number of independent vertex sets of the n X n torus grid graph.

Original entry on oeis.org

1, 7, 34, 743, 25531, 2406862, 464483559, 213256442503, 215560806324388, 498819827260367617, 2590618817013278596997, 30496896080418683388380966, 809724336154415150287031740151, 48609694845429192825410114233405807, 6589876632329358971395398453738256596574, 2018670118781080042934952855192359574137313799
Offset: 1

Views

Author

R. H. Hardin

Keywords

Links

Crossrefs

Cf. A006506 for flat version.
Cf. A067960, A201626, A212270.

Programs

  • Mathematica
    a[n_] := With[{sets = Select[Tuples[{0, 1}, n], Count[#*RotateLeft[#], 1] == 0 &]}, Tr[MatrixPower[Table[Boole[Count[s1*s2, 1] == 0], {s1, sets}, {s2, sets}], n]]];
Table[a[n], {n, 1, 10}] (* Pjotr Buys, Jun 07 2023 *)

Extensions

Terms a(14)-a(16) from Vaclav Kotesovec, Dec 02 2011

A286513 Array read by antidiagonals: T(m,n) is the number of independent sets in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 1, 3, 1, 7, 4, 1, 17, 13, 7, 1, 41, 43, 35, 11, 1, 99, 142, 181, 81, 18, 1, 239, 469, 933, 621, 199, 29, 1, 577, 1549, 4811, 4741, 2309, 477, 47, 1, 1393, 5116, 24807, 36211, 26660, 8303, 1155, 76, 1, 3363, 16897, 127913, 276561, 307983, 143697, 30277, 2785, 123
Offset: 1

Views

Author

Andrew Howroyd, May 10 2017

Keywords

Comments

Equivalently, the number of vertex covers in the stacked prism graph C_m X P_n.

Examples

			Table starts:
=============================================================
m\n|   1    2     3      4        5         6           7
---|---------------------------------------------------------
1  |   1    1     1      1        1         1           1 ...
2  |   3    7    17     41       99       239         577 ...
3  |   4   13    43    142      469      1549        5116 ...
4  |   7   35   181    933     4811     24807      127913 ...
5  |  11   81   621   4741    36211    276561     2112241 ...
6  |  18  199  2309  26660   307983   3557711    41097664 ...
7  |  29  477  8303 143697  2488431  43089985   746156517 ...
8  |  47 1155 30277 788453 20546803 535404487 13951571713 ...
...

Links

Crossrefs

Rows 3..8 are A003688(n+1), A051926, A181989, A181961, A182014, A182019.
Columns 1..4 are A000032, A051927, A050400, A050401.
Main diagonal is A212270.
Cf. A089934 (P_m X P_n), A027683, A286514.

A212271 Number of ways to place k non-attacking ferses on an n x n cylindrical chessboard, summed over all k >= 0.

Original entry on oeis.org

2, 9, 80, 1600, 79033, 8156736, 2055960192, 1108756350625, 1411080429618656, 3943472747846953216, 25425527581172360096017, 365481944233773616212640000, 11980566143208960475692367828480, 882106482533191605447029340350009049, 147314997388032765439791110273770608260928
Offset: 1

Views

Author

Vaclav Kotesovec, May 12 2012

Keywords

Comments

Fers is a leaper [1,1].

Links

Crossrefs

Cf. A067965, A067960, A182407, A212269, A212270.

Formula

Limit n ->infinity (a(n))^(1/n^2) is the hard square entropy constant A085850.
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.