A146304 -id:A146304 - cp's OEIS frontend

A288182 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking bishops on the white squares of an n X n board with every square controlled by at least one bishop (1<=k

2, 0, 2, 0, 4, 4, 0, 2, 16, 4, 0, 0, 16, 64, 8, 0, 0, 0, 128, 160, 8, 0, 0, 0, 72, 784, 528, 16, 0, 0, 0, 24, 864, 3672, 1152, 16, 0, 0, 0, 0, 432, 9072, 18336, 3584, 32, 0, 0, 0, 0, 0, 8304, 65664, 69472, 7424, 32, 0, 0, 0, 0, 0, 2880, 109152, 484416, 313856, 22592, 64

Offset: 2

Andrew Howroyd, Jun 06 2017

See A146304 for algorithm and PARI code to produce this sequence.
Equivalently, the coefficients of the maximal independent set polynomials on the n X n white bishop graph.
The product of the first nonzero term in each row of this sequence and that of A288183 give A122749.

			Triangle starts (first term is n=2, k=1):
  2;
  0, 2;
  0, 4,  4;
  0, 2, 16,   4;
  0, 0, 16,  64,   8;
  0, 0,  0, 128, 160,    8;
  0, 0,  0,  72, 784,  528,    16;
  0, 0,  0,  24, 864, 3672,  1152,    16;
  0, 0,  0,   0, 432, 9072, 18336,  3584,   32;
  0, 0,  0,   0,   0, 8304, 65664, 69472, 7424, 32;
  ...

Andrew Howroyd, Table of n, a(n) for n = 2..1276
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, White Bishop Graph

Row sums are A290613.

Cf. A288183, A122749, A274106, A146304.

A288183 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking bishops on the black squares of an n X n board with every square controlled by at least one bishop.

Original entry on oeis.org

2, 1, 4, 0, 4, 4, 0, 0, 22, 8, 0, 0, 16, 64, 8, 0, 0, 6, 128, 228, 16, 0, 0, 0, 72, 784, 528, 16, 0, 0, 0, 0, 1056, 4352, 1688, 32, 0, 0, 0, 0, 432, 9072, 18336, 3584, 32, 0, 0, 0, 0, 120, 7776, 76488, 87168, 11024, 64, 0, 0, 0, 0, 0, 2880, 109152, 484416, 313856, 22592, 64

Offset: 2

Andrew Howroyd, Jun 06 2017

See A146304 for algorithm and PARI code to produce this sequence.
Equivalently, the coefficients of the maximal independent set polynomials on the n X n black bishop graph.
The product of the first nonzero term in each row of this sequence and that of A288182 give A122749.

			Triangle begins:
  2;
  1, 4;
  0, 4,  4;
  0, 0, 22,   8;
  0, 0, 16,  64,    8;
  0, 0,  6, 128,  228,   16;
  0, 0,  0,  72,  784,  528,    16;
  0, 0,  0,   0, 1056, 4352,  1688,    32;
  0, 0,  0,   0,  432, 9072, 18336,  3584,    32;
  0, 0,  0,   0,  120, 7776, 76488, 87168, 11024,  64;
  ...
The first term is T(2,1) = 2.

Andrew Howroyd, Table of n, a(n) for n = 2..1276
Eric Weisstein's World of Mathematics, Black Bishop Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Row sums are A290594.

Cf. A288182, A122749, A274105, A146304.

A290615 Number of maximal independent vertex sets (and minimal vertex covers) in the n-triangular honeycomb bishop graph.

Original entry on oeis.org

1, 2, 5, 14, 45, 164, 661, 2906, 13829, 70736, 386397, 2242118, 13759933, 88975628, 604202693, 4296191090, 31904681877, 246886692680, 1986631886029, 16592212576862, 143589971363981, 1285605080403332, 11891649654471285, 113491862722958474, 1116236691139398565

Offset: 1

Eric W. Weisstein, Aug 07 2017

nonn

From Andrew Howroyd, Aug 09 2017: (Start)
See A146304 for algorithm and PARI code to produce this sequence.
The total number of independent vertex sets is given by Bell(n+1) where Bell=A000110.
A bishop can move along two axes in the triangular honeycomb grid.
Equivalently, the number of arrangements of non-attacking rooks on an n X n right triangular board with every square controlled by at least one rook. (End)

Andrew Howroyd, Table of n, a(n) for n = 1..150
Max Alekseyev, Subsequences of odd powers, answer to question on Mathoverflow.
Max Alekseyev, Generating function for partial sums of the sequence, answer to question on Mathoverflow.
Peter Taylor, Subsequence of the cubes, answer to question on Mathoverflow.
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Row sums of A290724.
Cf. A000110 (independent vertex sets), A007814, A146304.
Similar recurrences: A124758, A243499, A284005, A329369, A341392.

Table[Sum[k! StirlingS2[m, k] StirlingS2[n + 1 - m, k + 1], {m, 0, n}, {k, 0, Min[m, n - m]}], {n, 20}] (* Eric W. Weisstein, Feb 01 2024 *)

{ A290615(n) = sum(m=0, n, sum(k=0, min(m,n-m), k! * stirling(m,k,2) * stirling(n+1-m,k+1,2) )); } \\ Max Alekseyev, Oct 14 2021

Conjecture: a(n) = Sum_{k=0..2^(n-1) - 1} b(k) for n > 0 where b(2n+1) = b(n - 2^f(n)), b(2n) = b(n) + b(2n - 2^f(n)) for n > 0 with b(0) = b(1) = 1 and where f(n) = A007814(n). Also b((4^n - 1)/3) = (floor((n+1)/2)!)^3. - Mikhail Kurkov, Sep 18 2021

a(n) = Sum_{m=0..n} Sum_{k=0..min(m,n-m)} k! * S(m,k) * S(n+1-m,k+1), where S(,) are Stirling numbers of second kind. - Max Alekseyev, Oct 14 2021

Terms a(10) and beyond from Andrew Howroyd, Aug 09 2017

A290594 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n black bishop graph.

Original entry on oeis.org

1, 2, 5, 8, 30, 88, 378, 1400, 7128, 31456, 182640, 932960, 6048912, 35000320, 249904656, 1609079552, 12518446848, 88532931328, 744008722944, 5721984568832, 51576606895104, 427904524628992, 4112973567496704, 36567439575256064, 372971541998834688

Offset: 1

Eric W. Weisstein, Aug 07 2017

nonn

See A146304 for algorithm and PARI code to produce this sequence. - Andrew Howroyd, Aug 07 2017

Andrew Howroyd, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Black Bishop Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Row sums of A288183.

Cf. A146304, A290613.

Terms a(12) and beyond from Andrew Howroyd, Aug 07 2017

A290613 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n white bishop graph.

Original entry on oeis.org

2, 2, 8, 22, 88, 296, 1400, 5728, 31456, 150896, 932960, 5115376, 35000320, 214949120, 1609079552, 10909768192, 88532931328, 655461278720, 5721984568832, 45854239383040, 427904524628992, 3685075352873984, 36567439575256064, 336404621367433216

Offset: 2

Eric W. Weisstein, Aug 07 2017

nonn

See A146304 for algorithm and PARI code to produce this sequence. - Andrew Howroyd, Aug 09 2017

Andrew Howroyd, Table of n, a(n) for n = 2..100
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Eric Weisstein's World of Mathematics, White Bishop Graph

Row sums of A288182.

Cf. A146304, A290594.

Terms a(12) and beyond from Andrew Howroyd, Aug 09 2017

A146303 Number of distinct ways to place queens (even fewer than n) on an n X n chessboard so that no queen is attacking another and that it is not possible to add another queen.

Original entry on oeis.org

1, 4, 9, 18, 58, 348, 1862, 10188, 57600, 376692, 2640422, 19469324, 151978440, 1258451524, 10963084588, 100087600184

Offset: 1

Paolo Bonzini, Oct 29 2008

In other words, number of maximal independent vertex sets (and minimal vertex covers) in the n X n queen graph. - Eric W. Weisstein, Jun 20 2017

			The a(2) = 4 solutions are to place a single queen in each of the squares of the chessboard. For n=3, there is a single one-queen solution (placing the queen in b2) and eight two-queen solutions, but no three-queen solution (see A000170).

S. W. Golomb and L. D. Baumert, Backtrack Programming, Journal of the ACM, 4 (2001), 516-524.
Stefan Kral, C++11 code using OpenMP
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Eric Weisstein's World of Mathematics, Queen Graph

Cf. A000170, A146304.

a(12)-a(16) from Stefan Kral, Aug 10 2016

A290724 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking rooks on an n X n right triangular board with every square controlled by at least one rook.

Original entry on oeis.org

1, 1, 1, 0, 4, 1, 0, 2, 11, 1, 0, 0, 18, 26, 1, 0, 0, 6, 100, 57, 1, 0, 0, 0, 96, 444, 120, 1, 0, 0, 0, 24, 900, 1734, 247, 1, 0, 0, 0, 0, 600, 6480, 6246, 502, 1, 0, 0, 0, 0, 120, 8520, 39762, 21320, 1013, 1, 0, 0, 0, 0, 0, 4320, 90600, 219312, 70128, 2036, 1

Offset: 1

Andrew Howroyd, Aug 09 2017

See A146304 for algorithm and PARI code to produce this sequence.

Equivalently, the number of maximal independent vertex sets in the n-triangular honeycomb bishop graph with k vertices. A bishop can move along two axes in the triangular honeycomb grid.

			Triangle begins:
1;
1, 1;
0, 4,  1;
0, 2, 11,  1;
0, 0, 18,  26,  1;
0, 0,  6, 100,  57,    1;
0, 0,  0,  96, 444,  120,     1;
0, 0,  0,  24, 900, 1734,   247,     1;
0, 0,  0,  0,  600, 6480,  6246,   502,    1;
0, 0,  0,  0,  120, 8520, 39762, 21320, 1013, 1;
...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Row sums are A290615.

Cf. A259691, A259697.

CoefficientList[Table[Sum[k! StirlingS2[m, k] StirlingS2[n + 1 - m, k + 1] x^(n - k), {m, 0, n}, {k, 0, Min[m, n - m]}], {n, 20}]/x, x] // Flatten (* Eric W. Weisstein, Feb 01 2024 *)

cp's OEIS Frontend

A288182 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking bishops on the white squares of an n X n board with every square controlled by at least one bishop (1<=k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A288183 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking bishops on the black squares of an n X n board with every square controlled by at least one bishop.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A290615 Number of maximal independent vertex sets (and minimal vertex covers) in the n-triangular honeycomb bishop graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A290594 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n black bishop graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A290613 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n white bishop graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A146303 Number of distinct ways to place queens (even fewer than n) on an n X n chessboard so that no queen is attacking another and that it is not possible to add another queen.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A290724 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking rooks on an n X n right triangular board with every square controlled by at least one rook.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica