Combinatorial Derivations of Two Identities
Donald A. Steinberg · Mathematics Magazine · 1958
This paper shows, by means of two examples, the possibilities of deriving expressions by the use of the notions of permutation and combination. One of the examples is the binomial theorem. By the expansion of various polynomial expressions it is possible to derive many identities in integers, some having practical applications, and others exemplifying curious properties of numbe'rs. This method is utilized in Netto's Lehrbuch der Combinatorik to obtain a large number of such identities. Manyof these may be derived using different techniques. In this paper I propose to use the notions of permutation and combination to derive a familiar identity, the binomial theorem, and also to derive a new identity w-hich, like the binomial theorem, is an expansion of a quantity raised to a power. 1. We first see how the notions of permutation and combination can be used to give a simple proof for the binomial theorem. Consider a sequence , x2) ..,n of n variable terms and a domain la *, a I of m distinct values such that each term of the sequence can assume any of the values of the domain. Clearly the total number of actual sequences (i.e., an actual sequence being obtained by giving each xi a value from {a1,,-, am}) iS rn, We can also speak of this as the total number of arrangements of the sequence. We now partition la1, ....,ami into two subsets A and its compliment A , and specify that neither subset be empty. Let the number of elements in A be p and the number in A'.be (m-p). Let us consider the number of arrangements in which values from A are assumed by any k terms of the sequence. The expression for this is easily seen to be: (k) The remaining (m-p) values are assumed by the remaining (n-k) terms in (m-p)flk ways. Thus the total number of ways in which any k terms can assume p values is: