Stirling Permutations to Increasing Plane Trees and Back

Ariel Minakawa and Gavin Sayrs
Undergraduate Students
University of Wisconsin-Milwaukee

A Stirling permutation is a permutation on the multiset {1,1, 2, 2, 3, 3, … ,n, n} such that any numbers appearing between repeated values of i must be greater than i. Recall that a plane tree is a tree drawn on a plane with no edges crossing. An increasing plane tree is a plane tree where each vertex is labeled from 1 to n, with labels increasing away from the root. Our main result establishes a bijection from Stirling permutations to its respective increasing plain tree.