1
$\begingroup$

Given a $n{\times}n$ matrix $A$. $A$ can be partitioned into cells in $2^{2n-2}$ ways.

Proof

A $n{\times}n$ matrix has $n^2$ elements. The number of columns is $n$, and the number of rows is $n$. A partitioning of the matrix into cells is done by drawing lines to divide the matrix.
The number of horizontal lines is $n-1$.
The number of vertical lines is also $n-1$.
The total number of lines is $2(n-1) = 2n -2$ lines.

There is a partition that involves none of these lines, which is $A$ itself.

All the other partitions are formed by selecting any $k$ lines.

Number of partitions $N$: $$N = \sum_{i=0}^{2n-2} {(2n-2)\choose{i}} \tag{1}$$
Now, the cardinality of a power set $P(S)$ of $S$, where ${\#}S = m$ is given by the below formula:
$${\#}P(S) = 2^m \tag{2}$$
${\#}P(S)$ can alternatively be calculated as:
$${\#}P(S) = \sum_{i=0}^{m} {m\choose{i}} \tag{3}$$ Equivocating $(2)$ and $(3)$: $$\sum_{i=0}^{m} {m\choose{i}} = 2^m \tag{4}$$ Substituting $(4)$ into $(1)$: $$N = 2^{2n -2}$$.
Q.E.D

$\endgroup$
2
$\begingroup$

Yes, I think you're correct. Alternatively, once you have established that there are $2n-2$ possible lines, you could argue that each line can either be drawn or not ($2$ choices), and each set of choices of which lines to draw results in a unique partitioning. Thus, there are $2^{2n-2}$ partitions.

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