While tutoring today a student asked me about the following identity
One way to prove it is to count the number of possible triples of sets with . This can be done in two ways. First, if contain elements respectively then the number of such triples clearly equals the left-hand side of . On the other hand, since each element of must belong to one of the four disjoint regions in the picture below
the number of such triples equals precisely .
An algebraic proof can be obtained by repeated use of the binomial theorem:
Similarly, one obtains the more general identity
This also follows from the multinomial theorem since the left-hand side equals