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$.