show/hide this revision's text 4 fix typo

I will assume the uniform distribution on all (labelled) graphs with $n$ vertices and $k$ edges. An acyclic graph on $n$ vertices has at most $n-1$ edges, so let me further assume $k< n$. More precisely, $k=n-c$, where $c$ is the number of connected components, i.e., the graph is acyclic iff it is union of $c$ disjoint trees. Now, the number of trees with $m$ vertices is $m^{m-2}$ by Cayley’s formula, hence the requested probability is

$$p_{n,k}=\frac1{(n-k)!\binom{\binom n2}k!}\sum_{\substack{n_1+\cdots+n_{n-k}=n\\n_1,\dots,n_{n-kn2}k}\sum_{\substack{n_1+\cdots+n_{n-k}=n\\n_1,\dots,n_{n-k}>0}}\binom n{n_1\,\dots\,n_{n-k}}\prod_{i=1}^{n-k}n_i^{n_i-2}.$$

We have $\binom{\binom n2}k\approx\left(\frac{en^2}{2k}\right)^kk^{-1/2}$ by Stirling’s approximation (where $f\approx g$ means $c_1f\le g\le c_2f$ for some positive constants $c_1,c_2$), hence in the simplest case $k=n-1$,

$$p_{n,n-1}\approx\frac1{\sqrt n}\left(\frac2e\right)^n.$$

show/hide this revision's text 3 hmm

I will assume the uniform distribution on all (labelled) graphs with $n$ vertices and $k$ edges. An acyclic graph on $n$ vertices has at most $n-1$ edges, so let me further assume $k< n$. More precisely, $k=n-c$, where $c$ is the number of connected components, i.e., the graph is acyclic iff it is union of $c$ disjoint trees. Now, the number of trees with $m$ vertices is $m^{m-2}$ by Cayley’s formula, hence the requested probability is

$$p_{n,k}=\binom{\binom n2}k^{-1}\sum_{\substack{n_1+\cdots+n_{n-k}=n\\n_1,\dots,n_{n-k$p_{n,k}=\frac1{(n-k)!\binom{\binom n2}k!}\sum_{\substack{n_1+\cdots+n_{n-k}=n\\n_1,\dots,n_{n-k}>0}}\binom n{n_1\,\dots\,n_{n-k}}\prod_{i=1}^{n-k}n_i^{n_i-2}.$$

We have $\binom{\binom n2}k\approx\left(\frac{en^2}{2k}\right)^kk^{-1/2}$ by Stirling’s approximation (where $f\approx g$ means $c_1f\le g\le c_2f$ for some positive constants $c_1,c_2$), hence in the simplest case $k=n-1$,

$$p_{n,n-1}\approx\frac1{\sqrt n}\left(\frac2e\right)^n.$$

show/hide this revision's text 2 correction

I will assume the uniform distribution on all (labelled) graphs with $n$ vertices and $k$ edges. An acyclic graph on $n$ vertices has at most $n-1$ edges, so let me further assume $k< n$. More precisely, $k=n-c$, where $c$ is the number of connected components, i.e., the graph is acyclic iff it is union of $c$ disjoint trees. Now, the number of trees with $m$ vertices is $m^{m-2}$ by Cayley’s formula, hence the requested probability is

$$p_{n,k}=\binom{\binom n2}k^{-1}\sum_{\substack{n_1+\cdots+n_{n-k}=n\\n_1,\dots,n_{n-k}>0}}\binom n{n_1\,\dots\,n_{n-k}}\prod_{i=1}^{n-k}n_i^{n_i-2}.$$

We have $\binom{\binom n2}k\approx\left(\frac{en^2}{2k}\right)^k$ n2}k\approx\left(\frac{en^2}{2k}\right)^kk^{-1/2}$ by Stirling’s approximation (where $f\approx g$ means $c_1f\le g\le c_2f$ for some positive constants $c_1,c_2$), hence in the simplest case $k=n-1$,

$$p_{n,n-1}\approx\frac1n\left(\frac2e\right)^n.$$$p_{n,n-1}\approx\frac1{\sqrt n}\left(\frac2e\right)^n.$$

show/hide this revision's text 1