A194485 T(n,k) = number of ways to arrange k indistinguishable points on an n X n X n triangular grid so that no four points are in the same row or diagonal.

1, 0, 3, 0, 3, 6, 0, 1, 15, 10, 0, 0, 20, 45, 15, 0, 0, 15, 120, 105, 21, 0, 0, 6, 207, 455, 210, 28, 0, 0, 1, 234, 1347, 1330, 378, 36, 0, 0, 0, 165, 2817, 5922, 3276, 630, 45, 0, 0, 0, 63, 4135, 19362, 20307, 7140, 990, 55, 0, 0, 0, 9, 4080, 47010, 94584, 58527, 14190, 1485

Offset: 1

Author

R. H. Hardin, Aug 26 2011

Keywords

• nonn
• tabl

Comments

Table starts

...1....0......0.......0.........0..........0...........0............0

...3....3......1.......0.........0..........0...........0............0

...6...15.....20......15.........6..........1...........0............0

..10...45....120.....207.......234........165..........63............9

..15..105....455....1347......2817.......4135........4080.........2463

..21..210...1330....5922.....19362......47010.......83745.......105663

..28..378...3276...20307.....94584.....337860......927471......1931571

..36..630...7140...58527....365904....1790472.....6924357.....21123489

..45..990..14190..148239...1193283....7622340....39196161....162957252

..55.1485..26235..339669...3413619...27489825...180512640....974497260

..66.2145..45760..718344...8800704...87018360...708150465...4794685500

..78.3003..76076.1422564..20845968..247874770..2442836682..20207649891

..91.4095.121485.2666664..46017972..647091588..7582054194..75074999142

.105.5460.187460.4771221..95710797.1569661600.21540941994.251128663929

.120.7140.280840.8201466.189154056.3576049620.56763356130.768641935191

Examples

			Some solutions for n=5, k=4:
......0..........0..........0..........1..........0..........0..........0
.....0.0........0.1........0.1........1.0........0.0........0.1........0.0
....0.0.0......0.0.1......1.0.0......0.0.0......0.0.0......0.0.0......1.1.0
...0.0.1.1....0.0.0.0....0.0.1.0....0.0.1.0....0.0.1.1....0.0.0.0....0.0.0.0
..0.1.0.0.1..0.1.1.0.0..0.1.0.0.0..0.1.0.0.0..0.0.1.1.0..0.1.1.0.1..1.0.1.0.0
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..264

Crossrefs

Column 1 is A000217.

Column 2 is A050534(n+1).

Column 3 is A093566(n+2).

Formula

Empirical:

T(n,1) = (1/2)*n^2 + (1/2)*n

T(n,2) = (1/8)*n^4 + (1/4)*n^3 - (1/8)*n^2 - (1/4)*n

T(n,3) = (1/48)*n^6 + (1/16)*n^5 - (1/16)*n^4 - (11/48)*n^3 + (1/24)*n^2 + (1/6)*n

T(n,4) = (1/384)*n^8 + (1/96)*n^7 - (1/64)*n^6 - (13/120)*n^5 + (19/128)*n^4 + (7/96)*n^3 - (13/96)*n^2 + (1/40)*n

T(n,5) = (1/3840)*n^10 + (1/768)*n^9 - (1/384)*n^8 - (59/1920)*n^7 + (281/3840)*n^6 + (149/3840)*n^5 - (5/24)*n^4 + (29/320)*n^3 + (11/80)*n^2 - (1/10)*n

T(n,6) = (1/46080)*n^12 + (1/7680)*n^11 - (1/3072)*n^10 - (137/23040)*n^9 + (871/46080)*n^8 + (3107/161280)*n^7 - (5573/46080)*n^6 + (1157/23040)*n^5 + (2627/11520)*n^4 - (1121/5760)*n^3 - (181/1440)*n^2 + (11/84)*n

T(n,7) = (1/645120)*n^14 + (1/92160)*n^13 - (1/30720)*n^12 - (79/92160)*n^11 + (101/30720)*n^10 + (757/129024)*n^9 - (3049/92160)*n^8 - (34099/645120)*n^7 + (6613/15360)*n^6 - (16859/23040)*n^5 + (1043/3840)*n^4 + (2759/5040)*n^3 - (753/1120)*n^2 + (13/56)*n

Empirical: general T(n,k,z) for fewer than z points in any row or diagonal is polynomial in n of degree 2k with lead coefficient 1/(2^k*k!) for small k.

T(n,1,2) = (1/2)*n^2 + (1/2)*n

T(n,1,3) = (1/2)*n^2 + (1/2)*n

T(n,1,4) = (1/2)*n^2 + (1/2)*n

T(n,2,2) = (1/8)*n^4 - (1/4)*n^3 - (1/8)*n^2 + (1/4)*n

T(n,2,3) = (1/8)*n^4 + (1/4)*n^3 - (1/8)*n^2 - (1/4)*n

T(n,2,4) = (1/8)*n^4 + (1/4)*n^3 - (1/8)*n^2 - (1/4)*n

T(n,3,3) = (1/48)*n^6 + (1/16)*n^5 - (3/16)*n^4 + (1/48)*n^3 + (1/6)*n^2 - (1/12)*n

T(n,3,4) = (1/48)*n^6 + (1/16)*n^5 - (1/16)*n^4 - (11/48)*n^3 + (1/24)*n^2 + (1/6)*n

T(n,4,3) = (1/384)*n^8 + (1/96)*n^7 - (5/64)*n^6 + (13/240)*n^5 + (27/128)*n^4 - (23/96)*n^3 - (13/96)*n^2 + (7/40)*n

T(n,4,4) = (1/384)*n^8 + (1/96)*n^7 - (1/64)*n^6 - (13/120)*n^5 + (19/128)*n^4 + (7/96)*n^3 - (13/96)*n^2 + (1/40)*n

T(n,5,3) = (1/3840)*n^10 + (1/768)*n^9 - (7/384)*n^8 + (37/1920)*n^7 + (737/3840)*n^6 - (2347/3840)*n^5 + (101/192)*n^4 + (93/320)*n^3 - (7/10)*n^2 + (3/10)*n

T(n,5,4) = (1/3840)*n^10 + (1/768)*n^9 - (1/384)*n^8 - (59/1920)*n^7 + (281/3840)*n^6 + (149/3840)*n^5 - (5/24)*n^4 + (29/320)*n^3 + (11/80)*n^2 - (1/10)*n

T(n,6,4) = (1/46080)*n^12 + (1/7680)*n^11 - (1/3072)*n^10 - (137/23040)*n^9 + (871/46080)*n^8 + (3107/161280)*n^7 - (5573/46080)*n^6 + (1157/23040)*n^5 + (2627/11520)*n^4 - (1121/5760)*n^3 - (181/1440)*n^2 + (11/84)*n

T(n,7,4) = (1/645120)*n^14 + (1/92160)*n^13 - (1/30720)*n^12 - (79/92160)*n^11 + (101/30720)*n^10 + (757/129024)*n^9 - (3049/92160)*n^8 - (34099/645120)*n^7 + (6613/15360)*n^6 - (16859/23040)*n^5 + (1043/3840)*n^4 + (2759/5040)*n^3 - (753/1120)*n^2 + (13/56)*n