# Tag Info

## Hot answers tagged asymptotics

Accepted

• 2,979
Accepted

### How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?

For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2}$ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics&...
• 82.5k
Accepted

### Density of the set of numbers whose sum of digits is prime

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ ...
• 12.9k
Accepted

### Cubic-exponential enumerative combinatorics

Since you mentioned Cayley's theorem for spanning trees, I believe one important example is its higher dimensional analogue due to Kalai. Indeed the number of simplicial spanning trees of the k-...
• 82.5k
Accepted

### Distinct exponents in the factorization of the factorial, a problem of Erdős

The primes $p \leq \sqrt{n}$ can be ignored as the number of them is $$\approx \sqrt{n} / \log (\sqrt{n} )= 2 \sqrt{n}/\log n = o (1) \cdot \sqrt { n/\log n}$$ For primes $p> \sqrt{n}$, the ...
• 119k
Accepted

### Probability that a positive integer is the euler phi function of another positive integer

See Erick Wong's response here. In particular, Kevin Ford proved (in more precise form) that $$f(n) = \frac{n}{\log n} \exp\left(O(\log \log \log n)^2\right),$$ whence $f(n)/n$ tends to zero. The ...
• 87k
Accepted

• 82.5k
Accepted

• 153k
Accepted

• 87k
Accepted

### Prove or disprove that $\sup_{n\in\mathbb{N}}\left|\sum_{\substack{d|n \\d<Q}}\mu(d)\right|\sim\pi(Q)$

This is not true. In fact $$x(\log x)^{-1+1/\pi} \gg \sup_n \Big| \sum_{\substack{ d|n \\ d\le x}} \mu(d) \Big| \gg x (\log x)^{-1+1/\pi}.$$ The upper bound is due to Montgomery and Vaughan (see ...
• 42.6k
Accepted

• 7,154
Accepted

• 90.4k
Accepted

I will show how to improve Tulipani’s construction from $O(p^5)$ symbols to $O(p^3)$ symbols, or $O(p^3\log p)$ bits. Recall that Tulipani’s sentence is $$H_p=\forall\vec x\,\exists\vec s\,\exists\vec ... • 40.3k 11 votes Accepted ### Asymptotics for \int\exp( -x t / \log t)dt Denote t/\log t=y. Then y increases from e to \infty when x goes from e to \infty, and dt(1/\log t-1/\log^2 t)=dy, thus dt\sim \log t\cdot dy\sim \log y\cdot dy for large t (since ... • 90.4k 11 votes ### Asymptotics for \int\exp( -x t / \log t)dt Take any real a>e. Then \begin{equation*} f(x)=f_{1,a}(x)+f_{2,a}(x), \tag{1}\label{1} \end{equation*} where \begin{equation*} f_{1,a}(x):=\int_e^a dt\,e^{-xg(t)},\quad f_{2,a}(x):=\... • 82.5k 10 votes Accepted ### Bound on sum of complex summands involving binomial coefficients Assuming that |x+y|<1 and 4|xy| \le 1, here's a proof of the decay. First suppose that |x|> |y|. The desired sum is$$ \le \binom{2n}{n} |xy|^n \sum_{j=0}^{n} |y/x|^j \le \binom{2n}{...
• 42.6k
Let $A(x)$ denote the formal generating function of $\{ a_n\}$. The recurrence relation can be written as $A(x)=e^x A(x^2)$. Applying this repeatedly, we find $A(x) = e^x e^{x^2} \cdots = e^{f(x)}$, ...