With m=n and k=2 a brute force search gives the sequence of feasible/total for m=1,... as
2/2, 14/16, 108/512, 1256/65536, ...
which is not on oeis even after dividing by two to account for the label symmetry.