A067966 -id:A067966 - cp's OEIS frontend

A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles.

1, 1, 2, 5, 35, 314, 6427, 202841, 12727570, 1355115601, 269718819131, 94707789944544, 60711713670028729, 69645620389200894313, 144633664064386054815370, 540156683236043677756331721, 3641548665525780178990584908643, 44222017282082621251230960522832336

Offset: 0

Reiner Martin, Jul 23 2001

a(n) is also the number of ways to populate an n-1 X n-1 chessboard with nonattacking kings (including the case of zero kings). Cf. A193580. - Andrew Woods, Aug 27 2011

Also the number of vertex covers and independent vertex sets of the n-1 X n-1 king graph.

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 343

Andrew Woods and Vaclav Kotesovec and Johan Nilsson, Table of n, a(n) for n = 0..40 (terms 0..21 from Andrew Woods, terms 22..24 from Vaclav Kotesovec and terms 25..40 from Johan Nilsson)
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 68-69.
R. J. Mathar, Tiling n x m rectangles with 1 x 1 and s x s squares, arXiv:1609.03964 [math.CO], 2016, Section 4.1.
J. Nilsson, On Counting the Number of Tilings of a Rectangle with Squares of Size 1 and 2, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.2.
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A001045, A006506, A054854, A054855, A063650-A063653, A067966, etc.
Cf. A045846, A211348, A247413, A201513.
Cf. A212269, A067958.
a(n) = row sum n-1 of A193580.
Main diagonal of A245013.

Needs["LinearAlgebra`MatrixManipulation`"] Remove[mat] step[sa[rules1_, {dim1_, dim1_}], sa[rules2_, {dim2_, dim2_}]] := sa[Join[rules2, rules1 /. {x_Integer, y_Integer} -> {x + dim2, y}, rules1 /. {x_Integer, y_Integer} -> {x, y + dim2}], {dim1 + dim2, dim1 + dim2}] mat[0] = sa[{{1, 1} -> 1}, {1, 1}]; mat[1] = sa[{{1, 1} -> 1, {1, 2} -> 1, {2, 1} -> 1}, {2, 2}]; mat[n_] := mat[n] = step[mat[n - 2], mat[n - 1]]; A[n_] := mat[n] /. sa -> SparseArray; F[n_] := MatrixPower[A[n], n + 1][[1, 1]]; (* Mark McClure (mcmcclur(AT)bulldog.unca.edu), Mar 19 2006 *)
$RecursionLimit = 1000; Clear[a, b]; b[n_, l_List] := b[n, l] = Module[{m=Min[l], k}, If[m>0, b[n-m, l-m], If[n == 0, 1, k=Position[l, 0, 1, 1][[1, 1]]; b[n, ReplacePart[l, k -> 1]] + If[n>1 && k 2, k+1 -> 2}]], 0]]]]; a[n_] := a[n] = If[n<2, 1, b[n, Table[0, {n}]]]; Table[Print[a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Dec 11 2014, after Alois P. Heinz *)

Lim_{n -> infinity} (a(n))^(1/n^2) = A247413 = 1.342643951124... . - Brendan McKay, 1996

4 more terms from R. H. Hardin, Jan 23 2002
2 more terms from Keith Schneider (kschneid(AT)bulldog.unca.edu), Mar 19 2006
5 more terms from Andrew Woods, Aug 27 2011
a(22)-a(24) in b-file from Vaclav Kotesovec, May 01 2012
a(0) inserted by Alois P. Heinz, Sep 17 2014
a(25)-a(40) in b-file from Johan Nilsson, Mar 10 2016

A067961 Number of binary arrangements without adjacent 1's on n X n torus connected n-s.

Original entry on oeis.org

1, 9, 64, 2401, 161051, 34012224, 17249876309, 23811286661761, 84590643846578176, 792594609605189126649, 19381341794579313317802199, 1242425797286480951825250390016, 208396491430277954192889648311785961, 91534759488004239323168528670973468727049

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4:
| | | |
o o o o
| | | |
| | | |
o o o o
| | | |
| | | |
o o o o
| | | |
| | | |
o o o o
| | | |

Vincenzo Librandi, Table of n, a(n) for n = 1..69
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 409.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, e-w n-s A027683, e-w ne-sw n-s A066866.
Cf. A156216. - Paul D. Hanna, Sep 13 2010
Cf. A215941.

[Lucas(n)^n: n in [1..15]]; // Vincenzo Librandi, Mar 15 2014

a:= n-> (<<0|1>, <1|1>>^n. <<2, 1>>)[1$2]^n:
seq(a(n), n=1..15);  # Alois P. Heinz, Aug 01 2021

Table[LucasL[n]^n,{n,15}] (* Harvey P. Dale, Mar 13 2014 *)

a(n) = L(n)^n, where L(n) = A000032(n) is the n-th Lucas number.
Logarithmic derivative of A156216. - Paul D. Hanna, Sep 13 2010
Sum_{n>=1} 1/a(n) = A215941. - Amiram Eldar, Nov 17 2020

Edited by Dean Hickerson, Feb 15 2002

A067965 Number of binary arrangements without adjacent 1's on n X n array connected ne-sw and nw-se.

Original entry on oeis.org

2, 9, 119, 2704, 177073, 21836929, 6985036032, 4576976735769, 7263963336910751, 24830487842030082304, 198126078679714777857441, 3494153303407491549112098721, 141264727800378056245286463971328, 12779122891585386852029424628087941481, 2628141044813862018744988536642011269669959

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
. o..o..o..o
...\/ \/ \/
.../\ /\ /\
. o..o..o..o
...\/ \/ \/
.../\ /\ /\
. o..o..o..o
...\/ \/ \/
.../\ /\ /\
. o..o..o..o

Liang Kai, Table of n, a(n) for n = 1..27 (first 19 terms from Vaclav Kotesovec)
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69, 417.

Main diagonal of A181212.
Cf. circle A000204, line A000045, arrays: e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.
Cf. A201861, A212271.

Term a(14) from Vaclav Kotesovec, Dec 06 2011
Term a(15) from Vaclav Kotesovec, Jan 03 2012
Term a(16) from Vaclav Kotesovec, May 01 2012
Term a(17)-a(18) from Vaclav Kotesovec, Aug 13 2016

A067960 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw nw-se.

Original entry on oeis.org

1, 9, 34, 961, 25531, 2722500, 464483559, 224546142769, 215560806324388, 509113406167679889, 2590618817013278596997, 30737628149641669227004804, 809724336154415150287031740151, 48754690373355654118816600200711441

Offset: 1

R. H. Hardin, Feb 02 2002

If n is odd then A067960(n) = A027683(n).
a(18) = 2184710661251680812138610069332410066909052859790416601664. (a(17) = ?) - Vaclav Kotesovec, Sep 16 2014
a(20) = 61548416926224234005237372092957872593295040887178016957765412173582481. - Vaclav Kotesovec, May 18 2021

			Neighbors for n=4 (dots represent spaces):
.  \ /\ /\ /\ /
.   o..o..o..o
.  / \/ \/ \/ \
.  \ /\ /\ /\ /
.   o..o..o..o
.  / \/ \/ \/ \
.  \ /\ /\ /\ /
.   o..o..o..o
.  / \/ \/ \/ \
.  \ /\ /\ /\ /
.   o..o..o..o
.  / \/ \/ \/ \

Vaclav Kotesovec, Table of n, a(n) for n = 1..16
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 440.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Cf. A212271.

Terms a(12)-a(16) from Vaclav Kotesovec, May 18 2012

A067962 a(n) = F(n+2)*(Product_{i=1..n+1} F(i))^2 where F(i)=A000045(i) is the i-th Fibonacci number.

Original entry on oeis.org

1, 2, 12, 180, 7200, 748800, 204422400, 145957593600, 272940700032000, 1336044726656640000, 17122749216831498240000, 574502481723130428948480000, 50464872497041500009263431680000, 11605406728144633757130311383449600000

Offset: 0

R. H. Hardin, Feb 02 2002

Number of binary arrangements without adjacent 1's on n X n array connected nw-se.

Kitaev and Mansour give a general formula for the number of binary m X n matrices avoiding certain configurations.

			Neighbors for n=4 (dots represent spaces, circles represent grid points):
O..O..O..O
.\..\..\..
..\..\..\.
O..O..O..O
.\..\..\..
..\..\..\.
O..O..O..O
.\..\..\..
..\..\..\.
O..O..O..O

Reinhard Zumkeller, Table of n, a(n) for n = 0..68
Sergey Kitaev and Toufik Mansour, The problem of the pawns, arXiv:math/0305253 [math.CO], 2003; Annals of Combinatorics 8 (2004) 81-91.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69, 421.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Cf. A001654, A003266.

a067962 n = a067962_list !! n
a067962_list = 1 : zipWith (*) a067962_list (drop 2 a001654_list)
-- Reinhard Zumkeller, Sep 24 2015

a:= proc(n) option remember; `if`(n=0, 1, (F->
      F(n+1)*F(n+2)*a(n-1))(combinat[fibonacci]))
    end:
seq(a(n), n=0..14);  # Alois P. Heinz, May 20 2019

Rest[Table[With[{c=Fibonacci[Range[n]]},(Times@@Most[c])^2 Last[c]],{n,15}]] (* Harvey P. Dale, Dec 17 2013 *)

a(n)=fibonacci(n+2)*prod(i=0,n,fibonacci(i+1))^2

a(n) = (F(3) * F(4) * ... * F(n+1))^2 * F(n+2), where F(n) = A000045(n) is the n-th Fibonacci number.
a(n) is asymptotic to C^2*((1+sqrt(5))/2)^((n+2)^2)/(5^(n+3/2)) where C=1.226742010720353244... is the Fibonacci Factorial Constant, see A062073. - Vaclav Kotesovec, Oct 28 2011
a(n) = a(n-1) * A001654(n+1), n > 0. - Reinhard Zumkeller, Sep 24 2015

Edited by Dean Hickerson, Feb 15 2002

Revised by N. J. A. Sloane following comments from Benoit Cloitre, Nov 12 2003

A067958 Number of binary arrangements without adjacent 1's on n X n torus connected e-w ne-sw n-s nw-se.

Original entry on oeis.org

1, 5, 10, 133, 1411, 42938, 1796859, 157763829, 22909432780, 6291183426165, 3032485231813445, 2674030233698391466, 4216437656471537450175, 12038380931111061789962901, 61810608197507432888286102310, 572863067272579464080483552434421

Offset: 1

R. H. Hardin, Feb 02 2002

For n > 1, a(n) is also the number of ways to populate an n X n toroidal chessboard with non-attacking kings (including the case of zero kings). - Vaclav Kotesovec, Oct 10 2011

			Neighbors for n=4:
  :\|/\|/\|/\|/
  :-o--o--o--o-
  :/|\/|\/|\/|\
  :\|/\|/\|/\|/
  :-o--o--o--o-
  :/|\/|\/|\/|\
  :\|/\|/\|/\|/
  :-o--o--o--o-
  :/|\/|\/|\/|\
  :\|/\|/\|/\|/
  :-o--o--o--o-
  :/|\/|\/|\/|\

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 214.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Cf. A212269.

a(14) from Vaclav Kotesovec, Aug 22 2016

a(15)-a(16) from Vaclav Kotesovec, May 15 2021

A067963 Number of binary arrangements without adjacent 1's on n X n array connected e-w ne-sw nw-se.

Original entry on oeis.org

2, 7, 77, 1152, 56549, 3837761, 806190208, 251170142257, 223733272186825, 319544298135448960, 1210302996752248488817, 7876274672755293629849313, 127662922218147601317696761088, 3758866349549535184419575245899295

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
. o--o--o--o
...\/ \/ \/
.../\ /\ /\
. o--o--o--o
...\/ \/ \/
.../\ /\ /\
. o--o--o--o
...\/ \/ \/
.../\ /\ /\
. o--o--o--o

R. H. Hardin and Vaclav Kotesovec, Table of n, a(n) for n = 1..30
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-71.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Diagonal of A228683

Terms a(15)-a(19) from Vaclav Kotesovec, May 01 2012

A067964 Number of binary arrangements without adjacent 1's on n X n array connected n-s nw-se.

Original entry on oeis.org

2, 8, 90, 1876, 103484, 11462588, 3118943536, 1808994829500, 2465526600093372, 7394315828592829424, 50975951518289853305508, 784977037926751747674903856, 27509351187362150581313065415008, 2167705218542258344490649896364635660, 387057670485382113845659790427906287869964

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o
. |\ |\ |\ |
. | \| \| \|
. o..o..o..o

Vaclav Kotesovec, Table of n, a(n) for n = 1..21
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-71.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

Limit n->infinity (a(n))^(1/n^2) = 1.503048082... (see A085850)

Terms a(14)-a(18) from Vaclav Kotesovec, May 01 2012

A067959 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw n-s nw-se.

Original entry on oeis.org

1, 7, 22, 547, 9021, 812830, 70046159, 24082448515, 10363980496342, 14228018243052057, 29400555005986658803, 166705587265151114516638, 1606507128309318588452521527, 38505096862341023166325442747581, 1696028983502674228038462924646464012

Offset: 1

R. H. Hardin, Feb 02 2002

			Neighbors for n=4 (dots represent spaces):
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\
.\|/\|/\|/\|/
. o..o..o..o
./|\/|\/|\/|\

Sean A. Irvine, Table of n, a(n) for n = 1..17
V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 73.

Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, nw-se A067962, toruses: bare A002416, ne-sw nw-se A067960, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.

a(13) from Vaclav Kotesovec, Aug 22 2016
a(14) from Vaclav Kotesovec, May 24 2021
a(15) from Sean A. Irvine, Jan 14 2024

A210341 Triangle generated by T(n,k) = Fibonacci(n-k+2)^k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 5, 9, 8, 1, 1, 8, 25, 27, 16, 1, 1, 13, 64, 125, 81, 32, 1, 1, 21, 169, 512, 625, 243, 64, 1, 1, 34, 441, 2197, 4096, 3125, 729, 128, 1, 1, 55, 1156, 9261, 28561, 32768, 15625, 2187, 256, 1, 1, 89, 3025, 39304, 194481, 371293

Offset: 0

Emanuele Munarini, Mar 20 2012

Number of tilings of an nXk chessboard using monomers and dimers of a fixed orientation. This is easy to see because the board here consists of k independent strips of length n. - Ralf Stephan, May 22 2014
Row sums = A210342
Central coefficients = A067966.
This triangle is related to the infinite Vandermonde matrix
V = [F(i+2)^j]_(i,j>=0) generated by Fibonacci numbers:
  1, 1,  1,   1,    1,      1,       1
  1, 2,  4,   8,    16,     32,      64
  1, 3,  9,   27,   81,     243,     729
  1, 5,  25,  125,  625,    3125,    15625
  1, 8,  64,  512,  4096,   32768,   262144
  1, 13, 169, 2197, 28561,  371293,  4826809
 1, 21, 441, 9261, 194481, 4084101, 85766121
The generating series of the columns can be expressed in terms of Fibonomial coefficients (A010048) (see Riordan's paper).

			Triangle begins:
  1
  1,  1
  1,  2,   1
  1,  3,   4,    1
  1,  5,   9,    8,    1
  1,  8,  25,   27,   16,    1
  1, 13,  64,  125,   81,   32,   1
  1, 21, 169,  512,  625,  243,  64,   1
  1, 34, 441, 2197, 4096, 3125, 729, 128, 1

Vincenzo Librandi, Rows n = 0..90, flattened
J. Riordan, Generating functions for powers of Fibonacci numbers, Duke. Math. J. 29 (1962) 5-12.

Cf. A103323, A067966, A210342, A210343.

[Fibonacci(n-k+2)^k: k in [0..n], n in [0..10]]; /* Alternatively: */ [[Fibonacci(n-k+2)^k: k in [0..n]]: n in [0..8]]; // Bruno Berselli, Mar 28 2012

Flatten[Table[Fibonacci[n-k+2]^k,{n,0,20},{k,0,n}]]

create_list(fib(n-k+2)^k,n,0,20,k,0,n);

G.f.: Sum_{k>=0} x^k/(1-Fibonacci(k+2)*x*y).

cp's OEIS Frontend

A063443 Number of ways to tile an n X n square with 1 X 1 and 2 X 2 tiles.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A067961 Number of binary arrangements without adjacent 1's on n X n torus connected n-s.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A067965 Number of binary arrangements without adjacent 1's on n X n array connected ne-sw and nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A067960 Number of binary arrangements without adjacent 1's on n X n torus connected ne-sw nw-se.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A067962 a(n) = F(n+2)*(Product_{i=1..n+1} F(i))^2 where F(i)=A000045(i) is the i-th Fibonacci number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A067958 Number of binary arrangements without adjacent 1's on n X n torus connected e-w ne-sw n-s nw-se.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A067963 Number of binary arrangements without adjacent 1's on n X n array connected e-w ne-sw nw-se.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A067964 Number of binary arrangements without adjacent 1's on n X n array connected n-s nw-se.

Views

Author

Keywords

Examples