pigeonhole principle

pigeonhole principle
A theorem which states that there does not exist an injective function on finite sets whose codomain is smaller than its domain.

Wikipedia foundation.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Pigeonhole principle — A photograph of pigeons in holes. Here there are n = 10 pigeons in m = 9 holes, so by the pigeonhole principle, at least one hole has more than one pigeon: in this case, both of the top corner holes contain two pigeons. The principle says nothing …   Wikipedia

  • Pigeonhole — may refer to:*Pigeonholes, nesting spaces formed in a dovecote (also spelt dovecot or doocot ) *Pigeonhole, one of the boxes in a pigeon coop *Pigeonhole principle, a mathematical principle *Pigeonhole sort, a sorting algorithm *Pigeonhole… …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

  • pigeonhole — 1. noun a) One of an array of compartments for sorting post, messages etc. at an office, or college (for example). Fred was disappointed at the lack of post in his pigeonhole. b) A hole, or roosting place for pigeons. 2. verb To categorize;… …   Wiktionary

  • Dirichlet's principle — Not to be confused with Pigeonhole principle. In mathematics, Dirichlet s principle in potential theory states that, if the function u(x) is the solution to Poisson s equation on a domain Ω of with boundary condition then u can be obtained as the …   Wikipedia

  • 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

  • Ramsey theory — This article provides an introduction. For a more detailed and technical article, see Ramsey s theorem. Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in… …   Wikipedia

  • Lossless data compression — is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be… …   Wikipedia

  • Twelvefold way — In combinatorics, the twelvefold way is a name given to a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and… …   Wikipedia

  • Auxiliary function — In mathematics, auxiliary functions are an important construction in transcendental number theory. They are functions which appear in most proofs in this area of mathematics and that have specific, desirable properties, such as taking the value… …   Wikipedia

Share the article and excerpts

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