method of distinguished element

Let $\backslash mathcal\{A\}$ be a family of subsets of the set $A$ and let $x\; \backslash in\; A$ be a distinguished element of set $A$. Then suppose there is a predicate $P(X,x)$ that relates a subset $X\backslash subseteq\; A$ to $x$. Denote $\backslash mathcal\{A\}(x)$ to be the set of subsets $X$ from $\backslash mathcal\{A\}$ for which $P(X,x)$ is true and $\backslash mathcal\{A\}-x$ to be the set of subsets $X$ from $\backslash mathcal\{A\}$ for which $P(X,x)$ is false, Then $\backslash mathcal\{A\}(x)$ and $\backslash mathcal\{A\}-x$ are disjoint sets, so by the method of summation, the cardinalities are additive{{cite journal|last=Petkovšek|first=Marko|author2=Tomaž Pisanski|title=Combinatorial Interpretation of Unsigned Stirling and Lah Numbers|journal=University of Ljubljana Preprint Series|date=November 2002|volume=40|issue=837|pages=1–6|url=http://www.imfm.si/preprinti/PDF/00837.pdf|accessdate=12 July 2013}}

:$|\backslash mathcal\{A\}|\; =\; |\backslash mathcal\{A\}(x)|\; +\; |\backslash mathcal\{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.

• The binomial coefficient $\{n\; \backslash 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\; \backslash choose\; k-1\}+\{n\; \backslash choose\; k\}=\{n+1\; \backslash 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\; \backslash 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\; \backslash 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 {a, b, c} may be written thus:

::$\backslash begin\{matrix\}abc\; \backslash \backslash \; a/bc\; \backslash \backslash \; b/ac\; \backslash \backslash \; c/ab\; \backslash \backslash \; a/b/c\; \backslash 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.

• Combinatorial principles
• Combinatorial proof

{{reflist}}

{{DEFAULTSORT:Method Of Distinguished Element}}

Category:Combinatorics

Category:Mathematical principles