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$
  • 0
    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! )2010-10-31
  • 0
    Consider a function f: [n] -> [n] as a directed graph on n vertices. Unlabel this graph. I mean the number of those unlabelled graphs.2010-10-31
  • 0
    So you want to count the number of maps up to renamings on the domain and codomain?2010-10-31
  • 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
    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.2010-10-31
  • 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