Method of distinguished element

Short description: Method in enumerative combinatorics

"Distinguished element" redirects here. For sets with pre-defined distinguished elements, see Pointed set.

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

## Contents

* 1 Definition
* 2 Examples
* 3 See also
* 4 References

## Definition

Let 𝒜 be a family of subsets of the set A and let x∈A be a distinguished element of set A. Then suppose there is a predicate P(X,x) that relates a subset X⊆A to x. Denote 𝒜(x) to be the set of subsets X from 𝒜 for which P(X,x) is true and 𝒜−x to be the set of subsets X from 𝒜 for which P(X,x) is false, Then 𝒜(x) and 𝒜−x are disjoint sets, so by the method of summation, the cardinalities are additive[1]

|𝒜|=|𝒜(x)|+|𝒜−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 (nk) 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:

(nk−1)+(nk)=(n+1k).

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 (nk−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 (nk).

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

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

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

abca/bcb/acc/aba/b/c

We see 5 partitions, containing 10 blocks, so B3 = 5 and C3 = 10\. An identity states:

Bn+Cn=Bn+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 Bn 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 Cn such blocks.

## See also

* Combinatorial principles
* Combinatorial proof

## References

1. ↑ Petkovšek, Marko; Tomaž Pisanski (November 2002). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers". University of Ljubljana Preprint Series 40 (837): 1–6. http://www.imfm.si/preprinti/PDF/00837.pdf. Retrieved 12 July 2013.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Method of distinguished element. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Method_of_distinguished_element&oldid=4154359"