1
$\begingroup$

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.

  • 1
    Also see http://en.wikipedia.org/wiki/Telephone_number_(mathematics)2012-05-17

1 Answers 1

3

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