UlamDistance on Permutation

The entries to remove to leave an increasing sequence: n less the length of a longest increasing subsequence.

On Permutation

FindStat takes the longest increasing subsequence of the inverse, which has the same length.

Called as CombinatorialStat(x, "UlamDistance"). The head's page has its examples.

Live

Distribution

Over SymmetricGroup at each size, tallied here in your browser; sizes past 8 are not offered.

Sizes 1 to

FindStat St000829

The Ulam distance of a permutation to the identity permutation.

The Ulam distance of a permutation to the identity permutation. This is, for a permutation $\pi$ of $n$, given by $n$ minus the length of the longest increasing subsequence of $\pi^{-1}$.

Object	Value
[1,2]	0
[2,1]	1
[1,2,3]	0
[1,3,2]	1
[2,1,3]	1
[2,3,1]	1
[3,1,2]	1
[3,2,1]	2

Data from FindStat, the combinatorial statistic finder; the page at findstat.org/St000829 has the rest.