A030978 -id:A030978 - cp's OEIS frontend

A244081 Number T(n,k) of ways to place k nonattacking knights on an n X n board; triangle T(n,k), n>=0, 0<=k<=A030978(n), read by rows.

1, 1, 1, 1, 4, 6, 4, 1, 1, 9, 28, 36, 18, 2, 1, 16, 96, 276, 412, 340, 170, 48, 6, 1, 25, 252, 1360, 4436, 9386, 13384, 12996, 8526, 3679, 994, 158, 15, 1, 1, 36, 550, 4752, 26133, 97580, 257318, 491140, 688946, 716804, 556274, 323476, 141969, 47684, 12488, 2560, 393, 40, 2

Offset: 0

Alois P. Heinz, Jun 19 2014

In other words, the n-th row gives the coefficients of the independence polynomial of the n X n knight graph. - Eric W. Weisstein, May 05 2017

			T(4,8) = 6:
  ._______. ._______. ._______. ._______. ._______. ._______.
  |_|o|_|o| |o|_|o|_| |o|o|o|o| |o|_|_|o| |o|_|o|o| |o|o|_|o|
  |o|_|o|_| |_|o|_|o| |_|_|_|_| |o|_|_|o| |_|_|_|o| |o|_|_|_|
  |_|o|_|o| |o|_|o|_| |_|_|_|_| |o|_|_|o| |o|_|_|_| |_|_|_|o|
  |o|_|o|_| |_|o|_|o| |o|o|o|o| |o|_|_|o| |o|o|_|o| |o|_|o|o| .
.
Triangle T(n,k) begins:
  1;
  1,  1;
  1,  4,   6,    4,    1;
  1,  9,  28,   36,   18,    2;
  1, 16,  96,  276,  412,  340,   170,    48,    6;
  1, 25, 252, 1360, 4436, 9386, 13384, 12996, 8526, 3679, 994, 158, 15, 1;
  ...
As independence polynomials:
  1
  1 + x
  1 + 4*x + 6*x^2 + 4*x^3 + x^4
  1 + 9*x + 28*x^2 + 36*x^3 + 18*x^4 + 2*x^5
  1 + 16*x + 96*x^2 + 276*x^3 + 412*x^4 + 340*x^5 + 170*x^6 + 48*x^7 + 6*x^8
  ...

Alois P. Heinz, Rows n = 0..12, flattened
Eric Weisstein's World of Mathematics, Independence Polynomial
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Knights Problem

Columns k=0-6 give: A000012, A000290, A172132, A172134, A172135, A172136, A178499.
T(n,n) gives A201540.
Row sums give A141243.
Cf. A030978.

b:= proc(n, l) option remember; local d, f, g, k;
      d:= nops(l)/3; f:=false;
      if n=0 then 1
    elif l[1..d]=[f$d] then b(n-1, [l[d+1..3*d][], true$d])
    else for k while not l[k] do od; g:= subsop(k=f, l);
         if k>1 then g:=subsop(2*d-1+k=f, g) fi;
         if k2 then g:=subsop(  d-2+k=f, g) fi;
         if k(p->seq(coeff(p, x, i), i=0..degree(p)))(b(n, [true$(n*3)])):
seq(T(n), n=0..7);

b[n_, l_] := b[n, l] = Module[{d, f, g, k}, d = Length[l]/3; f = False; Which[n == 0, 1, l[[1 ;; d]] == Array[f&, d], b[n - 1, Join[l[[d + 1 ;; 3*d]], Array[True&, d]]], True, For[k = 1, !l[[k]], k++]; g = ReplacePart[l, k -> f];
     If [k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
     If [k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
     If [k > 2, g = ReplacePart[ g, d - 2 + k -> f]];
     If [k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
     Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][
  b[n, Array[True&, n*3]]];
Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Mar 28 2016, after Alois P. Heinz *)
Table[Count[IndependentVertexSetQ[KnightTourGraph[n, n], #] & /@ Subsets[Range[n^2], {k}], True], {n, 4}, {k, 0, If[n == 2, 4, (1 - (-1)^n + 2 n^2)/4]}] // Flatten (* Eric W. Weisstein, May 05 2017 *)

A005843 The nonnegative even numbers: a(n) = 2n.

Original entry on oeis.org

0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120

Offset: 0

N. J. A. Sloane

-2, -4, -6, -8, -10, -12, -14, ... are the trivial zeros of the Riemann zeta function. - Vivek Suri (vsuri(AT)jhu.edu), Jan 24 2008
If a 2-set Y and an (n-2)-set Z are disjoint subsets of an n-set X then a(n-2) is the number of 2-subsets of X intersecting both Y and Z. - Milan Janjic, Sep 19 2007
A134452(a(n)) = 0; A134451(a(n)) = 2 for n > 0. - Reinhard Zumkeller, Oct 27 2007
Omitting the initial zero gives the number of prime divisors with multiplicity of product of terms of n-th row of A077553. - Ray Chandler, Aug 21 2003
A059841(a(n))=1, A000035(a(n))=0. - Reinhard Zumkeller, Sep 29 2008
(APSO) Alternating partial sums of (a-b+c-d+e-f+g...) = (a+b+c+d+e+f+g...) - 2*(b+d+f...), it appears that APSO(A005843) = A052928 = A002378 - 2*(A116471), with A116471=2*A008794. - Eric Desbiaux, Oct 28 2008
A056753(a(n)) = 1. - Reinhard Zumkeller, Aug 23 2009
Twice the nonnegative numbers. - Juri-Stepan Gerasimov, Dec 12 2009
The number of hydrogen atoms in straight-chain (C(n)H(2n+2)), branched (C(n)H(2n+2), n > 3), and cyclic, n-carbon alkanes (C(n)H(2n), n > 2). - Paul Muljadi, Feb 18 2010
For n >= 1; a(n) = the smallest numbers m with the number of steps n of iterations of {r - (smallest prime divisor of r)} needed to reach 0 starting at r = m. See A175126 and A175127. A175126(a(n)) = A175126(A175127(n)) = n. Example (a(4)=8): 8-2=6, 6-2=4, 4-2=2, 2-2=0; iterations has 4 steps and number 8 is the smallest number with such result. - Jaroslav Krizek, Feb 15 2010
For n >= 1, a(n) = numbers k such that arithmetic mean of the first k positive integers is not integer. A040001(a(n)) > 1. See A145051 and A040001. - Jaroslav Krizek, May 28 2010
Union of A179082 and A179083. - Reinhard Zumkeller, Jun 28 2010
a(k) is the (Moore lower bound on and the) order of the (k,4)-cage: the smallest k-regular graph having girth four: the complete bipartite graph with k vertices in each part. - Jason Kimberley, Oct 30 2011
For n > 0: A048272(a(n)) <= 0. - Reinhard Zumkeller, Jan 21 2012
Let n be the number of pancakes that have to be divided equally between n+1 children. a(n) is the minimal number of radial cuts needed to accomplish the task. - Ivan N. Ianakiev, Sep 18 2013
For n > 0, a(n) is the largest number k such that (k!-n)/(k-n) is an integer. - Derek Orr, Jul 02 2014
a(n) when n > 2 is also the number of permutations simultaneously avoiding 213, 231 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl Aug 07 2014
It appears that for n > 2, a(n) = A020482(n) + A002373(n), where all sequences are infinite. This is consistent with Goldbach's conjecture, which states that every even number > 2 can be expressed as the sum of two prime numbers. - Bob Selcoe, Mar 08 2015
Number of partitions of 4n into exactly 2 parts. - Colin Barker, Mar 23 2015
Number of neighbors in von Neumann neighborhood. - Dmitry Zaitsev, Nov 30 2015
Unique solution b( ) of the complementary equation a(n) = a(n-1)^2 - a(n-2)*b(n-1), where a(0) = 1, a(1) = 3, and a( ) and b( ) are increasing complementary sequences. - Clark Kimberling, Nov 21 2017
Also the maximum number of non-attacking bishops on an (n+1) X (n+1) board (n>0). (Cf. A000027 for rooks and queens (n>3), A008794 for kings or A030978 for knights.) - Martin Renner, Jan 26 2020
Integer k is even positive iff phi(2k) > phi(k), where phi is Euler's totient (A000010) [see reference De Koninck & Mercier]. - Bernard Schott, Dec 10 2020
Number of 3-permutations of n elements avoiding the patterns 132, 213, 312 and also number of 3-permutations avoiding the patterns 213, 231, 321. See Bonichon and Sun. - Michel Marcus, Aug 20 2022
a(n) gives the y-value of the integral solution (x,y) of the Pellian equation x^2 - (n^2 + 1)*y^2 = 1. The x-value is given by 2*n^2 + 1 (see Tattersall). - Stefano Spezia, Jul 24 2025

			G.f. = 2*x + 4*x^2 + 6*x^3 + 8*x^4 + 10*x^5 + 12*x^6 + 14*x^7 + 16*x^8 + ...

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 2.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 28.
J.-M. De Koninck and A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 529a pp. 71 and 257, Ellipses, 2004, Paris.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 256.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
David Callan, On Ascent, Repetition and Descent Sequences, arXiv:1911.02209 [math.CO], 2019.
Charles Cratty, Samuel Erickson, Frehiwet Negass, and Lara Pudwell, Pattern Avoidance in Double Lists, preprint, 2015.
Kevin Fagan, Drabble cartoon, Jun 15 1987: Intelligence Test
Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012, J. Int. Seq. 15 (2012) # 12.6.2
Milan Janjic, Two Enumerative Functions
Tanya Khovanova, Recursive Sequences
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Even Number
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Riemann Zeta Function Zeros
Wikipedia, Alkane
Index entries for "core" sequences
Index entries for linear recurrences with constant coefficients, signature (2,-1).

a(n)=2*A001477(n). - Juri-Stepan Gerasimov, Dec 12 2009
Cf. A000027, A002061, A005408, A001358, A077553, A077554, A077555, A002024, A087112, A157888, A157889, A140811, A157872, A157909, A157910, A165900.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), this sequence (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A231200 (boustrophedon transform).

a005843 = (* 2)
a005843_list = [0, 2 ..]  -- Reinhard Zumkeller, Feb 11 2012

Magma
```
[ 2*n : n in [0..100]];
```

A005843 := n->2*n;
A005843:=2/(z-1)**2; # Simon Plouffe in his 1992 dissertation

Range[0,120,2] (* Harvey P. Dale, Aug 16 2011 *)

PARI
```
A005843(n) = 2*n
```

def a(n): return 2*n # Martin Gergov, Oct 20 2022

R
```
seq(0,200,2)
```

G.f.: 2*x/(1-x)^2.
E.g.f.: 2*x*exp(x). - Geoffrey Critzer, Aug 25 2012
G.f. with interpolated zeros: 2x^2/((1-x)^2 * (1+x)^2); e.g.f. with interpolated zeros: x*sinh(x). - Geoffrey Critzer, Aug 25 2012
Inverse binomial transform of A036289, n*2^n. - Joshua Zucker, Jan 13 2006
a(0) = 0, a(1) = 2, a(n) = 2a(n-1) - a(n-2). - Jaume Oliver Lafont, May 07 2008
a(n) = Sum_{k=1..n} floor(6n/4^k + 1/2). - Vladimir Shevelev, Jun 04 2009
a(n) = A034856(n+1) - A000124(n) = A000217(n) + A005408(n) - A000124(n) = A005408(n) - 1. - Jaroslav Krizek, Sep 05 2009
a(n) = Sum_{k>=0} A030308(n,k)*A000079(k+1). - Philippe Deléham, Oct 17 2011
Digit sequence 22 read in base n-1. - Jason Kimberley, Oct 30 2011
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - Vincenzo Librandi, Dec 23 2011
a(n) = 2*n = Product_{k=1..2*n-1} 2*sin(Pi*k/(2*n)), n >= 0 (undefined product := 1). See an Oct 09 2013 formula contribution in A000027 with a reference. - Wolfdieter Lang, Oct 10 2013
From Ilya Gutkovskiy, Aug 19 2016: (Start)
Convolution of A007395 and A057427.
Sum_{n>=1} (-1)^(n+1)/a(n) = log(2)/2 = (1/2)*A002162 = (1/10)*A016655. (End)
From Bernard Schott, Dec 10 2020: (Start)
Sum_{n>=1} 1/a(n)^2 = Pi^2/24 = A222171.
Sum_{n>=1} (-1)^(n+1)/a(n)^2 = Pi^2/48 = A245058. (End)

A008794 Squares repeated; a(n) = floor(n/2)^2.

Original entry on oeis.org

0, 0, 1, 1, 4, 4, 9, 9, 16, 16, 25, 25, 36, 36, 49, 49, 64, 64, 81, 81, 100, 100, 121, 121, 144, 144, 169, 169, 196, 196, 225, 225, 256, 256, 289, 289, 324, 324, 361, 361, 400, 400, 441, 441, 484, 484, 529, 529, 576, 576

Offset: 0

N. J. A. Sloane

Also number of non-attacking kings on (n-1) X (n-1) board (cf. A030978). - Koksal Karakus (karakusk(AT)hotmail.com), May 27 2002
Also the independence number and clique covering number of the (n-1) X (n-1) king graph. - Eric W. Weisstein, Jun 20 2017
Maximum number of 2 X 2 tiles that fit on an n X n board. - Jon Perry, Aug 10 2003
(n)-(1) + (n-1)-(2) + (n-3)-(3) + ... + (n-r)-(r) ... n terms. E.g., 5-1+4-2+3 = 9, 6-1+5-2+4-3 = 9, 7-1+6-2+5-3+4 = 16, 8-1+7-2+6-3+5-4 = 16. - Amarnath Murthy, Jul 24 2005
The smallest possible number of white cells in a solution to an n X n nurikabe grid. - Tanya Khovanova, Feb 24 2009
(1 + x + 4*x^2 + 4*x^3 + 9*x^4 + ...) = (1/(1-x))*(1 + 3*x^2 + 5*x^4 + 7*x^6 + ...). - Gary W. Adamson, Apr 07 2010
If the set {1,2,...,n} is divided in half (a part having size ceiling(n/2) and the rest), then a(n+1) is the largest possible difference between the totals of these parts. - Vladimir Shevelev, Oct 14 2017
a(n+1) is the sum of the smallest parts of the partitions of 2n into two odd parts. - Wesley Ivan Hurt, Dec 06 2017
a(n-1) is the largest number of single cells of an n X n grid that share no edge or vertex with each other or those of the grid perimeter. - Stefano Spezia, Jul 30 2021
The binomial transform is 0, 0, 1, 4, 14, 44, 128, 352, 928, 2368, 5888... (see A007466).  - R. J. Mathar, Feb 25 2023

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Stefano Spezia, Illustration of initial terms
Eric Weisstein's World of Mathematics, Clique Covering Number.
Eric Weisstein's World of Mathematics, King Graph.
Eric Weisstein's World of Mathematics, Kings Problem.
Index entries for sequences related to partitions
Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Cf. A030978, A032766, A059841, A086832, A109613, A182579, A189889.

Flat(List([0..24],n->[n^2,n^2])); # Muniru A Asiru, Oct 09 2018

[(2*n-1)*(-1)^n/8+(2*n^2-2*n +1)/8: n in [0..60]]; // Vincenzo Librandi, Aug 21 2011

A008794:=n->floor(n/2)^2: seq(A008794(n), n=0..50); # Wesley Ivan Hurt, Dec 08 2017

With[{sq = Range[0, 30]^2}, Riffle[sq, sq]] (* Harvey P. Dale, Nov 20 2015 *)
Table[Floor[n/2]^2, {n, 0, 49}] (* Michael De Vlieger, Oct 21 2016 *)
Table[(2 n - 1) (-1)^n/8 + (2 n^2 - 2 n + 1)/8, {n, 0, 49}] (* Michael De Vlieger, Oct 21 2016 *)
CoefficientList[Series[x^2*(1 + x^2)/((1 - x) (1 - x^2)^2), {x, 0, 49}], x] (* Michael De Vlieger, Oct 21 2016 *)
CoefficientList[Series[((x^2-x)Cosh[x]+(1+x+x^2)Sinh[x])/4,{x,0,50}],x]*Table[k!,{k,0,50}] (* Stefano Spezia, Oct 07 2018 *)

a(n)=(n\2)^2 \\ Charles R Greathouse IV, Sep 24 2015

first(n) = Vec(x^2*(1 + x^2)/((1 - x)*(1 - x^2)^2) + O(x^n), -n) \\ Iain Fox, Dec 08 2017

def A008794(n): return (n//2)**2 # Chai Wah Wu, Jun 07 2022

[((-1)^n*(2*n-1) +(2*n^2-2*n +1))/8 for n in (0..50)] # G. C. Greubel, Sep 11 2019

G.f.: x^2*(1 + x^2)/((1 - x)*(1 - x^2)^2).
a(n) = floor(n/2)^2.
From Paul Barry, May 31 2003: (Start)
a(n) = (2*n - 1)*(-1)^n/8 + (2*n^2 - 2*n + 1)/8.
a(n+1) = Sum_{k=0..n} k*(1-(-1)^k)/2. (End)
a(n+2) = Sum_{k=0..n} A109613(k)*A059841(n-k). - Reinhard Zumkeller, Dec 05 2009
a(n) = A182579(n,n-2) for n > 1. - Reinhard Zumkeller, May 07 2012
3*a(n) = A032766(n)^2 - A032766(n^2). - Bruno Berselli, Oct 21 2016
a(n) = Sum_{i=1..n-1; i odd} i. - Olivier Pirson, Nov 06 2017
a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) - a(n-4) + a(n-5), n > 4. - Iain Fox, Dec 08 2017
E.g.f.: ((x^2 - x)*cosh(x) + (1 + x + x^2)*sinh(x))/4. - Stefano Spezia, Oct 07 2018

A004277 1 together with positive even numbers.

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120, 122, 124, 126, 128, 130, 132

Offset: 0

N. J. A. Sloane

Also number of non-attacking bishops on n X n board. - Koksal Karakus (karakusk(AT)hotmail.com), May 27 2002
Engel expansion of e^(1/2) (see A006784 for definition) [when offset by 1]. - Henry Bottomley, Dec 18 2000
Numbers n such that a 2n-group (i.e., a group of order 2n) has subgroup C_2. - Lekraj Beedassy, Oct 14 2004
Image of 1/(1-2x) under the mapping g(x)->g(x/(1+x^2)). - Paul Barry, Jan 16 2005
Position of n in A113322: A113322(a(n-1)) = n for n>0. - Reinhard Zumkeller, Oct 26 2005
Incrementally largest terms in the continued fraction for e. - Nick Hobson, Jan 11 2007
Conjecturally, the differences of two consecutive primes (without repetition). - Juri-Stepan Gerasimov, Nov 09 2009
Equals (1, 2, 2, 2, ...) convolved with (1, 0, 2, 0, 2, 0, 2, ...). - Gary W. Adamson, Mar 03 2010
a(n) is the number of 0-dimensional elements (vertices) in an n-cross polytope. - Patrick J. McNab, Jul 06 2015
Numbers k such that in the symmetric representation of sigma(k) there is no pair bars as its ends (Cf. A237593). - Omar E. Pol, Sep 28 2018
Also, the coordination sequence of the L-lattice (see A332419). - Sean A. Irvine, Jul 29 2020

E. Friedman, Math. Magic
Eric Weisstein's World of Mathematics, Cross Polytope
Index entries for sequences related to Engel expansions
Index entries for linear recurrences with constant coefficients, signature (2, -1).

Cf. A004275, A008486, A030978, A097134.

INVERT transformation yields A098182 without A098182(0). - R. J. Mathar, Sep 11 2008

a004277 n = 2 * n - 1 + signum (1 - n)
a004277_list = 1 : [2, 4 ..]  -- Reinhard Zumkeller, Dec 19 2013

[1] cat [2*n: n in [1..80]]; // Vincenzo Librandi, Jul 11 2015

Join[{1}, Table[2*n, {n, 200}]] (* Vladimir Joseph Stephan Orlovsky, Jul 10 2011 *)
Select[Range@ 105, PowerMod[#, #, # + 1] == 1 &] (* Robert G. Wilson v, Sep 26 2016 *)

G.f.: (1+x^2)/(1-x)^2. - Paul Barry, Feb 28 2003
Inverse binomial transform of Cullen numbers A002064. a(n)=2n+0^n. - Paul Barry, Jun 12 2003
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1)*(-1)^k*2^(n-2k). - Paul Barry, Jan 16 2005
Equals binomial transform of [1, 1, 1, -1, 1, -1, 1, ...]. - Gary W. Adamson, Jul 15 2008
E.g.f.: 1+x*sinh(x) (aerated sequence). - Paul Barry, Oct 11 2009
a(n) = 0^n + 2*n = A000007(n) + A005843(n). - Reinhard Zumkeller, Jan 11 2012

Corrected by Charles R Greathouse IV, Mar 18 2010

A141243 Number of ways to place non-attacking knights on the n X n board.

Original entry on oeis.org

1, 2, 16, 94, 1365, 55213, 3368146, 394631712, 101693175442, 50929053498909, 48988729226134301, 96325314726538906164, 375615195988659173454092, 2933480442104347575000834468, 45480806737377995771543610802659, 1422902021111889804120495149240353936

Offset: 0

Max Alekseyev, Jun 17 2008

The maximum number of non-attacking knights is given by A030978.

Also the number of vertex covers and independent vertex sets in the n X n knight graph.

Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-72, 283-285.
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Knight Graph
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A182407, A182408, A201540.

Row sums of A244081.

b[n_, l_] := b[n, l] = Module[{d, f, g, k}, d = Length[l]/3; f = False; Which[n == 0, 1, l[[1 ;; d]] == Array[f &, d], b[n - 1, Join[l[[d + 1 ;; 3*d]], Array[True &, d]]], True, For[k = 1, ! l[[k]], k++]; g = ReplacePart[l, k -> f];
     If[k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
     If[k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
     If[k > 2, g = ReplacePart[g, d - 2 + k -> f]];
     If[k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
     Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Array[True &, n*3]]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 10}] (* Jean-François Alcover, Mar 29 2016, after Alois P. Heinz's code for A244081 *)

A141243(n=4, s=n^2-1, bad=0)={ while(s && bittest(bad, s), s--);
   if(s < n, 2^(s+1-hammingweight(bad % (2<A141243(n, s-1, bad), x = s%n);
      x > 1 && bad = bitor(bad, 2^(s-n-2)); x < n-2 && bad = bitor(bad, 2^(s-n+2));
      if( s >= 2*n, x && bad = bitor(bad, 2^(s-2*n-1));
              x < n-1 && bad = bitor(bad, 2^(s-2*n+1))
   ); cnt + A141243(n, s-1, bad))} \\ M. F. Hasler, Mar 18 2025

def A141243(n=4, start=(1,1), forbidden=()):
    if start[0] >= n: return 2**sum((n,y+1) not in forbidden for y in range(n))
    nxt = (start[0],start[1]+1) if start[1]A141243(n, nxt, forbidden)
    if start in forbidden: return cnt
    forbidden = {s for s in forbidden if s >= nxt}
    if start[1]2: forbidden |= {(start[0]+1,start[1]-2)}
    if start[0]1: forbidden |= {(start[0]+2,start[1]-1)}
    return cnt+A141243(n, nxt, forbidden) # M. F. Hasler, Mar 17 2025

a(8)-a(13) from R. H. Hardin, Aug 25 2008
a(0) from Alois P. Heinz, Jun 19 2014
a(14) from Hiroaki Yamanouchi, Aug 28 2014
a(15) from Hiroaki Yamanouchi, Aug 29 2014

cp's OEIS Frontend

A244081 Number T(n,k) of ways to place k nonattacking knights on an n X n board; triangle T(n,k), n>=0, 0<=k<=A030978(n), read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A005843 The nonnegative even numbers: a(n) = 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

R

Formula

A008794 Squares repeated; a(n) = floor(n/2)^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

A004277 1 together with positive even numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

Formula

Extensions

A141243 Number of ways to place non-attacking knights on the n X n board.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A243716 Irregular triangle read by rows: T(n, k) = number of inequivalent (mod the dihedral group D_8 of order 8) ways to place k nonattacking knights on an n X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs