
05192675
j
2007b.00419
Thorup, Anders
The Josefus permutation. (Om Josefus' permutation.)
Normat. Nord. Mat. Tidskr. 55, No. 1, 2536 (2007).
2007
Nationellt Centrum f\"or Matematikutbildning, G\"oteborg
DA
K20
N70
combinatorics
fixed points
cycle types
Summary: It is wellknown that any permutation can be presented as a composition of cycles. In fact every permutation has a unique representation, up to order, as a product of disjoint (and hence commuting) cycles. It turns out that the composition $c_n,c_{n1},\dots,c_2$ where $c_k = (1, 2, 3, \dots, k)$ has a nice and easily found such representation, but surprisingly if the order of the cycles is reversed the problem becomes almost intractable. The elementary nature of the problem gives a good exposure to students, and it has in fact been studied by students over the years. The article is in the nature of a progress report, and the cases of $n = 2^m, 2m1$ are treated in detail. Surprising connections to other parts of combinatorics are highlighted.