# Is the Below Theorem true:

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

## 1 Answer

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.