BinarySearchTree from Permutation

The tree built by inserting σ(1), σ(2), ... into an empty binary search tree.

The sylvester congruence: two permutations land on the same tree exactly when they agree on which of any pair is inserted first. Built as its parent array (BinarySearchTreeParentArray), then read as a tree.

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

Live

Explore

Each element of Permutation at a size, and its image, applied in your browser; sizes past 7 are not offered.

Size

Properties

Sizes 1 to

Transport a statistic

Pick a statistic on BinaryTree. Its distribution over the images of Permutation at each size is computed, and compared with the 323 statistics on Permutation: those that share it are the ones the map sends it to, as far as the sizes computed show.

Statistic Sizes 1 to

FindStat Mp00072

binary search tree: left to right

Matched by value: our map agrees with FindStat's image on each of the 873 rows of size at most 6 we can read (0 unread; its table has 1200 rows).

SurjectionGraded mapas FindStat records them, checked by FindStat's contributors.

Return the shape of the binary search tree of the permutation as a non labelled binary tree.

Object	Image
`[1]`	`[.,.]`
`[1,2]`	`[.,[.,.]]`
`[2,1]`	`[[.,.],.]`
`[1,2,3]`	`[.,[.,[.,.]]]`

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