Variation without Repetition

combinatorics

Definition

Variation without Repetition

A variation without repetition chooses different elements from available elements and places them in order. Order matters, so and are different selections, and no element may occur twice.

For a finite set with , it is an ordered tuple

Equivalently, the tuple defines an injective position map

The number of such ordered selections is

This generalises a permutation without repetition: a variation may use any elements, while a permutation is the special case , in which every element is used.

Derivation from the Product Rule

Construct a variation from left to right, stopping after positions. The first few positions reveal the pattern directly:

The symbol names the current position. Before position , the earlier positions have been filled, so distinct elements are no longer available. The number of legal choices is therefore

Every complete variation follows one path through these stages. Each first-position choice has continuations at the second position; each of those has continuations at the third; and the construction stops after position .

For and , the complete paths are:

The product rule multiplies the stage counts:

Expanding separates the unused tail,

so division by leaves exactly the first factors:

From Combination and Permutation to Variation

A variation without repetition is a combination without repetition together with an ordering of its selected elements. It can therefore be constructed in two stages. First, choose an unordered -element subset in ways. Then arrange its elements in ways.

For and , the construction forms the following paths:

In general, the first stage has branches and every branch has continuations.

The product rule gives

Conversely, forgetting the order of a variation returns its underlying combination. Every combination has exactly variations above it, one for each ordering of its elements.

Boundary Cases

When , every element is used and the variation is a permutation without repetition, so . When , there is one empty tuple, so .

Example

Awarding three medals

Eight runners compete for gold, silver, and bronze. The positions are ordered, and one runner cannot receive two medals.

Algebraically,