On a combinatorial identity of Djakov and Mityagin

Abstract

Consider a pyramid made out of unit cubes arranged in square horizontal layers, with a ledge of one cube's length around the perimeter of each layer. For any natural number k, we can count the number of ways of choosing k unit cubes from the pyramid such that no two cubes are in the same horizontal layer; we can also count the number of ways of choosing k unit cubes from the pyramid such that no two cubes come from the same vertical slice (taken parallel to a fixed edge of the pyramid) or from two adjacent slices.2 Djakov and Mityagin first established, using functional analysis, that these two quantities are always equal. Don Zagier supplied the first combinatorial proof of this result. We provide a new, more natural proof.