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