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
(9)
|