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

Author

Andrew Howroyd, Aug 09 2017

Keywords

• nonn
• tabl

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.

Examples

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

Links

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

Crossrefs

Row sums are A290615.

Cf. A259691, A259697.

Programs

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