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.

What is the number of functions $f : A\rightarrow A, \forall_{x\in{A}} f(f(x))=x$, set $A$ have $n$ distinct elements.

For $A=\{a,b,c,d\}$ we could look on the right-upper triangle of matrix of all possible pairs (? better word needed here) - below. For $a$ we have four possibilities but if we choose $a->b$ for example, then we have to delete second column. Without deletation we would have $4!$ functions $f$ for $A=\{a,b,c,d\}$, but there is only 1+6+3 of them.

$a->a,a->b,a->c,a->d \\ ........b->b,b->c,b->d \\ ................c->c,c->d \\ ........................d->d $

I think that if $n=2k$ then we could choose first $k$ elements so we have $k$ sets with single element then for each elements with number $k+1 : 2k$ we assign $0$ or $1$. $0$ if $a_{i}->a_{i}$ and $1$ if $a_{i}->a_{1 : n}$, for $i\in k+1:2k$, so we have $2^k$ possibilities. If $j$, $1's$ have been assigned then we have $\binom{k}{j}$ possibilities for two element sets and ... I'm out of ideas.

You could edit my post this is welcome.

share|improve this question
1  
In other words, the number of permutations $\sigma\in S_n$ such that $\sigma^2=e$. If you're familiar with the terms, consider the cycle decomposition of these $\sigma$'s. (Apparently, the answer isn't terribly simple, though.) –  anon May 17 '12 at 18:30
    
yes, it's the essence of my question –  Qbik May 17 '12 at 18:33
    
I don't get the tagging. This is neither set theory nor category theory related. –  Asaf Karagila May 17 '12 at 18:33
1  
Also see en.wikipedia.org/wiki/Telephone_number_(mathematics) –  anon May 17 '12 at 18:38
add comment

1 Answer

up vote 3 down vote accepted

Let $B$ denote a set of size $n+1$ with $B=A\cup\{o\}$, $A$ of size $n$, and $o$ not in $A$. Let $f$ denote an involution of $B$. Then:

  • Either $f(o)=o$, then $f$ is characterized by an involution of $A$.
  • Or $f(o)\ne o$, then there are $n$ possible choices of $f(o)=a$ with $a$ in $A$. Once $a$ is fixed, one knows that $f(a)=o$ hence $f$ is characterized by an involution of $A\setminus\{a\}$.

Let $i_n$ denote the number of involutions of a set of size $n$. One sees that $i_1=1$, $i_2=2$, and that the recursion $i_{n+1}=i_n+ni_{n-1}$ holds, for every $n\geqslant2$. This characterizes the sequence $(i_n)_{n\geqslant1}$.

share|improve this answer
add comment

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.