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

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

Links

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

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

Example

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

Crossrefs

Column 1 is A000217.

Column 2 is A050534(n+1).

Column 3 is A093566(n+2).

Sequence in context: A194492 A194136 A194480 * A120987 A281293 A258108

Adjacent sequences: A194482 A194483 A194484 * A194486 A194487 A194488

Keyword

nonn,tabl

Author

R. H. Hardin, Aug 26 2011

Status

approved