Young subgroups for reversible computers

We consider the symmetric group Sₙ in the special case wheren is composite: $n = pq$ (both p and q being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of S pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup Sₚq, whereas the second one is an element of the dual Young subgroup Sqᵖ. This leads to synthesis methods for arbitrary reversible logic circuits of logic width w. These circuits form a group isomorphic to S2w. A particularly efficient synthesis is found by choosing $p=2$ and thus $q=2$w−1. The approach illustrates a direct link between combinatorics, group theory, and reversible computing.