A235453 Triangle T(n, k) = Number of non-equivalent (mod D_4) ways to arrange k indistinguishable points on an n X n square grid so that no three of them are collinear. Triangle read by rows.

1, 0, 1, 2, 1, 1, 3, 8, 13, 15, 5, 1, 3, 21, 70, 181, 217, 142, 28, 4, 6, 49, 290, 1253, 3192, 4699, 3385, 1076, 110, 5, 6, 93, 867, 6044, 27041, 77970, 134353, 129929, 62177, 12511, 717, 11, 10, 171, 2266, 22302, 149217, 672506, 1958674, 3531747, 3695848, 2068757

Offset: 1

Author

Heinrich Ludwig, Jan 12 2014

Keywords

• nonn
• tabf

Comments

The triangle T(n, k) is irregularly shaped: 1 <= k <= 2n. First row corresponds to n = 1.

Without the restriction "non-equivalent (mod D_4)" the numbers are given by triangle A194193. (But this one is read by antidiagonals!)

T(n, 2n) = A000769(n).

2n is an upper bound on the number of points that can be placed on the grid. For large n, it is conjectured that this bound is not reached (see MathWorld link).

Examples

			Triangle begins
1,  0;
1,  2,   1,    1;
3,  8,  13,   15,     5,     1;
3, 21,  70,  181,   217,   142,     28,      4;
6, 49, 290, 1253,  3192,  4699,   3385,   1076,   110,     5;
6, 93, 867, 6044, 27041, 77970, 134353, 129929, 62177, 12511, 717, 11;
...
		

Links

• Heinrich Ludwig, Table of n, a(n) for n = 1..99
• Achim Flammenkamp, Progress in the no-three-in-line problem
• Eric Weisstein's World of Mathematics, No-Three-in-a-Line-Problem

Crossrefs

Cf. A194193, A000938, A000769.

Column 1 is A008805

Column 2 is A014409

Column 3 is A235454

Column 4 is A235455

Column 5 is A235456

Column 6 is A235457

Column 7 is A235458