Random points in a rectangular grid defining a closed path

Suppose we have a $n\times m$ rectangular grid (namely: $nm$ points disposed as a matrix with $n$ rows and $m$ columns).

We randomly pick $h$ different points in the grid, where every point is equally likely.

If only horizontal or vertical movements between two points are allowed, what is the probability that the points define at least one closed path?

ps: we can suppose $m=n$ to simplify

For example, let $n=m=4$ and $h=6$. 1 denotes a selected point, 0 a non-selected one.

These $6$ points define a closed path:

1 0 0 1

0 0 0 0

1 1 0 0

0 1 0 1

as these $6$ do (the $4$ in the bottom-right corner):

1 0 0 1

0 0 0 0

0 1 0 1

while the following $6$ points do not:

1 0 0 0

0 0 0 1

1 1 0 0

0 1 0 1

Substantially, the $h$ points define a closed path if and only if there exist a subset of these $h$ points such that every point in the subset has one other point of the subset on the same row and one on the same column.

Thanks for your help.

Solution 1:

As Aryabhata comments, it's equivalent to counting the number $f_{m,n,h}$ of $h$-edge acyclic subgraphs of $K_{m,n}$. I managed to find a method to compute $f_{m,n,h}$. The first observation is \[f_{m,n,h}=\sum_{i=0}^m \sum_{j=0}^n {m \choose i} {n \choose j} w_{i,j,h}\] where $w_{m,n,h}$ is the number of $h$-edge acyclic subgraphs of $K_{m,n}$ without isolated vertices. Since $w_{m,n,h}=0$ when $m \geq h$ or $n \geq h$, for fixed $h$, this formula can be run in time $O(\log(mn))$, by pre-computing the non-zero values of $w_{m,n,h}$. It seems, however, that it's not so easy to compute $f_{m,n,h}$ for general $h$.

We can make some improvements to this formula by:

deriving a formula for $w_{m,n,h}$ via decompositions into disjoint subgraphs,
considering the number of $h$-edge acyclic subgraphs of $K_{m,n}$ without isolated vertices and leaf vertices on the "$n$" side,
introducing a symmetry breaking condition.

I implemented this algorithm and used it to compute all non-zero values of $f_{m,n,h}$ with $m,n \leq 50$. The source code is here. In an effort to describe this algorithm in detail, I ended up writing a paper Computing the number of h-edge spanning forests in complete bipartite graphs (2014).

Here are the first few values:

[1,1] 1 1 
[1,2] 1 2 1 
[1,3] 1 3 3 1 
[1,4] 1 4 6 4 1 
[1,5] 1 5 10 10 5 1 
[1,6] 1 6 15 20 15 6 1 
[1,7] 1 7 21 35 35 21 7 1 
[1,8] 1 8 28 56 70 56 28 8 1 
[1,9] 1 9 36 84 126 126 84 36 9 1 
[1,10] 1 10 45 120 210 252 210 120 45 10 1 
[2,2] 1 4 6 4 
[2,3] 1 6 15 20 12 
[2,4] 1 8 28 56 64 32 
[2,5] 1 10 45 120 200 192 80 
[2,6] 1 12 66 220 480 672 544 192 
[2,7] 1 14 91 364 980 1792 2128 1472 448 
[2,8] 1 16 120 560 1792 4032 6272 6400 3840 1024 
[2,9] 1 18 153 816 3024 8064 15456 20736 18432 9728 2304 
[2,10] 1 20 190 1140 4800 14784 33600 55680 65280 51200 24064 5120 
[3,3] 1 9 36 84 117 81 
[3,4] 1 12 66 220 477 648 432 
[3,5] 1 15 105 455 1335 2673 3375 2025 
[3,6] 1 18 153 816 3015 7938 14499 16524 8748 
[3,7] 1 21 210 1330 5922 19278 45738 75330 76545 35721 
[3,8] 1 24 276 2024 10542 40824 118692 253368 373977 338256 139968 
[3,9] 1 27 351 2925 17442 78246 268758 701298 1345005 1778031 1436859 531441 
[3,10] 1 30 435 4060 27270 138996 549990 1691280 3969405 6845310 8129079 5904900 1968300 
[4,4] 1 16 120 560 1784 3936 5632 4096 
[4,5] 1 20 190 1140 4785 14544 31520 44800 32000 
[4,6] 1 24 276 2024 10536 40704 117376 244224 331776 221184 
[4,7] 1 28 378 3276 20349 95256 341712 928512 1822464 2308096 1404928 
[4,8] 1 32 496 4960 35792 196672 842240 2811904 7147520 13058048 15204352 8388608 
[4,9] 1 36 630 7140 58689 370080 1839936 7266816 22556160 53272576 89800704 95551488 47775744 
[4,10] 1 40 780 9880 91120 648288 3667200 16696320 61009920 175636480 383451136 593756160 576716800 262144000 
[5,5] 1 25 300 2300 12550 51030 155900 347500 515625 390625 
[5,6] 1 30 435 4060 27255 138606 544525 1641000 3645000 5400000 4050000 
[5,7] 1 35 595 6545 52150 318122 1524530 5764750 16900625 36596875 52521875 37515625 
[5,8] 1 40 780 9880 91110 647928 3660300 16607400 60170625 169700000 352400000 480000000 320000000 
[5,9] 1 45 990 14190 148635 1206999 7847220 41469300 178356375 616146875 1656168750 3257718750 4157578125 2562890625 
[5,10] 1 50 1225 19600 229850 2098060 15421050 92925000 461728125 1881031250 6165578125 15674375000 28953125000 34375000000 19531250000 
[6,6] 1 36 630 7140 58680 369792 1834992 7210080 22083840 50388480 77262336 60466176 
[6,7] 1 42 861 11480 111615 838698 5022031 24263028 94246740 287884800 657456912 1008189504 784147392 
[6,8] 1 48 1128 17296 194160 1693824 11870272 67942272 318691584 1212710400 3642236928 8169652224 12230590464 9172942848 
[6,9] 1 54 1431 24804 315711 3135510 25159545 166283280 912183120 4140720000 15318167904 44729853696 97138911744 139586167296 99179645184 
[6,10] 1 60 1770 34220 486960 5423712 49015360 367096320 2302629120 12114178560 53031822336 189460684800 532998144000 1108546560000 1511654400000 1007769600000 
[7,7] 1 49 1176 18424 211435 1887039 13542816 79497264 383225031 1503254095 4674900664 10930062696 17230990189 13841287201 
[7,8] 1 56 1540 27720 366702 3789240 31681300 218620760 1255792825 5993472240 23447436096 73006381056 171071057920 269858570240 215886856192 
[7,9] 1 63 1953 39711 594909 6984243 66640413 528138963 3516498531 19723392829 92605693635 357804004509 1101151227519 2544938108433 3938980639167 3063651608241 
[7,10] 1 70 2415 54740 915950 12040644 129071950 1154594080 8734901805 56204359750 307067393059 1410568820220 5339441040500 16075559360000 36194714850000 54189129400000 40353607000000 
[8,8] 1 64 2016 41664 634592 7577472 73574144 593773056 4029819264 23069699072 110763376640 438772432896 1389556137984 3322157203456 5360119185408 4398046511104 
[8,9] 1 72 2556 59640 1027782 13923000 153923196 1421475912 11117737665 74098919744 420440041728 2013081735168 7981887578112 25343121162240 60740934303744 98077104930816 80244904034304 
[8,10] 1 80 3160 82160 1580320 23944256 296880640 3086266880 27312138880 207462978560 1355573469184 7587975987200 35975515340800 141460766720000 445225369600000 1055286886400000 1677721600000000 1342177280000000 
[9,9] 1 81 3240 85320 1662444 25521804 320717880 3380400216 30345929910 233984870262 1553345659224 8845120243512 42730719804108 171593700184620 553227160200264 1348883466233256 2219048868131217 1853020188851841 
[9,10] 1 90 4005 117480 2553570 43809948 616649250 7302228120 73952056845 646947951130 4911678171801 32346150078960 183665091934800 887748334704000 3573356139900000 11554377645600000 28238648976000000 46490458680000000 38742048900000000 
[10,10] 1 100 4950 161700 3919200 75093120 1182753600 15712656000 179127216000 1772146496000 15311555436800 115760058048000 763841356800000 4365392640000000 21306528000000000 86798400000000000 284496000000000000 705600000000000000 1180000000000000000 1000000000000000000

The above lists $[m,n]$ followed by $f_{m,n,h}$ for $0 \leq h \leq m+n-1$ when $n \geq m \geq 1$. Note that $f_{m,n,m+n-1}=m^{n-1}n^{m-1}$, which counts spanning trees in $K_{m,n}$ (see Kirchoff's Matrix-Tree Theorem). Adding more edges introduces a cycle, so $f_{m,n,h}=0$ when $h \geq m+n$.