10
$\begingroup$

What is known about the (asymptotic?) behaviour of the number of equivalence classes of functions $n\to n$, where two functions are considered equivalent if they differ by a permutation of $n$, i.e., $f\sim g$ if there is a permutation $\sigma$ of $n$ so that $f=\sigma g\sigma^{-1}$?

I am guessing this a known or elementary thing that I am somehow unable to google. When restricted to bijections, this is the partition function, which has been famously estimated by Hardy and Ramanujan.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
12
$\begingroup$

The OEIS page linked by Sam Hopkins also refers to page 308 of Finch, Mathematical Constants (which refers back to the Meir and Moon paper). Finch writes that the generating function $$ P(x)=\sum_1^{\infty}P_nx^n $$ satisfies $$ 1+P(x)=\prod_1^{\infty}(1-T(x^k)))^{-1} $$ where $$ T(x)=\sum_1^{\infty}T_nx^n $$ is given on page 296 as the generating function for $T_n$, the number of nonisomorphic rooted trees of order $n$. $T(x)$ satisfies $$ T(x)=x\exp\left(\sum_1^{\infty}{T(x^k)\over k}\right),\quad T_{n+1}={1\over n}\sum_1^{\infty}\left(\sum_{d\mid k}dT_d\right)T_{n-k+1} $$ Finch gives the asymptotic $$ P_n\sim\eta_Pn^{-1/2}\alpha^n $$ where $$ \eta_P={1\over2\pi}\left({2\pi\over\beta}\right)^{1/3}\prod_2^{\infty}\left(1-T(\alpha^{-i})\right)^{-1}=0.4428767697\dotsc=(1.2241663491\dotsc)(4\pi^2\beta)^{-1/3} $$ Here $\alpha=2.9557652856\dotsc=(0.3383218568\dotsc)^{-1}$ is the unique positive solution of the equation $T(x^{-1})=1$, and $$ \beta={1\over\sqrt{2\pi}}\left(1+\sum_2^{\infty}\alpha^{-k}T'(\alpha^{-k})\right)^{3/2}=0.5349496061\dotsc $$ $T'$ being the derivative of $T$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I think this is all explained in the introduction of the paper by Mutafchiev I linked to too, but it's good to have it written down on MO, so thanks! $\endgroup$
    – Sam Hopkins
    Commented Aug 17, 2023 at 0:40
  • 1
    $\begingroup$ By the way, I believe roughly how to think of the generating function $\prod_{i=1}^{\infty} \frac{1}{1-T(x^i)}$ is this: of course $\prod_{i=1}^{\infty} \frac{1}{1-x^i}$ is the generating function for the partition numbers, i.e., for cycle types of permutations; to get a general function(al digraph) $[n] \to [n]$ we take the cycles of some permutation and append to them rooted trees (hence the appearance of $T(x)$). $\endgroup$
    – Sam Hopkins
    Commented Aug 17, 2023 at 0:50
  • $\begingroup$ That's pretty cool, thanks. I tried to estimate how many there are with one cycle using the asymptotic formula for $T_n$ and only got it up to $\alpha^n/n^{.6578}$ or so. (Not rigorously.) What's the correct answer for that? $\endgroup$
    – seldom seen
    Commented Aug 17, 2023 at 13:59
  • 1
    $\begingroup$ @seldomseen: The generating function for functional digraphs with a single cycled (a.k.a. weakly connected functional digraphs) is discussed on the last page of "Enumeration of mapping patterns" by N.G de Bruijn doi.org/10.1016/0097-3165(72)90081-7. (De Bruijn calls these "primitive" functional digraphs.) There's an appearance of Euler's totient function, because we have to use the cycle index polynomial for a cyclic group action. So it might be slightly difficult to work with this expression. A different approach is to take log of the relation between arbitrary and primitive digraphs. $\endgroup$
    – Sam Hopkins
    Commented Aug 17, 2023 at 17:55
10
$\begingroup$

This sequence is in the OEIS at: https://oeis.org/A001372

The asymptotics were apparently worked out in: Meir, A., Moon, J.W. On random mapping patterns. Combinatorica 4, 61–70 (1984). https://doi.org/10.1007/BF02579158.

But that paper is behind a paywall I cannot get through. You can see a description of the work of Meir and Moon in the first couple pages of "Large Trees in a Random Mapping Pattern" by Lyuben Mutafchiev https://doi.org/10.1006/eujc.1993.1037, which can be read free online.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .