The goal is to count the same objects with both left and write parts of the expression. The thing is that the formula is symmetric with respect to $$$(n,m)$$$ so the objects should be symmetric as well. I propose to count the following objects: grids of size $$$n\times m$$$ which cells are colored into black and white while each row and column contains at least one black cell. It is clear that such objects are symmetric, since we can rotate each grid by $$$90$$$ degrees and get a grid of size $$$m\times n$$$.

First, let's consider grids that may have zero black cells in the columns but have at least one black cell in the rows. We can color a certain row in $$$2^{m}-1$$$ ways, since each number in the range $$$[1, 2^m)$$$ responds for the distinct coloring in its binary representation with at least one black cell. As we are not interested about the columns, we may count each row independently and get $$$(2^m-1)^n$$$ such grids.

However, it isn't that easy to get rid of those completely white columns. One of the ways to do that is to use inclusion-exclusion principle. In the $$$k^\text{th}$$$ term we count the number of grids that have at least $$$k$$$ completely white columns, what means that some of the columns must be fixed and contain zero black cells. We can fix them in $$$\binom{m}{k}$$$ ways. Now we have the same problem but with the grid of size $$$n\times(m-k)$$$ and we can apply our previous formula.

At last we get the formula $$$\displaystyle \sum_{k=0}^{m}(-1)^k\binom{m}{k}(2^{m-k}-1)^n$$$ for counting the desired grids.

We may count the same objects with by fixing completely white rows and get the left part of the formula.

From my proof we see what objects does that formula counts. Moreover, I found two more types of objects counted by that expression:

If you have other objects counted by this formula, feel free to share about them in the comments.