We shall prove this recursively. Let be the number of ways to tile a board with the given dominoes. If the last piece is a domino, then there are ways to fill the remaining squares in the board. Otherwise, the last piece must be a domino, and there are ways to fill the remainder of the board with this piece at the front. Therefore . But note that since there is one way to tile a board (which is to not tile it at all!) and . Therefore for all .

Consider the number of ways to tile a board with squares and dominoes. We know that the number of ways to do this is . Now we need to find another way to express this quantity, and to do this we consider the location of the last square in the sequence. If this square is indeed last, then there are ways to tile the rest of the board. Otherwise, a domino must lie at the end. If a square comes immediately after this domino, then there are squares left to tile, and they can be tiled in ways. If not, however, then a domino must go here as well. Continue this pattern back until all but the first square is tiled with dominoes. Then, a square must fill this spot, and there are ways to tile the remaining "leftover" board. We have exhausted all possible cases, and adding all them up gives us , as desired.

Split the board into two boards along its middle. In a regular tiling, either two things will happen: the board will be "disconnected" or they will be "connected". If they are disconnected, then each of them can be tiled separately. Each of them can be tiled in ways, for a total of ways. Otherwise, the boards are "connected", and essentially what I mean by this is that a domino will pass through the point where the board is broken in two. In this case, this domino creates two boards, one on each side, which can also be tiled independently. This gives ways to tile the board in this case. Therefore , as desired.

As usual, consider a tiling of a board with squares and dominoes. Consider in each of the individual tilings the number of dominoes that exist in the tiling. If there are zero dominoes in the tiling, then there are ways to "place" them, and the remaining squares can be filled with squares.

Now, I claim that there exists a bijection mapping the number of ways to place dominoes in a board to the number of ways to place squares in a board. The reasoning for this is simple: I can take each of the squares that are placed and simply append another square to the right of it. That way, I will have dominoes taking up a total of squares. Now that the bijection is established, it is easy to see that the number of ways to place dominoes in a board is simply . Each of these placements establishes a unique tiling, as I can as before simply fill in the remaining untiled squares with tiles as necessary.

Therefore, the number of possible tilings with one domino is , the number of possible tilings with two dominoes is , and so on. Summing over all possible values for the number of dominoes in the tiling, we cover all possible tilings and get the requested identity

\[\begin{align*}&\sum_S 1^{a_1} 2^{a_2} \cdots n^{a_n}\\& =
{n \choose n} n^m - {n \choose n-1} (n-1)^m + \cdots +
(-1)^{n-2} {n \choose 2} 2^m + (-1)^{n-1} {n \choose 1}.\end{align*}\]

Define a new sequence such that for all . Then the LHS of the desired equality is equal to


I now claim that both sides of this equality are equivalent to the number of ways to color the squares of a board with colors such that each color is used at least once. The right hand side of the equality, while complicated, is actually PIE in disguise. is the number of ways to color the board with at most colors (since you assign one of possibilities to each of the squares), is the number of ways to color the board with at most colors (since there are ways to choose the colors to pick, and possible colors to assign to each of the squarea), is the number of ways to color the board with at most colors, and so on. Alternating adding and subtracting these expressions gives the required PIE calculation, and also unsurprisingly gives us the expression on the right.

The left hand side, while prettier to look at, is a bit more difficult to comprehend. However, it revolves around the following concept: when "reading" the coloring from left to right, for each of the colors there must exist a square for which that color is "introduced", i.e. there must exist a square for which that color appears first. This is where the sequences and come in. Consider analyzing the number of possible colors in the following way: denotes the number of squares for which only one color is used, denotes the number of squares for which only two colors can be used (i.e. the second color is introduced at the end of the set of squares), denotes the number of squares for which only three colors can be used, and so on. It is clear that this agrees with the concept described earlier, but there is a missing caveat: the th color must be used on the first square in the sequence of squares. This way, we will guarantee the fulfillment of the condition that every color is to be used at least once. This eliminates the first square from any dispute in terms of its color, and leaves us with squares to worry about. Now, note that there is one possible color for the squares collected under , two possible colors for the squares collected under , and so on, until there are possible colors for the final squares. This gives us possible colorings. However, there are ways to rearrange the colors to use (for example, we could have the sequence red-blue or the sequence blue-red for ). Therefore, for each unique sequence , there are possible colorings related to that sequence. Summing over all possible sequences gives us the total number of ways to color the board with our restrictions. But this is simply the left hand side of our equality as well!

Therefore the two sides are equal, as desired.