Equivalently, how many functions on the set $\{0, 1, 2, ..., 2N-1\}$ satisfy the following conditions?

  1. For all $n$, $f(n) \neq n$.
  2. For all $n$, $f(n) \neq n+1 ~(\text{mod } 2N)$.
  3. For all $n$, $f(f(n)) = n$.

If the answer to this question is denoted $F(N)$, I've determined that $F(2) = 1$, $F(3) = 4$, and $F(N) \le \frac{(2N-3)(2N-3)!}{2^{N-2}(N-2)!}$. (Note that the answer is $\frac{(2N)!}{2^N N!}$ if you remove condition 2.) But I don't know how to determine a general solution for $F$.

  • $\begingroup$ Could you please point out, how this relates to graphs? $\endgroup$ – draks ... Apr 24 '12 at 6:37
  • 1
    $\begingroup$ @draks : In a cycle graph, each vertex is connected to two other vertices. To make the graph cubic, we need to add one edge to each vertex. The function $f$ maps each vertex to the vertex that this new edge connects it to. Condition 3 says that the graph is undirected, so that if a new edge connects $v$ to $w$, it also connects $w$ to $v$. Condition 2 says that the new edges don't replicate existing edges. Condition 1 says that a new edge never connects a vertex to itself. $\endgroup$ – Will Orrick Apr 26 '12 at 17:41

You can use the principle of inclusion-exclusion. Let $s(i_1,i_2,\ldots,i_k)$ denote the number of ways to partition $2N$ vertices into $N$ unordered pairs if $\{i_1,i_1+1\}$, $\{i_2,i_2+1\}$, ..., $\{i_k,i_k+1\}$ (with arithmetic performed mod $2N$) are required to be among the pairs. Observe that this quantity is zero if $i_k=i_j+1 \pmod{2N}$ for any $j$, $k$, since $\{i_j,i_j+1\}$ and $\{i_j+1,i_j+2\}$ cannot both be pairs. Then the number of partitions in which none of the pairs are edges of the cycle graph is $$ s()-\sum_i s(i)+\sum_{i<j}s(i,j)-\sum_{i<j<k}s(i,j,k)+\ldots. $$

Now if $s(i_1,i_2,\ldots,i_k)$ is nonzero then it equals $\dfrac{(2N-2k)!}{2^{N-k}(N-k)!}=(2N-2k-1)!!$ since the pairings are fixed for $2k$ of the vertices, which leaves $2N-2k$ vertices to pair up. The number of ways of choosing $\{i_1,i_2,\ldots,i_k\}$ so that $i_k\ne i_j+1\pmod{2N}$ holds for all $j$, $k$, is $\binom{2N-k}{k}+\binom{2N-k-1}{k-1}$. (This is the same as the number of words that can be formed from $k$ Ps and $2N-2k$ Ss or from $k-1$ Ps and $2N-2k$ Ss. Here P stands for "pair" and S stands for "singleton". The word PPSPS, for example, corresponds to the $\{i_1,i_2,i_3\}=\{0,2,5\}$. The $i_j$ are the positions of the Ps, with Ps thought of as occupying two sites and Ss as occupying one. The first binomial coefficient counts the $\{i_1,i_2,\ldots,i_k\}$ in which none of the $i_j$ equals $2N-1$; the second counts the $\{i_1,i_2,\ldots,i_k\}$ in which one of the $i_j$ equals $2N-1$.)

Putting this all together, the number of partitions in which none of the pairs are edges of the cycle graph is $$ \sum_{k=0}^N(-1)^k(2N-2k-1)!!\left[\binom{2N-k}{k}+\binom{2N-k-1}{k-1}\right]. $$ For $N=1,2,3,4,\ldots$ we get 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897. This is A003436 in the Online Encyclopedia of Integer Sequences, which contains many useful references about this sequence.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.