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 <math>\mathcal{A}</math> be a family of subsets of the set <math>A</math> and let <math>x \in A</math> be a distinguished element of set <math>A</math>. Then suppose there is a predicate <math>P(X,x)</math> that relates a subset <math>X\subseteq A</math> to <math>x</math>. Denote <math>\mathcal{A}(x)</math> to be the set of subsets <math>X</math> from <math>\mathcal{A}</math> for which <math>P(X,x)</math> is true and <math>\mathcal{A}-x</math> to be the set of subsets <math>X</math> from <math>\mathcal{A}</math> for which <math>P(X,x)</math> is false, Then <math>\mathcal{A}(x)</math> and <math>\mathcal{A}-x</math> are disjoint sets, so by the method of summation, the cardinalities are additive
:<math>|\mathcal{A}| = |\mathcal{A}(x)| + |\mathcal{A}-x|</math>
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 <math>{n \choose k}</math> 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:
::<math>{n \choose k-1}+{n \choose k}={n+1 \choose k}.</math>
:Proof: In a size-(n + 1) set, choose one distinguished element. The set of all size-k subsets contains: (1) all size-k subsets that do contain the distinguished element, and (2) all size-k subsets that do not contain the distinguished element. If a size-k subset of a size-(n + 1) set does contain the distinguished element, then its other k − 1 elements are chosen from among the other n elements of our size-(n + 1) set. The number of ways to choose those is therefore <math>{n \choose k-1}</math>. If a size-k subset does not contain the distinguished element, then all of its k members are chosen from among the other n "non-distinguished" elements. The number of ways to choose those is therefore <math>{n \choose k}</math>.
- The number of subsets of any size-n set is 2<sup>n</sup>.
:Proof: We use mathematical induction. The basis for induction is the truth of this proposition in case n = 0. The empty set has 0 members and 1 subset, and 2<sup>0</sup> = 1. The induction hypothesis is the proposition in case n; we use it to prove case n + 1. In a size-(n + 1) set, choose a distinguished element. Each subset either contains the distinguished element or does not. If a subset contains the distinguished element, then its remaining elements are chosen from among the other n elements. By the induction hypothesis, the number of ways to do that is 2<sup>n</sup>. If a subset does not contain the distinguished element, then it is a subset of the set of all non-distinguished elements. By the induction hypothesis, the number of such subsets is 2<sup>n</sup>. Finally, the whole list of subsets of our size-(n + 1) set contains 2<sup>n</sup> + 2<sup>n</sup> = 2<sup>n+1</sup> elements.
- Let B<sub>n</sub> be the nth Bell number, i.e., the number of partitions of a set of n members. Let C<sub>n</sub> be the total number of "parts" (or "blocks", as combinatorialists often call them) among all partitions of that set. For example, the partitions of the size-3 set {a, b, c} may be written thus:
::<math>\begin{matrix}abc \\ a/bc \\ b/ac \\ c/ab \\ a/b/c \end{matrix}</math>
:We see 5 partitions, containing 10 blocks, so B<sub>3</sub> = 5 and C<sub>3</sub> = 10. An identity states:
::<math>B_n+C_n=B_{n+1}.</math>
:Proof: In a size-(n + 1) set, choose a distinguished element. In each partition of our size-(n + 1) set, either the distinguished element is a "singleton", i.e., the set containing only the distinguished element is one of the blocks, or the distinguished element belongs to a larger block. If the distinguished element is a singleton, then deletion of the distinguished element leaves a partition of the set containing the n non-distinguished elements. There are B<sub>n</sub> ways to do that. If the distinguished element belongs to a larger block, then its deletion leaves a block in a partition of the set containing the n non-distinguished elements. There are C<sub>n</sub> such blocks.
See also
- Combinatorial principles
- Combinatorial proof