pigeonhole principle


Also found in: Wikipedia.

pigeonhole principle

[′pij·ən‚hōl ‚prin·sə·pəl]
(mathematics)
The principle, that if a very large set of elements is partitioned into a small number of blocks, then at least one block contains a rather large number of elements. Also known as Dirichlet drawer principle.
References in periodicals archive ?
This book supplies students with 112 introductory to intermediate combinatorial problems drawn from the AwesomeMath summer program, as well as tools for solving counting problems, proof techniques, and examples related counting basics, permutations and combinations, multinomials, the principle of inclusion-exclusion, Pascal's triangle and the binomial theorem, the double counting principle, the pigeonhole principle, induction, recurrence relations, graph theory, invariants, combinatorial geometry, generating functions, and probabilities and probabilistic method.
In this work, we present two techniques to solve AAPSP The first utilizes a compact prefix tree in solving AAPSP, while our second technique takes advantage of the well-known pigeonhole principle and the minimal length for an overlap in order to identify potential overlap matches.
According to the pigeonhole principle, at least three edges are the same line.
Then it follows by the pigeonhole principle that there is one vertex of H with degree at least n - 2 and another vertex of H of degree at least n - 3.
Since deg([v.sub.1]) + deg([v.sub.2]) + deg([v.sub.3]) = 10, it follows by the pigeonhole principle that at least one vertex in [V.sub.1] has degree 4; suppose this vertex is [v.sub.1].
The topics include the multiplication principle, the distribution of balls into boxes, the binomial expansion, the principles of inclusion and exclusion, the pigeonhole principle, and the Catalan numbers.
They begin with a few examples, just to let students get a feel for it, then look at fundamentals of enumeration; the pigeonhole principle and Ramsey's theorem; the principle of inclusion and exclusion; generating functions and recurrence relations; Catalan, Bell, and Stirling numbers; symmetries and the Polya-Redfield method; graph theory; coding theory; Latin squares; balanced incomplete block designs; and linear algebra methods in combinatorics.
We show that in the classical examples of the Pigeonhole Principle, Tseitin graph tautologies, and random k-CNF's, these expansion properties are quite simple to prove (indeed, they comprised in some implicit way the simple part of the existing lower bound proofs).
The topics are basic counting methods, generating functions, the pigeonhole principle, Ramsey theory, error-correcting codes, and combinatorial designs.
By the pigeonhole principle, at least one of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains two vertices from [T.sub.i](w) and two vertices from [T.sub.j](w) for some i, j [member of] {2,3,4} with i [not equal to] j.
They explain such topics as combinatorics is, permutations and combinations, the inclusion-exclusion principle, generating functions and recurrence relations, trees, group actions, and Dirichlet's pigeonhole principle. The exercises are presented in pairs, with elaborate solutions provided for one of them.
The book's ten chapters cover induction, combinatorics, the whole numbers, geometric transformations, and inequalities, in addition to graphs, the pigeonhole principle, complex numbers and polynomials, rational approximations and mathematics at the computer.