XLIV OM - I - Problem 11

In six different cells of an $ n \times n $ table, we place a cross; all arrangements of crosses are equally probable. Let $ p_n $ be the probability that in some row or column there will be at least two crosses. Calculate the limit of the sequence $ (np_n) $ as $ n \to \infty $.
Elementary events are determined by six-element subsets of the set of $n^2$ cells of the table; there are $\binom{n^2}{6}$ of them. Let $\mathcal{Z}$ be the complementary event to the event considered in the problem. The configurations favorable to event $\mathcal{Z}$ are obtained as follows: we place the first cross in any arbitrarily chosen cell: here we have $n^2$ possibilities. We then "cross out" the entire horizontal row and the entire vertical row intersecting at the cell where we placed the first cross, and place the second cross in any of the remaining cells: thus, we now have $(n-1)^2$ possibilities. We repeat this scheme four more times and obtain the number of possibilities equal to $n^2 (n -1 )^2 (n - 2)^2 (n - 3)^2 (n - 4 )^2 (n - 5)^2$. This number must still be divided by $6!$ (the number of permutations of a six-element set) to make the reasoning independent of the order of placing the crosses.
Thus, the probability of event $\mathcal{Z}$ (equal to $1 - p_n$) is

One should not multiply all these factors! Let us denote the numerator of the obtained fraction by $L_n$, and the denominator by $M_n$. It is enough to notice that

where $\phi(n)$ and $f(n)$ are polynomials (in the variable $n$), of degree (at most) 4 and 10, respectively; similarly,

where $\psi(n)$ and $g(n)$ are polynomials (in the variable $n$), of degree (at most) 8 and 10, respectively. Therefore,

Since the polynomials $f(n)$ and $g(n)$ are of degree (at most) tenth, then

and consequently, $\displaystyle \lim_{n\to \infty} np_n = 30$.