There are $n$ men, standing one at each vertex of a convex $n$-gon. If they are allowed to move together along sides or diagonals of the polygon to reach another vertex, how many different ways are there to do so without meeting another one?


See OEIS [A350599](http://oeis.org/search?q=A350599) for the first few numerical values.



Combinatorics related plane geometry
Assume that the paths may not cross and each man must move.
Label the vertices $1,2,\dots,n$ in clockwise order. Let the man at
vertex $i$ move to vertex $\pi(i)$, so $\pi$ is a permutation of
$1,2,\dots,n$. If we draw an arrow from vertex $i$ to $\pi(i)$, then
we get a disjoint union of noncrossing cycles of length $\geq
3$. We can obtain such cycles by choosing a noncrossing partition of
the vertices with no blocks of size 1 and 2, and then orienting the
boundary of the convex hull of each block in two ways. Thus in
Exercise 5.35(b) of *Enumerative Combinatorics*, vol. 2, we should set
$f(i)=2$ for $i\geq 3$ and $f(1)=f(2)=0$. If the desired answer is
$h(n)$, then by this exercise we have
$$ x+\sum\_{n\geq 1}h(n)x^{n+1} = \left( \frac{x}{1+2\sum\_{n\geq 3}
 x^n}\right)^{\langle -1\rangle} $$
$$ = \left( \frac{x(1-x)}{(1+x)(1-2x+2x^2)}\right)^{\langle
 -1\rangle}, $$
where $\langle -1\rangle$ denotes compositional inverse.


If a man is allowed to stand still, replace $1+2\sum\_{n\geq 3}x^n$ by
$1+x+2\sum\_{n\geq 3}x^n$.


Possibly you can get some kind of explicit formula for $f(n)$ out of
this, but it will be messy.


