2
$\begingroup$

Square numerical matrix in which each cell is written or the number $0$ or the number $1$ is called binary. Let $T_n -$ the set of all binary matrix $m\times m, m=2,3,...,n$.

Find the probability $p_n$ that is chosen at random from the set $T_n$ of binary matrix does not have two identical rows or two identical columns.

Find $$\lim_{n\rightarrow \infty}p_n$$

My work so far:

1)$$|T_n|=2^{2\times 2}+2^{3\times 3}+...+2^{n\times n}$$ 2)

$n=2$

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

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

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

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

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

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

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

Then $$p_2=\frac9{4^2}=\frac9{16}$$

$\endgroup$
  • $\begingroup$ From your $n=2$ example, it seems that you actually want to count the matrices that don't have two identical rows or two identical columns? $\endgroup$ – joriki Jun 24 '16 at 19:07
  • $\begingroup$ @joriki: thank you! I edited. $\endgroup$ – Roman83 Jun 24 '16 at 19:29
4
$\begingroup$

You missed $\pmatrix{0&1\\1&0}$ in the $n=2$ case, so the correct count in that case is $10$.

To find the count for $n=3$, first count the matrices without identical rows: There are $8\cdot7\cdot6$. Then count the matrices without identical rows but with identical columns. Say the first two columns are identical. Then there are four different possible rows, so there are $4\cdot3\cdot2$ such matrices. There are $3$ different pairs of columns that can be identical. We can't have all three columns identical, since that would leave only $2$ different possible rows. Thus there's no overlap, and the count for $n=3$ is $8\cdot7\cdot6-3\cdot4\cdot3\cdot2=264$.

That's enough to search OEIS and find OEIS sequence A088310. It provides the two formulas

$$ \def\stir#1#2{\left[#1\atop#2\right]} n!\sum_{k=0}^n(-1)^{n-k}\stir nk\binom{2^k}n $$

and

$$ \sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}\stir ni\stir nj2^{ij}\;, $$

where $\stir nm$ is an unsigned Stirling number of the first kind that counts the number of permutations of $n$ items with $m$ disjoint cycles.

For the limit $n\to\infty$, we merely have to look at the expected number of pairs of identical rows or columns. As the number of pairs of rows and columns grows polynomially whereas the probability that two particular rows or columns are identical decays exponentially, the expected number of identical pairs goes to $0$, and thus so must the probability that there is any such identical pair; hence the probability of choosing a matrix without identical rows or columns goes to $1$.

$\endgroup$

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.