Method of distinguished element explained

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

l{A} be a family of subsets of the set A and let x \in A be a distinguished element of set A . Then suppose there is a predicate P(X,x) that relates a subset X\subseteq A to x . Denote l{A}(x) to be the set of subsets X from l{A} for which P(X,x) is true and l{A}-x to be the set of subsets X from l{A} for which P(X,x) is false, Then l{A}(x) and l{A}-x are disjoint sets, so by the method of summation, the cardinalities are additive^[1] | l{A}| = | l{A}(x)| + | l{A}-x|

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

{n \choose k} 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:{n \choose k -1 } + {n \choose k} = {n +1 \choose k}.

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

{n \choose k -1 } . 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 {n \choose k} .

• The number of subsets of any size-n set is 2ⁿ.

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⁰ = 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ⁿ. 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ⁿ. Finally, the whole list of subsets of our size-(n + 1) set contains 2ⁿ + 2ⁿ = 2ⁿ⁺¹ elements.

• Let B_n be the nth Bell number, i.e., the number of partitions of a set of n members. Let C_n 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 may be written thus:

\begin{matrix}abc \ a/bc \ b/ac \ c/ab \ a/b/c \end{matrix}

We see 5 partitions, containing 10 blocks, so B₃ = 5 and C₃ = 10. An identity states:

B _{n+C} _{n=B} _{n+1} .

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_n 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_n such blocks.

See also

• Combinatorial principles
• Combinatorial proof

Notes and References

1. Petkovšek. Marko. Tomaž Pisanski. Combinatorial Interpretation of Unsigned Stirling and Lah Numbers. University of Ljubljana preprint series. November 2002. 40. 837. 1–6. 12 July 2013.