Beyond simple ordering: how partial permutations map subsets of a finite set

Beyond simple ordering: how partial permutations map subsets of a finite set
Image: Intellect (generated)

In short: In mathematics, a permutation rearranges every element of a set. But what happens when you only map a portion of those items? A partial permutation acts as a bridge between two equal-sized subsets, creating a precise one-to-one relationship that leaves some elements behind while perfectly ordering the rest.

At its core, a partial permutation is a bijection between two subsets of equal size within a larger finite set. If you imagine a set of n items, a partial permutation selects a specific group of elements to map onto another group of the same size. This structure is essentially a partial function that can be extended into a full permutation of the entire set.

One intuitive way to visualize this is through string representation. If you have a set of n integers, you can represent a partial permutation as a string of length n. Some positions in this string contain distinct numbers from the set, while others are filled with a special 'hole' symbol. The positions without holes define the domain, and the number occupying each position indicates where that element is mapped. For example, in a three-item set, a string like '1 ◊ 2' maps the first element to itself and the third element to the second.

The total number of these configurations grows rapidly as the size of the set increases. For a set of n items, the count is determined by a specific summation formula: the sum of i-factorial multiplied by the square of the binomial coefficient of n and i, for all values from zero to n. Each individual term in this sum represents the total count of partial permutations that have exactly i non-hole entries. Alternatively, mathematicians can calculate these values using a recurrence relation that links the count for n items to the results for n minus one and n minus two.

While the standard definition is broad, some researchers apply stricter constraints. They may require the domain or the range to consist only of the first k items of the set. In simpler combinatorial contexts, these restricted versions are sometimes referred to as k-permutations, though this terminology can be ambiguous. Regardless of the specific constraints, these structures provide a powerful way to analyze mappings that are incomplete yet mathematically rigid.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-partial-permutation.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…