Here's a simple Python program that can be used to extend A178256 and others. For a given n and k, it counts the number of ways to choose k collinear points in an nxn square. It takes polytime, so you can get well past n=1000 (it's faster if you use pypy). Of course the numbers get very big very fast. I'm sure there's a way to calculate this even faster, but for the purposes of the OEIS this probably suffices. It can easily be modified to work for non-square grids. Sample usage:
pypy3 1000 4 1000 4 156556407299676
import sys, math n = int(sys.argv[1]) k = int(sys.argv[2]) def binom(a,b): if b<0 or b>a: return 0 if b+b>a: b = a-b r = 1 for i in range(b): r = r * (a-i) // (i+1) return r s = 0 for i in range(n): for j in range(i+1): g = 1+math.gcd(i, j) if g >= k: mul = 2 if j > 0 and j < i: mul *= 2 s += mul * binom(g-2, k-2) * (n-j) * (n-i) print(n,k,s) On Mon, Jun 15, 2020 at 10:06 AM Neil Sloane <njasloane@gmail.com> wrote:
PS I forgot to mention that the counts for collinear 4-tuples on a square grid (A178256) were computed by Ron Hardin, a former Bell Labs colleague of Tom and myself. He went out to n = 48 (in May 2010).
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Mon, Jun 15, 2020 at 12:53 PM Neil Sloane <njasloane@gmail.com> wrote:
Concerning my question from the other day about the counts for the 4 different ways of choosing 4 points from an m X n rectangular grid:
Tom Duff kindly computed the numbers for m and n up to 21. This produced 4 arrays of numbers, for the 4 different possibilities (collinear, one point inside a triangle, etc) which are now A334708 - A334711.
It turns out that for the square grid (when m = n), the collinear counts and the convex quadrilateral counts were already in the OEIS, as A178256 and A189413. I've added Ed Pegg's remark about Sylverster's theorem to the latter entry.
The other two diagonal sequences are now A334712 and A334713.
If we pick 3 points rather than 4, there are just two cases, as I mentioned in my first message, and the two arrays are A334704 and A334705. I see that Tom has just produced more data for those two arrays, but I have not had time to update them yet.
On Mon, Jun 15, 2020 at 11:59 AM Tom Duff <td@pixar.com> wrote:
I made a table of the number of collinear triples in an m by n grid, up to 50x50. Too big for a math-fun message, but you can see it at http://iq0.com/collinear-triples.txt
Here is the diagonal of the table (columns are m, n, number of collinear triples, total number of triples, probability that a randomly chosen triple is collinear):
m n collinear total probability
1 1 0 0 NaN 2 2 0 4 0 3 3 8 84 0.0952381 4 4 44 560 0.0785714 5 5 152 2300 0.066087 6 6 372 7140 0.0521008 7 7 824 18424 0.0447243 8 8 1544 41664 0.0370584 9 9 2712 85320 0.0317862 10 10 4448 161700 0.0275077 11 11 6992 287980 0.0242795 12 12 10332 487344 0.0212006 13 13 15072 790244 0.0190726 14 14 21012 1235780 0.017003 15 15 28688 1873200 0.015315 16 16 38520 2763520 0.0139387 17 17 50880 3981264 0.0127799 18 18 65480 5616324 0.0116589 19 19 83640 7775940 0.0107563 20 20 104676 10586800 0.00988741 21 21 130264 14197260 0.00917529 22 22 160556 18779684 0.00854945 23 23 195848 24532904 0.00798307 24 24 235600 31684800 0.00743574 25 25 282840 40495000 0.00698457 26 26 336384 51257700 0.0065626 27 27 397136 64304604 0.00617586 28 28 465876 80007984 0.00582287 29 29 544464 98783860 0.00551167 30 30 630684 121095300 0.00520816 31 31 729744 147455840 0.0049489 32 32 837744 178433024 0.00469501 33 33 958384 214652064 0.00446483 34 34 1091904 256799620 0.00425197 35 35 1238520 305627700 0.00405238 36 36 1400140 361957680 0.00386824 37 37 1581384 426684444 0.00370621 38 38 1776084 500780644 0.00354663 39 39 1987560 585301080 0.00339579 40 40 2217608 681387200 0.00325455 41 41 2471624 790271720 0.00312756 42 42 2742408 913283364 0.0030028 43 43 3040304 1051851724 0.00289043 44 44 3356852 1207512240 0.00277997 45 45 3700016 1381911300 0.00267746 46 46 4072916 1576811460 0.00258301 47 47 4471712 1794096784 0.00249246 48 48 4893080 2035778304 0.00240354 49 49 5352080 2303999600 0.00232295 50 50 5839616 2601042500 0.00224511
On Mon, Jun 15, 2020 at 8:32 AM Tom Duff <td@pixar.com> wrote:
The limiting probability is obviously zero. I can make a table for you. Hang on a few minutes...
On Mon, Jun 15, 2020 at 6:53 AM ed pegg <ed@mathpuzzle.com> wrote:
I think a related problem should be considered. In a m×n grid of
points, 3 selected, what are the odds of 3 points in a row?
On Monday, June 15, 2020, 08:13:54 AM CDT, Gareth McCaughan <
gareth.mccaughan@pobox.com> wrote:
On 14/06/2020 22:22, Tom Duff wrote:
Here's my table up to 21x21 using the stupidest possible program, which just enumerates and classifies each set of 4 points. 21x21 because that's where 32 bit counters start to overflow. I'm
rerunning
with 64 bit counters (up to 331x331), but someone will find good recurrences before it even gets close to finishing. Of course, the chance that my program has exactly zero bugs is not large.
In particular, it is at most 1. :-)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --