Permutation without Repetition

combinatorics

Definition

Permutation without Repetition

A permutation without repetition chooses all distinct elements and places them in order. Order matters, and every element is used exactly once.

For a finite set with , it is an ordered tuple in which every element of occurs exactly once.

Equivalently, the position map

is bijective.

Derivation from the Product Rule

Construct a permutation from left to right. The first few positions reveal the pattern directly:

The symbol merely names the current position. Before position , the earlier positions have already been filled. There are of them, and because repetition is forbidden, they have consumed distinct elements. The number still available is therefore

Every complete permutation follows one path through these stages. Each first-position choice has possible continuations at the second position; each of those has continuations at the third; and so on.

For , the complete paths are:

The product rule therefore multiplies the stage counts:

Thus a set of distinct elements has exactly the factorial permutations without repetition.

Example

Three elements

The set has permutations without repetition: