Method of distinguished element


In the mathematical field of enumerative combinatorics, identities are sometimes established by arguments that rely on singling out one "distinguished element" of a set.

Definition

Let be a family of subsets of the set and let be a distinguished element of set. Then suppose there is a predicate that relates a subset to. Denote to be the set of subsets from for which is true and to be the set of subsets from for which is false, Then and are disjoint sets, so by the method of summation, the cardinalities are additive
Thus the distinguished element allows for a decomposition according to a predicate that is a simple form of a divide and conquer algorithm. In combinatorics, this allows for the construction of recurrence relations. Examples are in the next section.

Examples

  • The binomial coefficient is the number of size-k subsets of a size-n set. A basic identity—one of whose consequences is that the binomial coefficients are precisely the numbers appearing in Pascal's triangle—states that:
  • The number of subsets of any size-n set is 2n.
  • Let Bn be the nth Bell number, i.e., the number of partitions of a set of n members. Let Cn be the total number of "parts" among all partitions of that set. For example, the partitions of the size-3 set may be written thus: