Method of distinguished element

Last updated February 18, 2021

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

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

Examples

The binomial coefficient ${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 {a, b, c} 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.

Related Research Articles

In mathematics, a combination is a selection of items from a collection, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements, the number of k-combinations is equal to the binomial coefficient

In combinatorial mathematics, a Steiner system is a type of block design, specifically a t-design with λ = 1 and t ≥ 2.

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for analysing discrete structures in terms of generating functions. Examples of discrete structures are (finite) graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by the Canadian group of people around André Joyal.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice.

In combinatorics, the Erdős–Ko–Rado theorem of Paul Erdős, Chao Ko, and Richard Rado is a theorem on intersecting set families.

Partition of a set Mathematical ways to group elements of a set

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.

In elementary set theory, Cantor's theorem is a fundamental result which states that, for any set $, the set of all subsets of has a strictly greater cardinality than itself. For finite sets, Cantor's theorem can be seen to be true by simple enumeration of the number of subsets. Counting the empty set as a subset, a set with members has a total of subsets, so that if then, and the theorem holds because for all non-negative integers.$

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as

In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of its application to the theory of free probability. The number of noncrossing partitions of a set of n elements is the nth Catalan number. The number of noncrossing partitions of an n-element set with k blocks is found in the Narayana number triangle.

In combinatorics, an abstract simplicial complex (ASC) is a family of sets that is closed under taking subsets, i.e., every subset of a set in the family is also in the family. It is a purely combinatorial description of the geometric notion of a simplicial complex. For example, in a 2-dimensional simplicial complex, the sets in the family are the triangles, their edges, and their vertices.

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

In combinatorics, bijective proof is a proof technique that finds a bijective function $f : A \to B$ between two finite sets $A$ and $B$ , or a size-preserving bijective function between two combinatorial classes, thus proving that they have the same number of elements, $| A | = | B |$ . One place the technique is useful is where we wish to know the size of $A$ , but can find no direct way of counting its elements. By establishing a bijection from $A$ to some $B$ solves the problem if $B$ is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets.

In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.

In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer.

In theoretical computer science, the term isolation lemma refers to randomized algorithms that reduce the number of solutions to a problem to one, should a solution exist. This is achieved by constructing random constraints such that, with non-negligible probability, exactly one solution satisfies these additional constraints if the solution space is not empty. Isolation lemmas have important applications in computer science, such as the Valiant–Vazirani theorem and Toda's theorem in computational complexity theory.

A Maker-Breaker game is a kind of positional game. Like most positional games, it is described by its set of positions/points/elements and its family of winning-sets. It is played by two players, called Maker and Breaker, who alternately take previously-untaken elements.

In combinatorial mathematics and extremal set theory, the Sauer–Shelah lemma states that every family of sets with small VC dimension consists of a small number of sets. It is named after Norbert Sauer and Saharon Shelah, who published it independently of each other in 1972. The same result was also published slightly earlier and again independently, by Vladimir Vapnik and Alexey Chervonenkis, after whom the VC dimension is named. In his paper containing the lemma, Shelah gives credit also to Micha Perles, and for this reason the lemma has also been called the Perles–Sauer–Shelah lemma.

References

↑ Petkovšek, Marko; Tomaž Pisanski (November 2002). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers" (PDF). University of Ljubljana preprint series. 40 (837): 1–6. Retrieved 12 July 2013.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Petkovsek2002-1] Petkovšek, Marko; Tomaž Pisanski (November 2002). "Combinatorial Interpretation of Unsigned Stirling and Lah Numbers" (PDF). University of Ljubljana preprint series. 40 (837): 1–6. Retrieved 12 July 2013.

[1]

Method of distinguished element

Contents

Definition

Examples

See also

Related Research Articles

References