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$
$\endgroup$
  • $\begingroup$ 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! ) $\endgroup$ – Djaian Oct 31 '10 at 15:50
  • $\begingroup$ Consider a function f: [n] -> [n] as a directed graph on n vertices. Unlabel this graph. I mean the number of those unlabelled graphs. $\endgroup$ – Hans-Peter Stricker Oct 31 '10 at 15:54
  • $\begingroup$ So you want to count the number of maps up to renamings on the domain and codomain? $\endgroup$ – Mariano Suárez-Álvarez Oct 31 '10 at 16:06
  • 2
    $\begingroup$ 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. $\endgroup$ – Mariano Suárez-Álvarez Oct 31 '10 at 16:13
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Robin Chapman Oct 31 '10 at 16:10
  • $\begingroup$ 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? $\endgroup$ – I. J. Kennedy Nov 1 '10 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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