12
$\begingroup$

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

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.

  • 5
    Something that might help simplify thinking about the problem, and possibly help in search for existing literature. You can view your grid as a complete bipartite graph: $K_{m,n}$. You are selecting a subset of $h$ edges in the graph and are looking for cycles.2011-03-03
  • 0
    In other words, you want to count the number of forests of size $h$ in $K_{m,n}$.2012-02-04

1 Answers 1