3
$\begingroup$

Consider the set $F_n: = [n]^{[n]}$ of all functions $f:[n] \rightarrow [n]$, $[n] = \lbrace 1,2,...,n\rbrace$. It is well known that $|F_n| = n^n$.

Edit: Let two functions $f, g$ in $F_n$ be of the same isomorphism type ($f\sim g$) iff there exists a permutation $\pi$ such that $f\pi = \pi g $

What is the number of isomorphism types of functions $f:[n] \rightarrow [n]$, i.e. what is $|F_n/_{\sim}|$?

Examples:

  • $|F_2| = 4$, $|F_2/_{\sim}| = 3$
  • $|F_3| = 27$, $|F_3/_{\sim}| = 7$
  • 2
    The less guessing people have to figure out what you are asking, the better your question is! Please add important information, like what you mean by 'isomorphism', to the actual body of the question.2010-10-31

1 Answers 1

2

If you want to count the number of functions up to renamings on the domain and codomain, then the number is $p_n$, the number of partitions of $n$.

Later: now that you've made precise what you wanted... This is counted here, with references.

  • 0
    The sequence begins 1, 3, 7, 19, 47, 130, 343, 951, 2615, 7318, 20491,... I couldn't help but notice $7^3$ sitting there at the 7th spot ($|F_7/_{\sim}|$). Coincidence?2010-11-01