Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$
share|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
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. –  Mariano Suárez-Alvarez Oct 31 '10 at 16:13

1 Answer 1

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|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

 
discard

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.