Proving an inequality regarding number of transitive subgroups of the symmetric group I defined the sequence $t$ where where $t(n)$ is the number of transitive subgroups of $S_n$ where we regard conjugate subgroups as distinct, i.e. the labeled version of A002106 at the OEIS.
Then I computed this sequence using a GAP program written by a professional to get more terms. The first $13$ terms of this sequence are
$$1, 1, 2, 9, 20, 279, 512, 19087, 71602, 636365, 1517042, 321965982,
240609602,$$
and I have verified that $\log(\frac{\text{A005432}(n)}{t(n)}) > \frac{n-1}{2}$ for $n$ prime and $\log(\frac{\text{A005432}(n)}{t(n)}) < \frac{n-1}{2}$ for $n$ composite (A005432) up to $n = 18$.
If it helps I have proven that $\text{A005432}(p)-t(p) \equiv 1 \bmod p$ when $p$ is prime.
 A: Here is a very rough sketch of a proof in the case when $n=p$ is prime.
First, a transitive group of prime degree $p$ is either a subgroup of $AGL(1,p)$, or it is an almost simple $2$-transitive group. (This is due to Burnside.)
Now, these almost simple groups are classified. For most values of $p$, this is only $S_p$ and $A_p$. The exceptional values are $11$, $23$ and when $p$ is of the form $\frac{q^n-1}{q-1}$ for a prime power $q$. (This is due to Guralnick I think.)
So these are very well understood.
As for the transitive subgroups of $AGL(1,p)$, there is one conjugacy class for every divisor $d$ of $p-1$, with shape $C_p\rtimes C_d$. It's not hard to show that the normaliser of such a group is exactly $AGL(1,p)$, so the size of the conjugacy class is $\frac{p!}{p(p-1)}=(p-2)!$  So, if $f$ is the number of divisors function, the number of subgroups in this family is $(p-2)!f(p-1)$.
So, for non-exceptional primes $p$, we have that $t(p)=2+(p-2)!f(p-1)$.
(For example, this holds for $p\in\{5,19,29,37,41,43,47...\}$.)
For exceptional primes, the number is a little larger, but it can be controlled, and I think it can be showed that it is asymptotically equal to the above.
Now, write $a(p)=A005432(p)$. According to the OEIS page, Pyber proved that $a(p)\geq c^{p^2}$, with $c$ a known constant.
So, in the non-exceptional case, we have $\log\left(\frac{a(p)}{t(p)}\right)=p^2 \log c-\log t(p)$. Using Stirling's approximation, we find that $\log t(p)$ is roughly $p\log p$, so the desired result holds asymptotically. By being careful with error terms throughout, it should not too hard to close the finite gap.
As for the case $n$ composite, it's possible it's not true.
We are trying to prove that $\log a(n)-log t(n) <   \frac{n-1}{2}$.
But by Pyber, $\log a(n)$ is very close to $n^2\log d$. Since $a(n)>t(n)$, the inequality above can only be true if there is a lot of cancellation, more precisely, it would imply $\frac{\log a(n)}{\log t(n)}\to 1$. In other words, after taking logs, "almost all" subgroups are transitive. My guess is that this is not true and, for large $n$, $\log a(n)-\log t(n)$ will grow like $kn^2$. To prove this, one would need decent upper bounds on $t(n)$. Pyber has many results of this kind, but they are sometimes hard to find, I'll try and have a look...
