Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


  • $|F_2| = 4$, $|F_2/_{\sim}| = 3$
  • $|F_3| = 27$, $|F_3/_{\sim}| = 7$
share|cite|improve this question
what do you mean by "isomorphism" ? Usually, when you have a structure on a set, a morphism is an application that preserves this structure, and an isomorphism is bijective morphism. Since you didn't give any structure on [n], do you mean bijection (in that case the answer is n! ) – Djaian Oct 31 '10 at 15:50
Consider a function f: [n] -> [n] as a directed graph on n vertices. Unlabel this graph. I mean the number of those unlabelled graphs. – Hans Stricker Oct 31 '10 at 15:54
So you want to count the number of maps up to renamings on the domain and codomain? – Mariano Suárez-Alvarez Oct 31 '10 at 16:06
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. – Mariano Suárez-Alvarez Oct 31 '10 at 16:13
up vote 2 down vote accepted

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.

share|cite|improve this answer
No, I doubt that's what he means. I suspect the equivalence relation is conjugacy with respect to permutations: that $f\sim g$ iff $f=\pi\circ g\circ\pi^{-1}$ for a permutation $\pi$. Thus when $n=2$ we get three equivalence classes, not $p_2=2$ of them. – Robin Chapman Oct 31 '10 at 16:10
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? – I. J. Kennedy Nov 1 '10 at 5:11

Your Answer


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.