Finite Set

A set  whose elements can be numbered through from 1 to , for some positive integer . The number  is called the cardinal number of the set, and is often denoted  or . In other words,  is equipollent to the set . We simply say that  has  elements. The empty set is also considered as a finite set, and its cardinal number is 0.

A finite set can also be characterized as a set which is not infinite, i.e., as a set which is not equipollent to any of its proper subsets. In fact, if , and , a certain number  of elements of  do not belong to , so that .

For all , the number of subsets having exactly  elements (the so-called k-subsets, or combinations of  elements out of ) is equal to the binomial coefficient

			(1)
			(2)

Hence the number of subsets of  (i.e., the cardinal number of its power set) is

			(3)
			(4)
			(5)

by virtue of the binomial theorem.

Assigning to each k-subset of  its complement set defines a one-to-one correspondence between the set of k-subsets and the set of -subsets of . This proves the identity

(6)

The possible arrangements of the elements of  are called permutations of order . They all give rise to the same finite ordinal , since they are essentially the same; they can be transformed into each other simply by renaming the elements. The number of permutations of order  is

(7)

This is called  factorial. In fact, when constructing an arrangement by placing the elements in  given positions, there are exactly  possible choices for the first element, there are  left for the second, and so on.

With respect to this notation, the number of combinations of  elements can be written as

(8)

The elements of each k-subset give rise to  different permutations, so that the total number of possible permutations of  elements out of  is