6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think this is closely related to the question of placing $n$ rooks on an $n\times n$ chess board such that no two attack each other. $\endgroup$ – user334732 Jul 8 '16 at 8:02
  • $\begingroup$ Except you want no $n$ rooks all attack each other. $\endgroup$ – user334732 Jul 8 '16 at 8:05
  • $\begingroup$ @RobertFrost I think my attempt where I permuted the $0$'s on the diagonal is a little similar to the rooks problem, but there ends up being multiple ways to attain the same matrix. $\endgroup$ – JasonM Jul 8 '16 at 8:11
  • $\begingroup$ Actually this is quite easy. Just enumerate the number of states in which the square is bridged. $\endgroup$ – user334732 Jul 8 '16 at 8:11
  • 1
    $\begingroup$ @RobertFrost Apologies, but I don't understand what you mean by enumerations. Do you mean a combinatorial approach? Because God knows I've tried that. $\endgroup$ – JasonM Jul 8 '16 at 8:39
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ remember to divide by $2^{n^2}$ to give the answer. $\endgroup$ – user334732 Jul 8 '16 at 14:05
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ok that all checks out now; I found a few minutes to fix the errors. $\endgroup$ – user334732 Jul 8 '16 at 11:19
  • $\begingroup$ It should give $\frac{9}{16}$ for $n=2$. $\endgroup$ – JasonM Jul 8 '16 at 19:49
  • $\begingroup$ Your solution for $H$ and $V$ is analogous to my solution for $P(\cup_{i=1}^n (v_i=1))$ and $P(\cup_{i=1}^n (u_i=1))$, but I think your solution for $|H \cap V|$ is flawed, since the end result does not yield a probability of $\frac{9}{16}$ for $n=2$. To your credit, that's where I got stuck. $\endgroup$ – JasonM Jul 9 '16 at 0:07
  • $\begingroup$ @JasonM Yeah I know it's wrong, I don't have time sadly to pick through it :( $\endgroup$ – user334732 Jul 9 '16 at 9:09
  • 1
    $\begingroup$ No worries, thank you so much for the insight $\endgroup$ – JasonM Jul 9 '16 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.