Permutation Rank: Definition, Formula & Example

A permutation rank identifies the position of a permutation within a specified ordering of all permutations of the same elements.

For distinct elements arranged in ascending reference order, lexicographic ranking is commonly calculated with factorial weights. For a permutation of n distinct elements:

Rank₀ = c₁(n-1)! + c₂(n-2)! + … + cₙ0!

where cᵢ is the number of unused smaller elements that could appear at position i.

This gives a zero-based rank, ranging from:

0 to n! – 1

If positions are numbered starting at 1 instead:

Rank₁ = Rank₀ + 1

For example, the permutation:

3, 1, 4, 2

of:

1, 2, 3, 4

has zero-based lexicographic rank:

13

and one-based position:

14

The ranking convention matters. A permutation does not have one universal numeric rank unless the underlying element order and zero-based or one-based convention are specified.

What Is a Permutation Rank?

A permutation is an ordering of distinct elements.

For the elements:

1, 2, 3

the six permutations in lexicographic order are:

Thus:

rank₀(2,3,1) = 3

while its one-based position is:

4

Permutation ranking converts an ordering into an integer index.

Why the Ranking Convention Matters

Consider:

2, 3, 1

If the first permutation is assigned rank 0, its rank is:

3

If the first permutation is assigned rank 1, its position is:

4

Both statements can be correct under different conventions.

The safest approach is to state explicitly:

zero-based lexicographic rank

or:

one-based lexicographic position

before calculating.

What Is Lexicographic Order?

Lexicographic order is analogous to dictionary order.

For:

1, 2, 3, 4

all permutations beginning with 1 come before permutations beginning with 2.

Within the 1 group, permutations beginning:

1,2,…

come before those beginning:

1,3,…

and so on.

The first few permutations are:

1,2,3,4

1,2,4,3

1,3,2,4

1,3,4,2

1,4,2,3

1,4,3,2

Then permutations beginning with 2 start.

This hierarchical structure is exactly why factorial weights appear in the ranking formula.

How Many Permutations Have a Fixed First Element?

For n distinct elements, once the first position is fixed, there are:

(n-1)!

ways to arrange the remaining elements.

For four elements:

(4-1)! = 3!

= 6

Therefore each first-element block contains:

6 permutations

This is the foundation of factorial-based ranking.

Permutation Rank Formula

For a permutation:

p₁, p₂, …, pₙ

define cᵢ as the number of currently unused elements smaller than pᵢ.

Then:

Rank₀ = Σ cᵢ(n-i)!

Written explicitly:

Rank₀ = c₁(n-1)! + c₂(n-2)! + … + cₙ0!

The digits:

c₁, c₂, …, cₙ

form what is commonly called a Lehmer-code representation of the permutation.

Each digit records how many smaller available choices were skipped at that position.

Why Factorials Appear

Suppose five distinct elements remain and you choose the third-smallest available element for the next position.

You have skipped:

2

smaller possibilities.

Each skipped choice would allow the remaining four elements to be arranged in:

4!

ways.

Therefore those skipped blocks contribute:

2 × 4!

to the rank.

This same logic repeats at each position.

Example: Rank 3,1,4,2

Rank the permutation:

3,1,4,2

relative to the ordered elements:

1,2,3,4

First Position

Current element:

3

Unused elements smaller than 3:

1,2

Count:

c₁ = 2

Weight:

3! = 6

Contribution:

2 × 6 = 12

Second Position

Remaining elements are:

1,2,4

Current element:

1

There are no smaller unused elements.

c₂ = 0

Contribution:

0 × 2! = 0

Third Position

Remaining:

2,4

Current element:

4

One unused element is smaller:

2

Therefore:

c₃ = 1

Contribution:

1 × 1! = 1

Fourth Position

Only:

2

remains.

Therefore:

c₄ = 0

Contribution:

0 × 0! = 0

Add:

Rank₀ = 12 + 0 + 1 + 0

= 13

Therefore:

Zero-based permutation rank = 13

and:

One-based position = 14

Why 0! Appears

The final factorial weight is:

0!

By definition:

0! = 1

But the final Lehmer digit is necessarily zero because only one element remains.

Therefore the final term contributes:

0 × 1 = 0

The factorial definition is developed more generally under factorial.

Another Permutation Rank Example

Find the zero-based rank of:

2,4,1,3

from:

1,2,3,4

For 2:

Smaller unused elements:

1

so:

c₁ = 1

Contribution:

1 × 3! = 6

For 4, remaining values are:

1,3,4

Smaller unused values than 4:

1,3

so:

c₂ = 2

Contribution:

2 × 2! = 4

For 1:

c₃ = 0

For 3:

c₄ = 0

Therefore:

Rank₀ = 6 + 4

= 10

So:

rank₀(2,4,1,3) = 10

and its one-based position is:

11

Example With Five Elements

Rank:

4,1,5,2,3

relative to:

1,2,3,4,5

For 4, smaller unused elements are:

1,2,3

so:

c₁ = 3

Contribution:

3 × 4!

= 3 × 24

= 72

Remaining:

1,2,3,5

Current:

1

so:

c₂ = 0

Remaining after 1:

2,3,5

Current:

5

Smaller available values:

2,3

so:

c₃ = 2

Contribution:

2 × 2!

= 4

Remaining:

2,3

Current:

2

so:

c₄ = 0

Final contribution:

0

Therefore:

Rank₀ = 72 + 4

= 76

So:

Zero-based rank = 76

and:

One-based position = 77

Maximum Permutation Rank

There are:

n!

permutations of n distinct elements.

Therefore the zero-based ranks run from:

0 through n! – 1

The maximum rank belongs to the descending permutation when the underlying order is ascending.

For:

1,2,3,4

the final lexicographic permutation is:

4,3,2,1

There are:

4! = 24

permutations.

Therefore its zero-based rank is:

23

and one-based position:

24

Rank of the First Permutation

The ascending permutation:

1,2,3,…,n

has no smaller unused element at any position.

Thus every Lehmer digit is zero:

0,0,…,0

Therefore:

Rank₀ = 0

This is the first lexicographic permutation.

Rank of the Reverse Permutation

For:

n,n-1,…,2,1

the first element skips:

n-1

smaller elements.

The second skips:

n-2

and so on.

Its Lehmer digits are:

n-1, n-2, …, 1, 0

The resulting rank is:

n! – 1

which is the largest possible zero-based rank.

Permutation Rank and Factorials

The number of permutations remaining after fixing i positions is factorial.

At the first position:

(n-1)!

At the second:

(n-2)!

At the third:

(n-3)!

This is why factorials form the place-value system used by permutation rank.

Ordinary decimal notation uses weights:

10³, 10², 10¹, 10⁰

while permutation ranking uses:

(n-1)!, (n-2)!, …, 1!, 0!

This is sometimes described as a factorial number system.

Factorial Number Representation

A zero-based permutation rank can be expressed using factorial place values.

For example:

Rank = 13

for four elements.

Write:

13 = 2×3! + 0×2! + 1×1! + 0×0!

So its factorial digits are:

2,0,1,0

These are precisely the Lehmer-code digits of:

3,1,4,2

The digits are constrained:

c₁ ≤ n-1

c₂ ≤ n-2

and so on.

Unranking a Permutation

Ranking maps:

permutation → integer

The inverse operation maps:

integer → permutation

Suppose the ordered elements are:

1,2,3,4

and the zero-based rank is:

13

Convert to factorial digits.

Largest weight:

3! = 6

Calculate:

13 ÷ 6 = 2 remainder 1

So first digit:

2

Next weight:

2! = 2

1 ÷ 2 = 0 remainder 1

Second digit:

0

Next:

1! = 1

1 ÷ 1 = 1

Third digit:

1

Final digit:

0

Thus:

2,0,1,0

Convert Lehmer Digits Back to a Permutation

Start with available elements:

[1,2,3,4]

Digit:

2

Select the zero-based item at index 2:

3

Remaining:

[1,2,4]

Next digit:

0

select:

1

Remaining:

[2,4]

Next digit:

1

select:

4

Remaining:

[2]

Final:

2

Therefore:

rank 13 corresponds to 3,1,4,2

The ranking and unranking calculations reverse each other.

Permutation Rank With Letters

The elements do not have to be numbers.

Suppose the reference order is:

A < B < C

The lexicographic permutations are:

ABC

ACB

BAC

BCA

CAB

CBA

Therefore:

Rank₀(BCA) = 3

The ranking calculation depends on the ordering relation among the elements, not on whether they are represented by numbers or letters.

Reference Ordering Must Be Defined

Suppose the elements are:

red, blue, green

To assign a lexicographic rank, you must define an ordering such as:

blue < green < red

or another explicit order.

Different reference orders can produce different ranks for the same displayed permutation.

Thus a complete permutation-rank problem needs:

the elements,

their ordering rule,

and:

the rank-index convention.

Permutation Rank Is Not the Same as nPr

The permutations formula:

nPr = n!/(n-r)!

counts how many ordered selections of r elements can be made from n distinct elements.

Permutation rank answers a different question:

Where does one particular permutation appear within an ordering?

For a full permutation of four elements:

4P4 = 4! = 24

There are 24 possibilities.

The rank then identifies one of those 24 positions.

Permutation Rank vs. Permutations and Combinations

Permutations and combinations distinguishes ordered selections from unordered selections.

Permutation ranking requires an ordered arrangement, because its position changes when the arrangement changes.

For example:

1,2,3

and:

1,3,2

contain the same elements but are different permutations and therefore have different ranks.

An unordered combination would treat those arrangements as the same selected set, so the ordinary permutation-ranking concept would not apply directly.

Permutation Rank and Combinatorics

Combinatorics studies counting, arrangements, selections, and discrete structures.

Permutation ranking adds indexing to one of those structures.

Instead of merely saying there are:

n!

full permutations, ranking establishes a one-to-one correspondence between them and integers:

0,1,2,…,n!-1

under a fixed convention.

This allows permutations to be stored or referenced by position.

Distinct Elements Are Important

The simple factorial rank formula assumes all elements are distinct.

For:

A, A, B

ordinary permutations such as swapping the two indistinguishable A elements do not create a visibly different arrangement.

The number of distinct arrangements is then:

3!/2! = 3

rather than:

3! = 6

Ranking repeated-element permutations requires adjusted counting based on how many distinct arrangements remain after each candidate choice.

Therefore the ordinary Lehmer-code formula should not be applied unchanged to multisets.

Permutation Rank With Repeated Elements

For distinct symbols, every remaining choice leads to the same number:

k!

of suffix arrangements.

With repeated symbols, those block sizes may instead involve multinomial counts such as:

k!/(n₁!n₂!…nⱼ!)

This changes the ranking procedure.

The central permutation-rank formula on this page therefore assumes:

distinct elements

unless explicitly stated otherwise.

Perfect Square Rank Values

A permutation rank is an integer, so its numerical value can have other number-theory properties.

For example, a zero-based rank of:

16

is also a perfect square because:

16 = 4²

That classification does not change how rank 16 was obtained.

It simply describes the resulting integer.

Perfect Cube Rank Values

Likewise, a rank can happen to be a perfect cube.

For example:

8 = 2³

If a permutation has zero-based rank 8, then 8 is both:

a permutation index

and:

a perfect cube

These are independent mathematical properties of the same integer.

How Fast the Number of Possible Ranks Grows

For a full permutation of n distinct elements, there are:

n!

possible ranks.

For:

n = 4

there are:

24

For:

n = 5

there are:

120

For:

n = 6

there are:

720

The increase from 120 to 720 is:

600

Relative to 120:

600/120 × 100%

= 500%

Using the standard percentage growth interpretation, the number of full permutations grows by 500% when moving from five elements to six.

This rapid factorial growth is why direct enumeration becomes expensive even for moderately large n.

Number of Digits Needed for a Rank

A rank for n distinct elements must represent values up to:

n! – 1

For example, with 10 elements:

10! = 3,628,800

so zero-based ranks range:

0 through 3,628,799

The rank provides a compact integer identifier compared with storing an entire lexicographically sorted list of permutations.

Ranking Algorithm

For distinct elements, a direct procedure is:

Start with the elements sorted according to the reference order.

For each position:

1. Count how many unused elements smaller than the current one remain.
2. Multiply that count by the factorial of the number of positions still to the right.
3. Add the contribution to the running rank.
4. Remove the current element from the unused set.

After the final position, the total is the zero-based rank.

This is the operational form of:

Rank₀ = Σ cᵢ(n-i)!

Example: Rank C,A,D,B

Let:

A < B < C < D

and rank:

C,A,D,B

At C, smaller available letters:

A,B

Count:

2

Contribution:

2 × 3!

= 12

At A:

0 × 2! = 0

At D, remaining:

B,D

One smaller value:

B

Contribution:

1 × 1! = 1

Total:

12 + 1 = 13

Therefore:

Rank₀(CADB) = 13

This is structurally identical to ranking:

3,1,4,2

under numeric order.

Common Mistake: Not Specifying Zero-Based or One-Based Rank

If a calculation gives:

Rank₀ = 13

the permutation occupies:

position 14

in a human-readable list starting at 1.

Calling both values simply “the rank” can create an off-by-one error.

State the convention explicitly.

Common Mistake: Counting All Smaller Elements Instead of Unused Smaller Elements

Suppose ranking:

3,1,4,2

At the third position, current element is:

4

The elements originally smaller than 4 are:

1,2,3

But:

1 and 3

have already been used.

Only:

2

is still available.

Therefore:

c₃ = 1

not 3.

The rank formula counts smaller remaining choices.

Common Mistake: Using the Wrong Factorial Weight

At position i, the weight is based on the number of positions remaining to the right.

For four elements:

first weight = 3!

second = 2!

third = 1!

fourth = 0!

Using 4! for the first digit would overcount entire permutation blocks.

Common Mistake: Ignoring the Reference Order

If:

A < B < C

then:

BAC

has one rank.

If instead the defined order is:

C < B < A

the same displayed arrangement may have a completely different rank.

Lexicographic ranking is relative to a specified ordering of symbols.

Common Mistake: Applying Distinct-Element Formula to Duplicates

The permutation:

AAB

contains repeated symbols.

Treating the two A values as distinct would count arrangements that are visually identical.

Use repeated-element combinatorial counting instead of the ordinary Lehmer-code formula when duplicate elements are present.

How to Check a Permutation Rank

For a small permutation, one check is to list all permutations lexicographically.

For:

1,2,3

the zero-based list is:

0: 1,2,3

1: 1,3,2

2: 2,1,3

3: 2,3,1

4: 3,1,2

5: 3,2,1

The formula gives:

rank₀(3,1,2)

First digit:

2 × 2! = 4

remaining digits contribute:

0

Therefore:

Rank₀ = 4

which matches the list.

Frequently Asked Questions

What is permutation rank?

Permutation rank is the numeric position of a permutation within a defined ordering of all relevant permutations.

What is the permutation rank formula?

For distinct elements under zero-based lexicographic ranking:

Rank₀ = Σ cᵢ(n-i)!

where cᵢ counts smaller unused elements at position i.

What is a Lehmer code?

It is the sequence of counts:

c₁,c₂,…,cₙ

used with factorial weights to represent and rank a permutation.

What is the difference between zero-based and one-based rank?

Zero-based ranking starts the first permutation at 0. One-based indexing starts it at 1.

Rank₁ = Rank₀ + 1

What is the first permutation’s zero-based rank?

0

What is the largest zero-based rank for n elements?

n! – 1

How many ranks exist for n distinct elements?

For full permutations:

n!

Does permutation rank depend on element order?

Yes. The reference ordering of the elements must be specified.

Can letters be ranked?

Yes, provided an ordering such as alphabetical order is defined.

Can permutations with repeated elements be ranked?

Yes, but the simple distinct-element factorial ranking formula must be adjusted for repeated symbols.

What is the zero-based rank of 3,1,4,2?

Relative to:

1,2,3,4

the rank is:

13

Its one-based position is:

14

Final Example

Find the zero-based lexicographic rank of:

4,2,1,5,3

relative to:

1,2,3,4,5

At the first position:

4

Smaller available elements:

1,2,3

So:

c₁ = 3

Contribution:

3 × 4!

= 3 × 24

= 72

Remove 4.

Remaining:

1,2,3,5

Current:

2

Smaller available element:

1

So:

c₂ = 1

Contribution:

1 × 3!

= 6

Remove 2.

Remaining:

1,3,5

Current:

1

No smaller available value:

c₃ = 0

Contribution:

0 × 2! = 0

Remove 1.

Remaining:

3,5

Current:

5

One smaller available value:

3

So:

c₄ = 1

Contribution:

1 × 1! = 1

Final contribution:

0 × 0! = 0

Add:

Rank₀ = 72 + 6 + 0 + 1

= 79

Therefore:

Zero-based permutation rank = 79

and:

One-based position = 80

The central relationship is:

Rank₀ = Σ cᵢ(n-i)!

For distinct elements, factorial weights count how many complete lexicographic blocks are skipped at each position, turning an ordered arrangement into a unique integer from 0 through n!-1.