Prove that $2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$ using double counting. Using a combinatorial proof (counting the same thing in different ways), show that:
$$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$
I was thinking of having some set $A$ where $|A| = n$, and then trying to find the size of the power set $|P(A\times A)|$. That will get the left hand side of the equation, but I'm having deriving the right hand side in the same way. Thanks for any help!
 A: Your idea is exactly the right one. Let $A=\{1,\ldots, n\}$. Then the cardinality of the power set of $A\times A$ is $2^{(n^2)}$.
Let $\pi:A\times A\to A$ be the first coordinate projection $\pi(a,b)=a$. For $S\subset A\times A$, we let $\pi(S)=\{\pi(x):x\in S\}$. For each $S\subset A\times A$ and $a\in \pi(S)$, we let $S_a=\{b\in A:(a,b)\in S\}$. Then each $S\subset A\times A$ can be uniquely decomposed as $$S=\bigcup_{a\in \pi(S)}\{(a,b):b\in S_a\}$$
We can construct each $S$ by first choosing an $i$, then choosing a set $T\subset A$ with $|T|=i$ (which will eventually be $\pi(S)$), and then for each $a\in T$, we choose a set to be $S_a$. Note that by definition, if $a\in \pi(S)$, then $S_a$ is non-empty (which is where the $-1$ comes from in $2^n-1$).
First choose $i$.
Then choose $T$ with $|T|=i$. There are $\binom{n}{i}$ ways to do this.
For each $a\in T$, choose an $S_a$.  There are $2^n-1$ ways to do this for an individual $a$, and there are $i$ values of $a$ in $T$, so we get $(2^n-1)^i$, one factor of $2^n-1$ for each $a$. Summing over $i$ counts the power set of $A\times A$.
A: This is already stated as a side-note in @Arthur's answer. But for me this is a prime example of a combinatorial proof. We want to show
\begin{align*}
\color{blue}{2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i}\tag{1}
\end{align*}
by counting a number of configurations in two different ways.

We assume we have an $n\times n$ chessboard and $n^2$ grains of rice.
One way: We take up to $n^2$ grains of rice and put a grain of rice on a square  of the chessboard or not. Since there are $n^2$ squares on this chessboard we have
\begin{align*}
\color{blue}{2^{\left(n^2\right)}}
\end{align*}
pairwise different configurations of a chessboard filled with zero up to $n^2$ grains of rice.
Another way: Let's say a chess board has $n$ rows and $n$ columns. We classify the chess board configurations according to the number of rows which contain at least one grain of rice. We observe

*

*The number of rows with at least on grain of rice can be $0$ up to $n$.


*There are $\binom{n}{i}$ ways to choose $i$ non-empty rows, $0\leq i\leq n$.


*Each non-empty row can be filled in $\left(2^n-1\right)$ different ways. The minus one indicates the empty row, which is not to count.

Putting these three statements into a formula we get
\begin{align*}
\color{blue}{\sum_{i=0}^n\binom{n}{i}\left(2^n-1\right)^i}
\end{align*}
pairwise different configurations to fill a chessboard with zero up to $n^2$ grains of rice and the claim (1) follows.
A: Partition $P(A\times A)$ into subsets determined by how many distinct elements appear as the first coordinate, and count the size of each subset. For instance, with $n=3$, the element $$\{(1,1),(1,2), (1,3)\}$$belongs to the $i=1$ partition because it only has $1$ as first coordinate, while $$\{(1,2), (2,2), (3,3)\}$$ belongs to $i=3$.
Translated into the world of $n\times n$ square grids filled with 0 and 1: Split into cases depending on how many columns have at least one 1 in them.
A: 
Using a combinatorial proof (counting the same thing in different ways), show that:To show:
$$2^{(n^2)} = \sum_{i=0}^n \binom{n}{i} (2^n-1)^i$$

Depending on what is intended by the phrase combinatorial proof, an alternative approach is that by the binomial theorem:
$$2^{(n^2)} = \left(2^n\right)^n = \left[ ~1 + \left(2^n - 1\right) ~\right]^n $$
$$= \sum_{i=0}^n \binom{n}{i}  \left[1^{(n-i)} \times (2^n-1)^i\right].$$
A: We have $n$ objects, each of which can be in any of the $2^{n}$ states. The summand is the number of possibilities of $n-i$ objects to be in the first state while the remaining $i$ objects are in the other $2^{n}-1$ states.
Add everything and you get $\left(2^{n}\right)^{n}$
