- Combinatorial Choreography (the workshop paper, details)
- Slides
- Handout
- Signs for A B C D E
- Signs for 0 1 2

- Tom Verhoeff, Roos van Berkel.
"
**Lehmer's Dance - A Lecture Performance**".*Proceedings of Bridges 2019: Mathematics, Art, Music, Architecture, Education, Culture*, pp.375-378, 2019. - Score for 2+2+1 - three colors for five dancers
- Lehmer's theorem on the move (Cursor, news site of TU/e; includes a video interview and some highlights)
- Trailer of Lehmer's Dance -- the lecture performance
- Software
- "The spurs of D. H. Lehmer : Hamiltonian paths in neighbor-swap graphs of permutations"
by Tom Verhoeff in
*Designs, Codes and Cryptography*, DOI: 10.1007/s10623-016-0301-9 (2016). [Open Access] - Tom Verhoeff.
"
**Four Mathematical Designs for EGMO 2020, the European Girls' Mathematical Olympiad in the Netherlands**".*Proceedings of Bridges 2020: Mathematics, Art, Music, Architecture, Education, Culture*, pp.289-296, 2020.

Permutohedron of order four (From Wikipedia) |

Hamilton path on permutohedron of order four (From Wikipedia) |

- Combinatorics, Wikipedia, The Free Encyclopedia.
- Choreography, Wikipedia, The Free Encyclopedia.
- Permutation, Wikipedia, The Free Encyclopedia.
- Combination, Wikipedia, The Free Encyclopedia.
- Hamiltonian path problem, Wikipedia, The Free Encyclopedia.
- Travelling Salesman Problem, Wikipedia, The Free Encyclopedia.
- Concorde: solver for the symmetric traveling salesman problem (TSP) and some related network optimization problems
- Steinhaus-Johnson-Trotter algorithm, Wikipedia, The Free Encyclopedia.
- De Bruijn sequence, Wikipedia, The Free Encyclopedia.
- D.H. Lehmer,
"Permutation by Adjacent Interchanges",
*The American Mathematical Monthly*, Vol. 72, No. 2, Part 2: Computers and computing (Feb. 1965), pp. 36-46. - P. Eades, M. Hickey and R. Read.
"Some Hamilton Paths and a Minimal Change Algorithm",
*Journal of the ACM*, Vol.31, pp.19--29 (1984).

This article proves the theorem that the neighbor-swap graph on n-bit strings (combinations) admits a Hamilton path if and only if it is trivial or the number of 0s and 1s are both odd. - F. Ruskey.
"Solution to Some Lattice Path Parity Difference Recurrence Relations
using Involutions",
*Congressus Numerantium*,**59**:257-264 (1987).

This article actually already presents a proof (for the necessity of two odd counts in the binary case) based on (what I call)*stutter permutations*. - C.W. Ko, F. Ruskey.
"Solution of Some Multi-dimensional Lattice Path
Parity Difference Recurrence Relations",
*Discrete Mathematics*,**71**:47-56 (1988).

This article proves a necessary condition for the existence of a Hamilton path on the neighbor-swap graph on the permutations of a non-trivial multiset, viz. that at least two elements in the multiset occur an odd number of times. - F. Ruskey.
"Generating Linear Extensions of Posets by Transpositions",
Journal of Combinatorial Theory, Series B,
**54**:77-101 (1992). - G. Stachowiak.
"Hamilton Paths in Graphs of Linear Extensions for Unions of Posets",
*SIAM Journal on Discrete Mathematics*, Vol.5, Nr.2, pp.199-206 (1992).

This article (constructively) proves the sufficiency part of the conjecture that the neighbor-swap graph on the permutations of a multiset admits a Hamilton path if and only if it is trivial or there are at least two elements in the multiset that occur an odd number of times. - A. Williams.
"Loopless Generation of Multiset Permutations by Prefix Shifts",
*SODA 2009, Symposium on Discrete Algorithms*, New York, United States (2009).

This article presents a simple algorithm to generate all permutations of a multiset by prefix rotations. [Flash demo] - F. Ruskey, A. Williams.
"The Coolest Way to Generate Combinations",
*Discrete Mathematics*, Vol.309, pp.5305-5320 (2009).

This article presents a simple algorithm to generate all combinations (n-bit strings) by prefix rotations. - Jacqueline M. Smith-Autard.
*Dance Composition: A practical guide to creative success in dance making*. Methuen Drama, A&C Black Publishers, 2010.

The accompanying CD has a nice duo, showing various elegant ways for a pair to trade places.

Selected quotes - E. van Duijnhoven, "Generating all possible permutations with a minimal fixed restriction of any multiset by adjacent interchanges", Bachelor Project Report, Dept. Math. & CS, Eindhoven University of Technology, 2013.
- I. van Heck, "An alternative method and implementation for the generation of a Hamiltonian path through the binary neighbour-swap graph, Bachelor Project Report, Dept. Math. & CS, Eindhoven University of Technology, 2016.
- G. Bellaard, "Constructing shortest covering walks of neighbour-swap graphs: generating linear extensions of posets by adjacent transpositions, Bachelor Project Report, Dept. Math. & CS, Eindhoven University of Technology, 2019.
- A. Smerdu, "Hamiltonian cycles in neighbor-swap graphs, Master Thesis, Faculty of Mathematics and Physics, University of Ljubljana, 2019.