Method of distinguished element

Method of distinguished element

In enumerative combinatorial mathematics, identities are sometimes established by arguments that rely on singling out one "distinguished element" of a set.

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 these 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 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 {abc} 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 B3 = 5 and C3 = 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 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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Discrete element method — A discrete element method (DEM), also called a distinct element method is any of family of numerical methods for computing the motion of a large number of particles of micrometre scale size and above. Though DEM is very closely related to… …   Wikipedia

  • rare-earth element — /rair errth /, Chem. any of a group of closely related metallic elements, comprising the lanthanides, scandium, and yttrium, that are chemically similar by virtue of having the same number of valence electrons. Also called rare earth metal. [1955 …   Universalium

  • Scientific method — …   Wikipedia

  • Philosophical method — (or philosophical methodology) is the study of how to do philosophy. A common view among philosophers is that philosophy is distinguished by the methods that philosophers follow in addressing philosophical questions. There is, however, not just… …   Wikipedia

  • chemical element — Introduction also called  element,         any substance that cannot be decomposed into simpler substances by ordinary chemical processes. Elements are the fundamental materials of which all matter is composed.       This article considers the… …   Universalium

  • Combinatorial principles — In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion exclusion principle are often used for enumerative purposes.… …   Wikipedia

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Outline of combinatorics — See also: Index of combinatorics articles The following outline is presented as an overview of and topical guide to combinatorics: Combinatorics – branch of mathematics concerning the study of finite or countable discrete structures. Contents 1… …   Wikipedia

  • Enumerative combinatorics — is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”