# P

## Pascal's Formula

The basic recursion formula for generating binomial coefficients.

## 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
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
.
.
.

## Path

A path (aka chain ) in a graph is a sequence
*{x*_{1}, x_{2}, x_{3}, ... x_{k}} of nodes
such that *{[x*_{1}, x_{2}], [x_{2}, x_{3}], ... [x_{k-1}, x_{k}]} 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.

## Permutation

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 *n*_{1} elements
in the first category, or *n*_{2} elements in the second category, ...
or *n*_{k} elements in the *k*-th category?" The answer
to this question is:

* (n*_{1} - 1) + (n_{2} - 1) + ... + (n_{k} - 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 R^{2} 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.

## Polytope

(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.

## Poset

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