Bridges across a tiled floor

Question

A few years back, a friend of mine did a seminar on "Bridges across a tiled floor". A "bridge" was defined as a row or column of an $n \times n$ binary matrix consisting entirely of $1$'s, for example the third column and fourth row of

\begin{bmatrix} 1&0&1&0 \\ 0&0&1&0 \\ 0&1&1&1 \\ 1&1&1&1 \end{bmatrix}

The problem is to find the probability of selecting an $n\times n$ binary matrix with at least one bridge, when selecting from all $n\times n$ binary matrices. My friend made an algorithm using Markov chains for calculating it for a given $n$, but we never found a closed formula. I was wondering if there was a simple approach, or if anyone knows how to find the solution.

I made several attempts. My first attempt was to try a purely combinatorial solution, but the interconnectivity made it a bit ridiculous. I tried to solve the complementary problem by placing $0$'s on the main diagonal, permuting them, and considering all other choices for the other entries, but this resulted in multiple ways of attaining the same matrix. I tried solving the simpler problems of only column bridges or row bridges, which had simple solutions, but combining them proved difficult. And most recently (which I haven't fully fleshed out), I tried setting up a recursive relationship from the $n-1$ case to the $n$ case.

Any insight would be greatly appreciated.

Answer 1

Let $F(a,b)$ be the number with $a$ specific horizontal bridges and $b$ specific vertical bridges. The other rows and columns may or may not be bridges. Then the number of unaffected squares is $(n-a)(n-b)$ so $$F(a,b)=2^{(n-a)(n-b)}$$
Let $B(n)$ be the number of bridged arrangements.
Now, do inclusion-exclusion:

• Start with single bridges: There are $F(1,0)$ a bridge on the first row, another $F(1,0)$ with a bridge on the second row, and so on, so $nF(1,0)$ in all with a horizontal bridge (counting repetitions). There are $F(0,1)$ with a bridge on the first column, etc, so another $nF(0,1)$ with a vertical bridge.
  $nF(1,0)+nF(0,1)$.
• Two-bridge patterns have been counted twice, so that number must be subtracted. If both bridges are horizontal: there are $n\choose2$ pairs of bridges, each pair has $F(2,0)$ patterns. If both bridges are vertical, there are another ${n\choose2}F(0,2)$ patterns. If one is vertical and the other horizontal, there are $n$ choices for the horizontal one and $n$ choices for the vertical one. In every case, there are $F(1,1)$ patterns.
  Subtract ${n\choose2}F(2,0)+{n\choose1}{n\choose1}F(1,1)+{n\choose2}F(0,2)$
• Three-bridge patterns need to be added back in:
  Add ${n\choose3}F(3,0)+{n\choose2}{n\choose1}F(2,1)+{n\choose1}{n\choose2}F(1,2)+{n\choose3}F(0,3)$
• etc...

The total with no bridges has a slightly simpler formula, and that sum will be $$2^{n^2}-B(n)=\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}{n\choose i}{n\choose j}2^{(n-i)(n-j)}$$ The symmetry with $(i,j)$ replaced by $(n-i,n-j)$ gives $$\begin{array}{rcl}2^{n^2}-B(n)&=&\sum_{i=0}^n(-1)^i{n\choose i}\sum_{j=0}^n(-1)^j{n\choose j}2^{ij}\\&=&\sum_{i=0}^n(-1)^i{n\choose i}(1-2^i)^n\end{array}$$ To check for $n=1,2,3$:
$n=1:2-B(1)=0-(-1)=1\to B(1)=1$
$n=2:16-B(2)=1.0^2-2.1^2+1.3^2=7\to B(2)=9$
$n=3:512-B(3)=1.0^3+3.1^3-3.3^3+1.7^3\to B(3)=247$

Answer 2

There are $2^{n^2}$ possible states for the matrix.

How many of those are bridged?

If $\lvert H\rvert$ enumerates the horizontal bridges and $\lvert V\rvert$ enumerates the vertical ones then we have:

$$\lvert H \cup V\rvert=\lvert H\rvert +\lvert V\rvert-\lvert H \cap V\rvert$$

To enumerate $H$ I will take the complement of the cases in which there is at least one zero in every row.

For any given row, the number of cases with at least one zero is in turn the complement of the cases in which there are no zeroes in that row:

$(2^n-1)$

Combining for all n rows:

$(2^n-1)^n$

And taking the complement:

$\lvert H\rvert=2^{n^2}-(2^n-1)^n$

By symmetry:

$\lvert V\rvert=2^{n^2}-(2^n-1)^n$

Now to calculate $\lvert H \cap V\rvert$

There are $2^n-1$ ways of bridging left to right if we ignore the non-bridging squares and consider only the truth for each row of whether there is a line running from left to right.

Likewise there are also $2^n-1$ ways of bridging top to bottom if we ignore the non-bridging squares and consider only complete lines.

Multiply those to get the number of combinations of both, but subtract $(2^n-2)=-(2^n-1)+1$ since by the inclusion-exclusion principle this method double-counts that many cases. This is because for every combination of horizontal lines, every combination of vertical lines is distinctly permitted with the exception of when every horizontal line is full of 1's. When it's all 1's, every vertical line combination is impossible except for the single case where all vertical lines are bridges. So we must deduct $2^n-1$ and add $1$.

$\lvert H \cap V\rvert=(2^n-1)(2^n-1)-(2^n-1)+1=(2^n-2)(2^n-1)+1$

Now by our method $$\lvert H \cup V\rvert=\lvert H\rvert +\lvert V\rvert-\lvert H \cap V\rvert$$

$$\lvert H \cup V\rvert=2\times(2^{n^2}-(2^n-1)^n)-((2^n-2)(2^n-1))$$

Now divide this by the total number of possible arrangements to give the probability:

$$P=\frac{2\times(2^{n^2}-(2^n-1)^n)-((2^n-2)(2^n-1)+1)}{2^{n^2}}$$

Which checks out giving $\frac{1}{2}$ for $n=1$ and $\frac{7}{16}$ for $n=2$.