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.

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,5

Comments

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.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Example

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;
...

Mathematica

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 *)

Crossrefs

Row sums are A290615.

Cf. A259691, A259697.

Sequence in context: A206799 A084119 A166073 * A283879 A216178 A122899

Adjacent sequences: A290721 A290722 A290723 * A290725 A290726 A290727

Keyword

nonn,tabl

Author

Andrew Howroyd, Aug 09 2017

Status

approved