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 $\mathcal$ 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 $\mathcal(x)$ to be the set of subsets $X$ from $\mathcal$ for which $P(X,x)$ is true and $\mathcal-x$ to be the set of subsets $X$ from $\mathcal$ for which $P(X,x)$ is false, Then $\mathcal(x)$ and $\mathcal-x$ are disjoint sets, so by the method of summation, the cardinalities are additive

:$, \mathcal, = , \mathcal(x), + , \mathcal-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

* 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:

::$+=.$

: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 $$. 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 $$.

*The number of subsets of any size-''n'' set is 2^''n''.

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

* Let ''B''_''n'' be the ''n''th 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:

::$\beginabc \\ a/bc \\ b/ac \\ c/ab \\ a/b/c \end$

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

::$B_n+C_n=B_.$

: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

References

{{DEFAULTSORT:Method Of Distinguished Element
Combinatorics
Mathematical principles