[math-fun] Number of ways to pick 4 points from an m X n grid?
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities: (i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area. As a function of m and n, what are these numbers? This must be a classical problem, but I don't have enough data to check in the OEIS. (It might be called the "moduli space" of 4-tuples from an m X n grid.) I would like the 4 tables of numbers, and exact and/or asymptotic formulas. Which is more likely, (iii) or (iv)? I just looked at what happens if we choose three rather than four points. Now there are only two cases, collinear or not. This produces two triangles of numbers, which are now A334704 and A334705. E.g. A334704(m,n) is the number of ways to choose 3 collinear points from an m X n grid, for m >= n >= 1. Both triangles need more terms, and are lacking exact formulas (or generating functions). 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
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. Columns of the table are m, n, # of collinear 4-tuples, # of triangles with the extra point inside, # of triangles with the extra point on and edge, # of concyclic quads total number of quads (should be the sum of the previous 4 columns unless I have a *really* stupid bug). m n collinear in on concyclic total 2 2 0 0 0 1 1 2 3 0 0 6 9 15 2 4 2 0 32 36 70 2 5 10 0 100 100 210 2 6 30 0 240 225 495 2 7 70 0 490 441 1001 2 8 140 0 896 784 1820 2 9 252 0 1512 1296 3060 2 10 420 0 2400 2025 4845 2 11 660 0 3630 3025 7315 2 12 990 0 5280 4356 10626 2 13 1430 0 7436 6084 14950 2 14 2002 0 10192 8281 20475 2 15 2730 0 13650 11025 27405 2 16 3640 0 17920 14400 35960 2 17 4760 0 23120 18496 46376 2 18 6120 0 29376 23409 58905 2 19 7752 0 36822 29241 73815 2 20 9690 0 45600 36100 91390 2 21 11970 0 55860 44100 111930 3 3 0 8 48 70 126 3 4 3 48 168 276 495 3 5 15 144 456 750 1365 3 6 45 348 990 1677 3060 3 7 105 700 1920 3260 5985 3 8 210 1280 3360 5776 10626 3 9 378 2144 5520 9508 17550 3 10 630 3400 8550 14825 27405 3 11 990 5120 12720 22090 40920 3 12 1485 7440 18216 31764 58905 3 13 2145 10448 25368 44290 82251 3 14 3003 14308 34398 60221 111930 3 15 4095 19124 45696 80080 148995 3 16 5460 25088 59520 104512 194580 3 17 7140 32320 76320 134120 249900 3 18 9180 41040 96390 169641 316251 3 19 11628 51384 120240 211758 395010 3 20 14535 63600 148200 261300 487635 3 21 17955 77840 180840 319030 595665 4 4 10 240 532 1038 1820 4 5 29 716 1312 2788 4845 4 6 72 1712 2652 6190 10626 4 7 157 3404 4972 11942 20475 4 8 302 6176 8420 21062 35960 4 9 531 10336 13452 34586 58905 4 10 874 16288 20480 53748 91390 4 11 1361 24480 29980 79930 135751 4 12 2028 35504 42288 114760 194580 4 13 2917 49748 58304 159756 270725 4 14 4070 68000 78272 216948 367290 4 15 5535 90828 103032 288240 487635 4 16 7366 118944 133284 375782 635376 4 17 9617 153104 169792 481872 814385 4 18 12348 194256 213084 609102 1028790 4 19 15625 243000 264540 759810 1282975 4 20 19514 300528 324500 937038 1581580 4 21 24087 367668 394188 1143558 1929501 5 5 64 2100 3088 7398 12650 5 6 129 4984 5964 16328 27405 5 7 248 9900 10816 31396 52360 5 8 442 17936 17768 55244 91390 5 9 747 29924 27840 90484 148995 5 10 1196 47080 41652 140372 230300 5 11 1825 70700 60040 208490 341055 5 12 2679 102460 83448 299048 487635 5 13 3818 143420 113936 415866 677040 5 14 5287 195880 151444 564284 916895 5 15 7146 261504 197568 749232 1215450 5 16 9464 342336 253512 976268 1581580 5 17 12313 440400 320896 1251176 2024785 5 18 15762 558504 400140 1580784 2555190 5 19 19895 698460 494040 1971150 3183545 5 20 24793 863596 602720 2430116 3921225 5 21 30552 1056144 728880 2964654 4780230 6 6 234 11604 11340 35727 58905 6 7 405 22936 20142 68447 111930 6 8 666 41372 32436 120106 194580 6 9 1065 68844 50004 196338 316251 6 10 1638 108132 73704 304161 487635 6 11 2439 161964 105282 451035 720720 6 12 3510 234228 144936 646116 1028790 6 13 4929 327500 196284 897712 1426425 6 14 6744 446812 258792 1217153 1929501 6 15 9027 596040 335034 1615089 2555190 6 16 11874 779464 427548 2103074 3321960 6 17 15363 1001948 538488 2693776 4249575 6 18 19572 1269720 668052 3401751 5359095 6 19 24603 1587180 820890 4240203 6672876 6 20 30552 1961544 996780 5225694 8214570 6 21 37551 2397516 1201320 6372738 10009125 7 7 660 45184 35264 130768 211876 7 8 1020 81320 55916 229034 367290 7 9 1545 135192 84960 373968 595665 7 10 2276 212152 123690 578777 916895 7 11 3283 317492 174976 857524 1353275 7 12 4605 458812 238512 1227572 1929501 7 13 6358 641108 320672 1704532 2672670 7 14 8573 874196 419618 2309893 3612280 7 15 11334 1165720 539328 3063848 4780230 7 16 14766 1523776 684316 3987962 6210820 7 17 18951 1958144 857184 5106472 7940751 7 18 23976 2480796 1057590 6446763 10009125 7 19 29981 3100188 1293696 8033580 12457445 7 20 37057 3830460 1563724 9898374 15329615 7 21 45372 4680796 1877280 12068492 18671940 8 8 1524 145648 88088 400116 635376 8 9 2220 241544 132708 652318 1028790 8 10 3154 378400 191588 1008438 1581580 8 11 4412 565636 268972 1492870 2331890 8 12 6030 816520 363876 2135534 3321960 8 13 8162 1140188 486088 2963688 4598126 8 14 10822 1553664 632076 4014258 6210820 8 15 14136 2069984 808788 5321662 8214570 8 16 18228 2703964 1022088 6923720 10668000 8 17 23184 3473064 1275036 8862546 13633830 8 18 29100 4398036 1566576 11185164 17178876 8 19 36154 5494112 1909200 13934584 21374050 8 20 44432 6785900 2299104 17164924 26294360 8 21 54138 8290100 2750808 20923864 32018910 9 9 3156 399656 198912 1062016 1663740 9 10 4362 625232 285312 1640284 2555190 9 11 5940 933808 397968 2426660 3764376 9 12 7923 1346928 534888 3469356 5359095 9 13 10509 1879888 710592 4812716 7413705 9 14 13689 2560304 918912 6516220 10009125 9 15 17631 3409300 1170672 8635232 13232835 9 16 22458 4451832 1473012 11231574 17178876 9 17 28302 5715684 1831392 14372472 21947850 9 18 35226 7235172 2242188 18134334 27646920 9 19 43446 9035816 2723376 22587172 34389810 9 20 53043 11157400 3268356 27818006 42296805 9 21 64263 13627700 3898560 33904228 51494751 10 10 5928 976552 407744 2531001 3921225 10 11 7914 1457172 566046 3742053 5773185 10 12 10350 2100112 757008 5347100 8214570 10 13 13480 2929564 1001196 7414640 11358880 10 14 17270 3987896 1288864 10035585 15329615 10 15 21930 5307956 1635414 13294975 20260275 10 16 27584 6928764 2049984 17288028 26294360 10 17 34408 8893036 2540380 22117546 33585370 10 18 42432 11253828 3099816 27900729 42296805 10 19 51966 14050288 3755414 34744497 52602165 10 20 63030 17344348 4494792 42782780 64684950 10 21 75912 21180052 5347452 52135244 78738660 11 11 10428 2172328 783344 5529310 8495410 11 12 13437 3128428 1043784 7897136 12082785 11 13 17231 4362152 1375176 10947126 16701685 11 14 21751 5935600 1763350 14812425 22533126 11 15 27249 7897756 2229312 19618448 29772765 11 16 33862 10306352 2785484 25505202 38630900 11 17 41798 13224904 3441600 32624168 49332470 11 18 51054 16731692 4186794 41147515 62117055 11 19 62034 20884928 5059248 51232666 77238876 11 20 74697 25776176 6039348 63076574 94966795 11 21 89445 31470380 7169640 76854850 115584315 12 12 17154 4500816 1388196 11272710 17178876 12 13 21747 6272032 1824288 15620648 23738715 12 14 27132 8529752 2332812 21129214 32018910 12 15 33603 11344676 2941140 27977386 42296805 12 16 41310 14799436 3665412 36364322 54870480 12 17 50493 18985088 4517508 46505662 70058751 12 18 61116 24012756 5481828 58645470 88201170 12 19 73677 29966664 6609192 73008492 109658025 12 20 88074 36976764 7871604 89873898 134810340 12 21 104823 45136568 9326568 109491916 164059875 13 13 27340 8736172 2392592 21639022 32795126 13 14 33791 11876052 3052468 29262324 44224635 13 15 41436 15790612 3838800 38738672 58409520 13 16 50440 20594552 4772360 50343268 75760620 13 17 61079 26414224 5867968 64374064 96717335 13 18 73278 33403168 7103508 81167672 121747626 13 19 87649 41678860 8546376 101035130 151348015 13 20 104009 51421004 10156944 124361628 186043585 13 21 122994 62760192 12011184 151493610 226387980 14 14 41506 16135996 3889292 39559591 59626385 14 15 50523 21446416 4883070 52358651 78738660 14 16 61022 27962776 6059716 68030862 102114376 14 17 73315 35856140 7437300 86978110 130344865 14 18 87288 45333072 8986356 109653159 164059875 14 19 103667 56554132 10792814 136476957 203927570 14 20 122188 69760952 12803924 167967466 250654530 14 21 143607 85132172 15116292 204593680 304985751 15 15 61176 28493760 6124032 69283632 103962600 15 16 73434 37141204 7588884 90006818 134810340 15 17 87645 47615220 9299760 115058880 172061505 15 18 103656 60187856 11218566 145036267 216546345 15 19 122307 75074036 13452288 180497104 269145735 15 20 143253 92591576 15933060 222123286 330791175 15 21 167370 112979748 18780912 270536760 402464790 16 16 87756 48400296 9394536 116910052 174792640 16 17 104190 62037244 11497788 149431718 223070940 16 18 122544 78403600 13851024 188343272 280720440 16 19 143774 97781436 16585516 234371150 348881876 16 20 167452 120581288 19615656 288397124 428761520 16 21 194586 147116676 23089764 351230154 521631180 17 17 123216 79500936 14058816 190977408 284660376 17 18 144282 100456632 16918092 240681534 358200540 17 19 168460 125268524 20234000 299474696 445145680 17 20 195239 154458324 23900924 368479078 547033565 17 21 225765 188429720 28100160 448729840 665485485 18 18 168420 126909720 20345400 303286461 450710001 18 19 195906 158230656 24312546 377338047 560077155 18 20 226146 195072768 28692144 464244252 688235310 18 21 260424 237949112 33701304 565311910 837222750 19 19 227208 197253768 29034288 469431366 695946630 19 20 261417 243150548 34238516 577504274 855154755 19 21 299955 296564724 40181784 703186038 1040232501 20 20 300054 299683032 40356156 710400658 1050739900 20 21 343311 365474776 47332356 864948302 1278098745 21 21 391920 445664700 55487952 1053055398 1554599970 On Sat, Jun 13, 2020 at 6:39 PM Neil Sloane <njasloane@gmail.com> wrote:
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities:
(i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area.
As a function of m and n, what are these numbers? This must be a classical problem, but I don't have enough data to check in the OEIS. (It might be called the "moduli space" of 4-tuples from an m X n grid.)
I would like the 4 tables of numbers, and exact and/or asymptotic formulas. Which is more likely, (iii) or (iv)?
I just looked at what happens if we choose three rather than four points. Now there are only two cases, collinear or not. This produces two triangles of numbers, which are now A334704 and A334705. E.g. A334704(m,n) is the number of ways to choose 3 collinear points from an m X n grid, for m >= n >= 1. Both triangles need more terms, and are lacking exact formulas (or generating functions).
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I pointed Neil to https://mathworld.wolfram.com/SylvestersFour-PointProblem.html which shows the limit is 25/36 ~ 0.694444. Tom's result at 21x21 is 1053055398/1554599970 ~ 0.67738.
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
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
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
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
Tom, that seems helpful. Number of collinear point-triples in an n X n grid. https://oeis.org/A000938 --Ed Pegg Jr
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
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
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/ --
Using Tom Rokicki's program (smarter than anything I did), I ran the A178256 table out to 1000 entries. It took about 15 seconds for the whole list. See here: http://iq0.com/b178256.txt On Mon, Jun 15, 2020 at 1:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
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/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Tom, Tomas, I added your 1000-term b-file for the no. of collinear 4-tuples in an n X n grid to A178256. This is a sufficiently sweet problem that there ought to be a generating function, or some kind of formula. I tried a bunch of things (including gfun) without success. For the RH at least we have a hypothesis. For this sequence - it might be called the RHH Problem, after Ron Hardin - all we have are 1000 integer terms. With 1000 exact terms, surely the world can find a formula. There are a bunch of other sequences all of this class (a LOT of terms, no formula). AI is in the news a lot. It would be nice if the Superseeker sequence guessing program could incorporate some AI to do a better job on sequences like A178256. Tomas, or Tom, could you do the same thing for the 3-point analog, A000938? There we have a 1000-term b-file already, and an explicit formula as a complicated double sum, but no generating function. Maybe with a lot more terms a generating function would emerge. Clearly we should pound on the 3-point problem before attacking the 4-point problem. 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 8:07 PM Tom Duff <td@pixar.com> wrote:
Using Tom Rokicki's program (smarter than anything I did), I ran the A178256 table out to 1000 entries. It took about 15 seconds for the whole list. See here: http://iq0.com/b178256.txt
On Mon, Jun 15, 2020 at 1:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
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/ -- _______________________________________________ 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
hihi - a curious observation; for the collinear problem with m=4, the fourth differences seem to be periodic, repeating (6, 6, 0) starting with n=6 (up to n=38, which is all i have checked from the provided data) for higher m, there are much more complicated paths for differences (for m=3, they are constant 3 and for m=2, they are constant 2, which makes formulas are easy) more later, chris On 2020-06-15 19:32, Neil Sloane wrote:
Tom, Tomas, I added your 1000-term b-file for the no. of collinear 4-tuples in an n X n grid to A178256. This is a sufficiently sweet problem that there ought to be a generating function, or some kind of formula. I tried a bunch of things (including gfun) without success.
For the RH at least we have a hypothesis. For this sequence - it might be called the RHH Problem, after Ron Hardin - all we have are 1000 integer terms. With 1000 exact terms, surely the world can find a formula. There are a bunch of other sequences all of this class (a LOT of terms, no formula).
AI is in the news a lot. It would be nice if the Superseeker sequence guessing program could incorporate some AI to do a better job on sequences like A178256.
Tomas, or Tom, could you do the same thing for the 3-point analog, A000938? There we have a 1000-term b-file already, and an explicit formula as a complicated double sum, but no generating function. Maybe with a lot more terms a generating function would emerge. Clearly we should pound on the 3-point problem before attacking the 4-point problem.
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 8:07 PM Tom Duff <td@pixar.com> wrote:
Using Tom Rokicki's program (smarter than anything I did), I ran the A178256 table out to 1000 entries. It took about 15 seconds for the whole list. See here: http://iq0.com/b178256.txt
On Mon, Jun 15, 2020 at 1:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
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/ -- _______________________________________________ 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://iq0.com/collinear has a bunch of files in it with 1000 terms counting collinear k-tuples of collinear points on an n x n grid for k from 2 to 16. There's a zip file http://iq0.com/collinear/collinear.zip to make it easy to download the whole lot. Again, these were computed using the Rokicki program -- all I did was run it & upload the results. On Mon, Jun 15, 2020 at 7:33 PM Neil Sloane <njasloane@gmail.com> wrote:
Tom, Tomas, I added your 1000-term b-file for the no. of collinear 4-tuples in an n X n grid to A178256. This is a sufficiently sweet problem that there ought to be a generating function, or some kind of formula. I tried a bunch of things (including gfun) without success.
For the RH at least we have a hypothesis. For this sequence - it might be called the RHH Problem, after Ron Hardin - all we have are 1000 integer terms. With 1000 exact terms, surely the world can find a formula. There are a bunch of other sequences all of this class (a LOT of terms, no formula).
AI is in the news a lot. It would be nice if the Superseeker sequence guessing program could incorporate some AI to do a better job on sequences like A178256.
Tomas, or Tom, could you do the same thing for the 3-point analog, A000938? There we have a 1000-term b-file already, and an explicit formula as a complicated double sum, but no generating function. Maybe with a lot more terms a generating function would emerge. Clearly we should pound on the 3-point problem before attacking the 4-point problem.
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 8:07 PM Tom Duff <td@pixar.com> wrote:
Using Tom Rokicki's program (smarter than anything I did), I ran the A178256 table out to 1000 entries. It took about 15 seconds for the whole list. See here: http://iq0.com/b178256.txt
On Mon, Jun 15, 2020 at 1:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
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/ -- _______________________________________________ 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
I don't think there's any sort of closed form or generating function for this, even in the k=3 (three collinear points) case. However, computation can certainly be sped up with Mobeius inversion (although I have not yet done the algebra). -tom On Mon, Jun 15, 2020 at 7:33 PM Neil Sloane <njasloane@gmail.com> wrote:
Tom, Tomas, I added your 1000-term b-file for the no. of collinear 4-tuples in an n X n grid to A178256. This is a sufficiently sweet problem that there ought to be a generating function, or some kind of formula. I tried a bunch of things (including gfun) without success.
For the RH at least we have a hypothesis. For this sequence - it might be called the RHH Problem, after Ron Hardin - all we have are 1000 integer terms. With 1000 exact terms, surely the world can find a formula. There are a bunch of other sequences all of this class (a LOT of terms, no formula).
AI is in the news a lot. It would be nice if the Superseeker sequence guessing program could incorporate some AI to do a better job on sequences like A178256.
Tomas, or Tom, could you do the same thing for the 3-point analog, A000938? There we have a 1000-term b-file already, and an explicit formula as a complicated double sum, but no generating function. Maybe with a lot more terms a generating function would emerge. Clearly we should pound on the 3-point problem before attacking the 4-point problem.
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 8:07 PM Tom Duff <td@pixar.com> wrote:
Using Tom Rokicki's program (smarter than anything I did), I ran the A178256 table out to 1000 entries. It took about 15 seconds for the whole list. See here: http://iq0.com/b178256.txt
On Mon, Jun 15, 2020 at 1:19 PM Tomas Rokicki <rokicki@gmail.com> wrote:
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/ -- _______________________________________________ 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/ --
=Neil Sloane There are a bunch of other sequences all of this class [...]
Per Polya maybe we should start with an easier problem? Specifically: What numbers do we get if we also identify opposite edges of the grid? Then all the translations along the glued directions of a given "configuration" are the same. Moreover, gluing merges cases (iii) & (iv) since "interior" vs. "exterior" becomes arbitrary. This suggests 4 new systems of related OEIS arrays (or even 9 if we include twisted grids).
there ought to be a generating function, or some kind of formula.
Can we isolate the "edge effects" into a subexpression that modifies a symmetrical formula?
=Tom Duff using the stupidest possible program
"Things should always be made as stupid as possible, but no stupider." --Herbert Einstein
Updated table goes up to 38x38 is at http://iq0.com/lq.txt I stopped there because I need to use that machine for real work today. If anyone needs more terms (what's the chance?) I can run it some more when I get time, or just send you the C++ program and you can burn your own kilowatt hours. On Sun, Jun 14, 2020 at 2:22 PM Tom Duff <td@pixar.com> 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.
Columns of the table are m, n, # of collinear 4-tuples, # of triangles with the extra point inside, # of triangles with the extra point on and edge, # of concyclic quads total number of quads (should be the sum of the previous 4 columns unless I have a *really* stupid bug). m n collinear in on concyclic total 2 2 0 0 0 1 1 2 3 0 0 6 9 15 2 4 2 0 32 36 70 2 5 10 0 100 100 210 2 6 30 0 240 225 495 2 7 70 0 490 441 1001 2 8 140 0 896 784 1820 2 9 252 0 1512 1296 3060 2 10 420 0 2400 2025 4845 2 11 660 0 3630 3025 7315 2 12 990 0 5280 4356 10626 2 13 1430 0 7436 6084 14950 2 14 2002 0 10192 8281 20475 2 15 2730 0 13650 11025 27405 2 16 3640 0 17920 14400 35960 2 17 4760 0 23120 18496 46376 2 18 6120 0 29376 23409 58905 2 19 7752 0 36822 29241 73815 2 20 9690 0 45600 36100 91390 2 21 11970 0 55860 44100 111930 3 3 0 8 48 70 126 3 4 3 48 168 276 495 3 5 15 144 456 750 1365 3 6 45 348 990 1677 3060 3 7 105 700 1920 3260 5985 3 8 210 1280 3360 5776 10626 3 9 378 2144 5520 9508 17550 3 10 630 3400 8550 14825 27405 3 11 990 5120 12720 22090 40920 3 12 1485 7440 18216 31764 58905 3 13 2145 10448 25368 44290 82251 3 14 3003 14308 34398 60221 111930 3 15 4095 19124 45696 80080 148995 3 16 5460 25088 59520 104512 194580 3 17 7140 32320 76320 134120 249900 3 18 9180 41040 96390 169641 316251 3 19 11628 51384 120240 211758 395010 3 20 14535 63600 148200 261300 487635 3 21 17955 77840 180840 319030 595665 4 4 10 240 532 1038 1820 4 5 29 716 1312 2788 4845 4 6 72 1712 2652 6190 10626 4 7 157 3404 4972 11942 20475 4 8 302 6176 8420 21062 35960 4 9 531 10336 13452 34586 58905 4 10 874 16288 20480 53748 91390 4 11 1361 24480 29980 79930 135751 4 12 2028 35504 42288 114760 194580 4 13 2917 49748 58304 159756 270725 4 14 4070 68000 78272 216948 367290 4 15 5535 90828 103032 288240 487635 4 16 7366 118944 133284 375782 635376 4 17 9617 153104 169792 481872 814385 4 18 12348 194256 213084 609102 1028790 4 19 15625 243000 264540 759810 1282975 4 20 19514 300528 324500 937038 1581580 4 21 24087 367668 394188 1143558 1929501 5 5 64 2100 3088 7398 12650 5 6 129 4984 5964 16328 27405 5 7 248 9900 10816 31396 52360 5 8 442 17936 17768 55244 91390 5 9 747 29924 27840 90484 148995 5 10 1196 47080 41652 140372 230300 5 11 1825 70700 60040 208490 341055 5 12 2679 102460 83448 299048 487635 5 13 3818 143420 113936 415866 677040 5 14 5287 195880 151444 564284 916895 5 15 7146 261504 197568 749232 1215450 5 16 9464 342336 253512 976268 1581580 5 17 12313 440400 320896 1251176 2024785 5 18 15762 558504 400140 1580784 2555190 5 19 19895 698460 494040 1971150 3183545 5 20 24793 863596 602720 2430116 3921225 5 21 30552 1056144 728880 2964654 4780230 6 6 234 11604 11340 35727 58905 6 7 405 22936 20142 68447 111930 6 8 666 41372 32436 120106 194580 6 9 1065 68844 50004 196338 316251 6 10 1638 108132 73704 304161 487635 6 11 2439 161964 105282 451035 720720 6 12 3510 234228 144936 646116 1028790 6 13 4929 327500 196284 897712 1426425 6 14 6744 446812 258792 1217153 1929501 6 15 9027 596040 335034 1615089 2555190 6 16 11874 779464 427548 2103074 3321960 6 17 15363 1001948 538488 2693776 4249575 6 18 19572 1269720 668052 3401751 5359095 6 19 24603 1587180 820890 4240203 6672876 6 20 30552 1961544 996780 5225694 8214570 6 21 37551 2397516 1201320 6372738 10009125 7 7 660 45184 35264 130768 211876 7 8 1020 81320 55916 229034 367290 7 9 1545 135192 84960 373968 595665 7 10 2276 212152 123690 578777 916895 7 11 3283 317492 174976 857524 1353275 7 12 4605 458812 238512 1227572 1929501 7 13 6358 641108 320672 1704532 2672670 7 14 8573 874196 419618 2309893 3612280 7 15 11334 1165720 539328 3063848 4780230 7 16 14766 1523776 684316 3987962 6210820 7 17 18951 1958144 857184 5106472 7940751 7 18 23976 2480796 1057590 6446763 10009125 7 19 29981 3100188 1293696 8033580 12457445 7 20 37057 3830460 1563724 9898374 15329615 7 21 45372 4680796 1877280 12068492 18671940 8 8 1524 145648 88088 400116 635376 8 9 2220 241544 132708 652318 1028790 8 10 3154 378400 191588 1008438 1581580 8 11 4412 565636 268972 1492870 2331890 8 12 6030 816520 363876 2135534 3321960 8 13 8162 1140188 486088 2963688 4598126 8 14 10822 1553664 632076 4014258 6210820 8 15 14136 2069984 808788 5321662 8214570 8 16 18228 2703964 1022088 6923720 10668000 8 17 23184 3473064 1275036 8862546 13633830 8 18 29100 4398036 1566576 11185164 17178876 8 19 36154 5494112 1909200 13934584 21374050 8 20 44432 6785900 2299104 17164924 26294360 8 21 54138 8290100 2750808 20923864 32018910 9 9 3156 399656 198912 1062016 1663740 9 10 4362 625232 285312 1640284 2555190 9 11 5940 933808 397968 2426660 3764376 9 12 7923 1346928 534888 3469356 5359095 9 13 10509 1879888 710592 4812716 7413705 9 14 13689 2560304 918912 6516220 10009125 9 15 17631 3409300 1170672 8635232 13232835 9 16 22458 4451832 1473012 11231574 17178876 9 17 28302 5715684 1831392 14372472 21947850 9 18 35226 7235172 2242188 18134334 27646920 9 19 43446 9035816 2723376 22587172 34389810 9 20 53043 11157400 3268356 27818006 42296805 9 21 64263 13627700 3898560 33904228 51494751 10 10 5928 976552 407744 2531001 3921225 10 11 7914 1457172 566046 3742053 5773185 10 12 10350 2100112 757008 5347100 8214570 10 13 13480 2929564 1001196 7414640 11358880 10 14 17270 3987896 1288864 10035585 15329615 10 15 21930 5307956 1635414 13294975 20260275 10 16 27584 6928764 2049984 17288028 26294360 10 17 34408 8893036 2540380 22117546 33585370 10 18 42432 11253828 3099816 27900729 42296805 10 19 51966 14050288 3755414 34744497 52602165 10 20 63030 17344348 4494792 42782780 64684950 10 21 75912 21180052 5347452 52135244 78738660 11 11 10428 2172328 783344 5529310 8495410 11 12 13437 3128428 1043784 7897136 12082785 11 13 17231 4362152 1375176 10947126 16701685 11 14 21751 5935600 1763350 14812425 22533126 11 15 27249 7897756 2229312 19618448 29772765 11 16 33862 10306352 2785484 25505202 38630900 11 17 41798 13224904 3441600 32624168 49332470 11 18 51054 16731692 4186794 41147515 62117055 11 19 62034 20884928 5059248 51232666 77238876 11 20 74697 25776176 6039348 63076574 94966795 11 21 89445 31470380 7169640 76854850 115584315 12 12 17154 4500816 1388196 11272710 17178876 12 13 21747 6272032 1824288 15620648 23738715 12 14 27132 8529752 2332812 21129214 32018910 12 15 33603 11344676 2941140 27977386 42296805 12 16 41310 14799436 3665412 36364322 54870480 12 17 50493 18985088 4517508 46505662 70058751 12 18 61116 24012756 5481828 58645470 88201170 12 19 73677 29966664 6609192 73008492 109658025 12 20 88074 36976764 7871604 89873898 134810340 12 21 104823 45136568 9326568 109491916 164059875 13 13 27340 8736172 2392592 21639022 32795126 13 14 33791 11876052 3052468 29262324 44224635 13 15 41436 15790612 3838800 38738672 58409520 13 16 50440 20594552 4772360 50343268 75760620 13 17 61079 26414224 5867968 64374064 96717335 13 18 73278 33403168 7103508 81167672 121747626 13 19 87649 41678860 8546376 101035130 151348015 13 20 104009 51421004 10156944 124361628 186043585 13 21 122994 62760192 12011184 151493610 226387980 14 14 41506 16135996 3889292 39559591 59626385 14 15 50523 21446416 4883070 52358651 78738660 14 16 61022 27962776 6059716 68030862 102114376 14 17 73315 35856140 7437300 86978110 130344865 14 18 87288 45333072 8986356 109653159 164059875 14 19 103667 56554132 10792814 136476957 203927570 14 20 122188 69760952 12803924 167967466 250654530 14 21 143607 85132172 15116292 204593680 304985751 15 15 61176 28493760 6124032 69283632 103962600 15 16 73434 37141204 7588884 90006818 134810340 15 17 87645 47615220 9299760 115058880 172061505 15 18 103656 60187856 11218566 145036267 216546345 15 19 122307 75074036 13452288 180497104 269145735 15 20 143253 92591576 15933060 222123286 330791175 15 21 167370 112979748 18780912 270536760 402464790 16 16 87756 48400296 9394536 116910052 174792640 16 17 104190 62037244 11497788 149431718 223070940 16 18 122544 78403600 13851024 188343272 280720440 16 19 143774 97781436 16585516 234371150 348881876 16 20 167452 120581288 19615656 288397124 428761520 16 21 194586 147116676 23089764 351230154 521631180 17 17 123216 79500936 14058816 190977408 284660376 17 18 144282 100456632 16918092 240681534 358200540 17 19 168460 125268524 20234000 299474696 445145680 17 20 195239 154458324 23900924 368479078 547033565 17 21 225765 188429720 28100160 448729840 665485485 18 18 168420 126909720 20345400 303286461 450710001 18 19 195906 158230656 24312546 377338047 560077155 18 20 226146 195072768 28692144 464244252 688235310 18 21 260424 237949112 33701304 565311910 837222750 19 19 227208 197253768 29034288 469431366 695946630 19 20 261417 243150548 34238516 577504274 855154755 19 21 299955 296564724 40181784 703186038 1040232501 20 20 300054 299683032 40356156 710400658 1050739900 20 21 343311 365474776 47332356 864948302 1278098745 21 21 391920 445664700 55487952 1053055398 1554599970
On Sat, Jun 13, 2020 at 6:39 PM Neil Sloane <njasloane@gmail.com> wrote:
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities:
(i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area.
As a function of m and n, what are these numbers? This must be a classical problem, but I don't have enough data to check in the OEIS. (It might be called the "moduli space" of 4-tuples from an m X n grid.)
I would like the 4 tables of numbers, and exact and/or asymptotic formulas. Which is more likely, (iii) or (iv)?
I just looked at what happens if we choose three rather than four points. Now there are only two cases, collinear or not. This produces two triangles of numbers, which are now A334704 and A334705. E.g. A334704(m,n) is the number of ways to choose 3 collinear points from an m X n grid, for m >= n >= 1. Both triangles need more terms, and are lacking exact formulas (or generating functions).
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
It just occurred to me that you can probably use Brion's theorem to enumerate these sets pretty quickly. Brion's theorem lets you quickly calculate the number of lattice points inside a convex polytope. So you can enumerate the triangles inside an m x n grid and quickly add up the total number of lattice points inside them. Counting the lattice points on a triangle boundary is easy -- just a gcd per edge and add them up. Tomas Rokicki's program will give you the number of 4-collinear sets. Then subtract from binom(n*m,4) to get the number of strictly convex regions. No time to work on that right now (I still haven't retired from the Real Job), but I'll get at it this weekend. On Sun, Jun 14, 2020 at 2:22 PM Tom Duff <td@pixar.com> 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.
Columns of the table are m, n, # of collinear 4-tuples, # of triangles with the extra point inside, # of triangles with the extra point on and edge, # of concyclic quads total number of quads (should be the sum of the previous 4 columns unless I have a *really* stupid bug). m n collinear in on concyclic total 2 2 0 0 0 1 1 2 3 0 0 6 9 15 2 4 2 0 32 36 70 2 5 10 0 100 100 210 2 6 30 0 240 225 495 2 7 70 0 490 441 1001 2 8 140 0 896 784 1820 2 9 252 0 1512 1296 3060 2 10 420 0 2400 2025 4845 2 11 660 0 3630 3025 7315 2 12 990 0 5280 4356 10626 2 13 1430 0 7436 6084 14950 2 14 2002 0 10192 8281 20475 2 15 2730 0 13650 11025 27405 2 16 3640 0 17920 14400 35960 2 17 4760 0 23120 18496 46376 2 18 6120 0 29376 23409 58905 2 19 7752 0 36822 29241 73815 2 20 9690 0 45600 36100 91390 2 21 11970 0 55860 44100 111930 3 3 0 8 48 70 126 3 4 3 48 168 276 495 3 5 15 144 456 750 1365 3 6 45 348 990 1677 3060 3 7 105 700 1920 3260 5985 3 8 210 1280 3360 5776 10626 3 9 378 2144 5520 9508 17550 3 10 630 3400 8550 14825 27405 3 11 990 5120 12720 22090 40920 3 12 1485 7440 18216 31764 58905 3 13 2145 10448 25368 44290 82251 3 14 3003 14308 34398 60221 111930 3 15 4095 19124 45696 80080 148995 3 16 5460 25088 59520 104512 194580 3 17 7140 32320 76320 134120 249900 3 18 9180 41040 96390 169641 316251 3 19 11628 51384 120240 211758 395010 3 20 14535 63600 148200 261300 487635 3 21 17955 77840 180840 319030 595665 4 4 10 240 532 1038 1820 4 5 29 716 1312 2788 4845 4 6 72 1712 2652 6190 10626 4 7 157 3404 4972 11942 20475 4 8 302 6176 8420 21062 35960 4 9 531 10336 13452 34586 58905 4 10 874 16288 20480 53748 91390 4 11 1361 24480 29980 79930 135751 4 12 2028 35504 42288 114760 194580 4 13 2917 49748 58304 159756 270725 4 14 4070 68000 78272 216948 367290 4 15 5535 90828 103032 288240 487635 4 16 7366 118944 133284 375782 635376 4 17 9617 153104 169792 481872 814385 4 18 12348 194256 213084 609102 1028790 4 19 15625 243000 264540 759810 1282975 4 20 19514 300528 324500 937038 1581580 4 21 24087 367668 394188 1143558 1929501 5 5 64 2100 3088 7398 12650 5 6 129 4984 5964 16328 27405 5 7 248 9900 10816 31396 52360 5 8 442 17936 17768 55244 91390 5 9 747 29924 27840 90484 148995 5 10 1196 47080 41652 140372 230300 5 11 1825 70700 60040 208490 341055 5 12 2679 102460 83448 299048 487635 5 13 3818 143420 113936 415866 677040 5 14 5287 195880 151444 564284 916895 5 15 7146 261504 197568 749232 1215450 5 16 9464 342336 253512 976268 1581580 5 17 12313 440400 320896 1251176 2024785 5 18 15762 558504 400140 1580784 2555190 5 19 19895 698460 494040 1971150 3183545 5 20 24793 863596 602720 2430116 3921225 5 21 30552 1056144 728880 2964654 4780230 6 6 234 11604 11340 35727 58905 6 7 405 22936 20142 68447 111930 6 8 666 41372 32436 120106 194580 6 9 1065 68844 50004 196338 316251 6 10 1638 108132 73704 304161 487635 6 11 2439 161964 105282 451035 720720 6 12 3510 234228 144936 646116 1028790 6 13 4929 327500 196284 897712 1426425 6 14 6744 446812 258792 1217153 1929501 6 15 9027 596040 335034 1615089 2555190 6 16 11874 779464 427548 2103074 3321960 6 17 15363 1001948 538488 2693776 4249575 6 18 19572 1269720 668052 3401751 5359095 6 19 24603 1587180 820890 4240203 6672876 6 20 30552 1961544 996780 5225694 8214570 6 21 37551 2397516 1201320 6372738 10009125 7 7 660 45184 35264 130768 211876 7 8 1020 81320 55916 229034 367290 7 9 1545 135192 84960 373968 595665 7 10 2276 212152 123690 578777 916895 7 11 3283 317492 174976 857524 1353275 7 12 4605 458812 238512 1227572 1929501 7 13 6358 641108 320672 1704532 2672670 7 14 8573 874196 419618 2309893 3612280 7 15 11334 1165720 539328 3063848 4780230 7 16 14766 1523776 684316 3987962 6210820 7 17 18951 1958144 857184 5106472 7940751 7 18 23976 2480796 1057590 6446763 10009125 7 19 29981 3100188 1293696 8033580 12457445 7 20 37057 3830460 1563724 9898374 15329615 7 21 45372 4680796 1877280 12068492 18671940 8 8 1524 145648 88088 400116 635376 8 9 2220 241544 132708 652318 1028790 8 10 3154 378400 191588 1008438 1581580 8 11 4412 565636 268972 1492870 2331890 8 12 6030 816520 363876 2135534 3321960 8 13 8162 1140188 486088 2963688 4598126 8 14 10822 1553664 632076 4014258 6210820 8 15 14136 2069984 808788 5321662 8214570 8 16 18228 2703964 1022088 6923720 10668000 8 17 23184 3473064 1275036 8862546 13633830 8 18 29100 4398036 1566576 11185164 17178876 8 19 36154 5494112 1909200 13934584 21374050 8 20 44432 6785900 2299104 17164924 26294360 8 21 54138 8290100 2750808 20923864 32018910 9 9 3156 399656 198912 1062016 1663740 9 10 4362 625232 285312 1640284 2555190 9 11 5940 933808 397968 2426660 3764376 9 12 7923 1346928 534888 3469356 5359095 9 13 10509 1879888 710592 4812716 7413705 9 14 13689 2560304 918912 6516220 10009125 9 15 17631 3409300 1170672 8635232 13232835 9 16 22458 4451832 1473012 11231574 17178876 9 17 28302 5715684 1831392 14372472 21947850 9 18 35226 7235172 2242188 18134334 27646920 9 19 43446 9035816 2723376 22587172 34389810 9 20 53043 11157400 3268356 27818006 42296805 9 21 64263 13627700 3898560 33904228 51494751 10 10 5928 976552 407744 2531001 3921225 10 11 7914 1457172 566046 3742053 5773185 10 12 10350 2100112 757008 5347100 8214570 10 13 13480 2929564 1001196 7414640 11358880 10 14 17270 3987896 1288864 10035585 15329615 10 15 21930 5307956 1635414 13294975 20260275 10 16 27584 6928764 2049984 17288028 26294360 10 17 34408 8893036 2540380 22117546 33585370 10 18 42432 11253828 3099816 27900729 42296805 10 19 51966 14050288 3755414 34744497 52602165 10 20 63030 17344348 4494792 42782780 64684950 10 21 75912 21180052 5347452 52135244 78738660 11 11 10428 2172328 783344 5529310 8495410 11 12 13437 3128428 1043784 7897136 12082785 11 13 17231 4362152 1375176 10947126 16701685 11 14 21751 5935600 1763350 14812425 22533126 11 15 27249 7897756 2229312 19618448 29772765 11 16 33862 10306352 2785484 25505202 38630900 11 17 41798 13224904 3441600 32624168 49332470 11 18 51054 16731692 4186794 41147515 62117055 11 19 62034 20884928 5059248 51232666 77238876 11 20 74697 25776176 6039348 63076574 94966795 11 21 89445 31470380 7169640 76854850 115584315 12 12 17154 4500816 1388196 11272710 17178876 12 13 21747 6272032 1824288 15620648 23738715 12 14 27132 8529752 2332812 21129214 32018910 12 15 33603 11344676 2941140 27977386 42296805 12 16 41310 14799436 3665412 36364322 54870480 12 17 50493 18985088 4517508 46505662 70058751 12 18 61116 24012756 5481828 58645470 88201170 12 19 73677 29966664 6609192 73008492 109658025 12 20 88074 36976764 7871604 89873898 134810340 12 21 104823 45136568 9326568 109491916 164059875 13 13 27340 8736172 2392592 21639022 32795126 13 14 33791 11876052 3052468 29262324 44224635 13 15 41436 15790612 3838800 38738672 58409520 13 16 50440 20594552 4772360 50343268 75760620 13 17 61079 26414224 5867968 64374064 96717335 13 18 73278 33403168 7103508 81167672 121747626 13 19 87649 41678860 8546376 101035130 151348015 13 20 104009 51421004 10156944 124361628 186043585 13 21 122994 62760192 12011184 151493610 226387980 14 14 41506 16135996 3889292 39559591 59626385 14 15 50523 21446416 4883070 52358651 78738660 14 16 61022 27962776 6059716 68030862 102114376 14 17 73315 35856140 7437300 86978110 130344865 14 18 87288 45333072 8986356 109653159 164059875 14 19 103667 56554132 10792814 136476957 203927570 14 20 122188 69760952 12803924 167967466 250654530 14 21 143607 85132172 15116292 204593680 304985751 15 15 61176 28493760 6124032 69283632 103962600 15 16 73434 37141204 7588884 90006818 134810340 15 17 87645 47615220 9299760 115058880 172061505 15 18 103656 60187856 11218566 145036267 216546345 15 19 122307 75074036 13452288 180497104 269145735 15 20 143253 92591576 15933060 222123286 330791175 15 21 167370 112979748 18780912 270536760 402464790 16 16 87756 48400296 9394536 116910052 174792640 16 17 104190 62037244 11497788 149431718 223070940 16 18 122544 78403600 13851024 188343272 280720440 16 19 143774 97781436 16585516 234371150 348881876 16 20 167452 120581288 19615656 288397124 428761520 16 21 194586 147116676 23089764 351230154 521631180 17 17 123216 79500936 14058816 190977408 284660376 17 18 144282 100456632 16918092 240681534 358200540 17 19 168460 125268524 20234000 299474696 445145680 17 20 195239 154458324 23900924 368479078 547033565 17 21 225765 188429720 28100160 448729840 665485485 18 18 168420 126909720 20345400 303286461 450710001 18 19 195906 158230656 24312546 377338047 560077155 18 20 226146 195072768 28692144 464244252 688235310 18 21 260424 237949112 33701304 565311910 837222750 19 19 227208 197253768 29034288 469431366 695946630 19 20 261417 243150548 34238516 577504274 855154755 19 21 299955 296564724 40181784 703186038 1040232501 20 20 300054 299683032 40356156 710400658 1050739900 20 21 343311 365474776 47332356 864948302 1278098745 21 21 391920 445664700 55487952 1053055398 1554599970
On Sat, Jun 13, 2020 at 6:39 PM Neil Sloane <njasloane@gmail.com> wrote:
If we take an m X n rectangular grid of points, and choose four of them (in binomial(m*n,4) ways), there are four possibilities:
(i) the 4 points are collinear, (ii) 3 points are collinear and one point is not on that line, (iii) 3 points form a triangle of positive area and the other point is in the interior of that triangle, (iv) the 4 points form a convex quadrilateral of nonzero area.
As a function of m and n, what are these numbers? This must be a classical problem, but I don't have enough data to check in the OEIS. (It might be called the "moduli space" of 4-tuples from an m X n grid.)
I would like the 4 tables of numbers, and exact and/or asymptotic formulas. Which is more likely, (iii) or (iv)?
I just looked at what happens if we choose three rather than four points. Now there are only two cases, collinear or not. This produces two triangles of numbers, which are now A334704 and A334705. E.g. A334704(m,n) is the number of ways to choose 3 collinear points from an m X n grid, for m >= n >= 1. Both triangles need more terms, and are lacking exact formulas (or generating functions).
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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
christopher landauer -
ed pegg -
Gareth McCaughan -
Marc LeBrun -
Neil Sloane -
Tom Duff -
Tomas Rokicki