Pascal's Formula

The basic recursion formula for generating binomial coefficients.

\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \]

Pascal's Triangle

The arrangement of binomial coefficients into a triangle so that each coefficient is the sum of the two above it.

                     1   1 
                   1   2   1 
                 1   3   3   1 
              1   4    6    4   1 
            1   5   10   10   5    1 


A path (aka chain ) in a graph is a sequence {x1, x2, x3, ... xk} of nodes such that {[x1, x2], [x2, x3], ... [xk-1, xk]} are edges of the graph. In a non-simple graph (one with repeated edges) it is necessary to impose the condition that no edge occur in the sequence more than it's repetion number. In a simple graph, each edge can appear at most once.


A rearrangement of the elements of a set.

Petersen Graph

A graph on ten vertices; all nodes have degree three. But, a picture is worth a thousand words...

Pigeonhole Principle

If one is distributing the elements of a set into various categories, the pigeonhole principle provides an answer to the question "What is the smallest set such that there is guaranteed to be n1 elements in the first category, or n2 elements in the second category, ... or nk elements in the k-th category?" The answer to this question is:

(n1 - 1) + (n2 - 1) + ... + (nk - 1) + 1

This picture from the lead page of this dictionary provides a way to visualize the proof of the pigeonhole principle:

Planar Graph

A graph that can be drawn in the plane so that edges do not touch except at nodes. For example the complete graph on four vertices K(4) appears at first not to be planar, but by rearranging the vertices, we see that it is.

The complete graph on 5 vertices is not planar.

The complete bipartite graph K(3,3) is also not planar

The previous assertions about the non-planarity of K(5) and K(3,3) are proved using Euler's formula . There is a theorem due to Kuratowski that a graph is planar iff it contains neither a homeomorph of K(5) nor one of K(3,3).

Planar straight line graph

An embedding of a graph formed by placing its vertices in the plane R2 and placing a straight line segment corresponding to each edge. It is not required that the edges avoid crossing each other.

Platonic Solids

The five three-dimensional regular polytopes: the regular tetrahedron, cube, octahedron, dodecahedron, and icosahedron. See George Hart's beautiful VRML models.


(a) The convex hull of a finite point set.

(b) The intersection of a finite collection of halfspaces.

These two definitions differ in that polytopes of type (a) are always bounded.


A partially-ordered set. The prototypical example of a poset is the set of subsets of a set partially-ordered by inclusion.

Projective Plane

A projective plane is derived from an affine plane by the addition of points "at infinity".

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

An On-line Dictionary of Combinatorics