Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
Could you please point out, how this relates to graphs? –  draks ... Apr 24 '12 at 6:37
1  
@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. –  Will Orrick Apr 26 '12 at 17:41

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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