What are the odds of a tie in a random election with k candidates? Consider an election with $N$ voters and $k$ candidates, where each voter votes randomly for one of the candidates. What are the odds of a tie?
Here "tie" means that multiple candidates get the highest number of votes, not necessarily that all candidates get the same number of votes.
For $k = 2$ the answer is given by ${N \choose {N/2}} \frac{1}{2^N}$.
I'm not sure how to generalize to $k > 2$. If a closed formula doesn't exist, can we still say something about the asymptotic behavior as $k$ grows?
Edit: asking for "asymptotic behavior" was ambiguous. The question I'm most interested in is: for $k \ll N$, what can we say about how the odds change if $k$ increases by $1$ (or, if it's a cleaner answer, if $k$ doubles). Perhaps it's incorrect to call this asymptotic behavior at all! And, unfortunately, I'm not sure what "$\ll$" should mean in this context. I suppose that's part of the question as well.
 A: For $k=3$ with $N$ not divisible by $3$, the probability  of a tie is
$$ \sum_{m= \lceil N/3 \rceil}^{\lfloor N/2 \rfloor} \dfrac{N!}{m! m! (N-2m)!} 3^{1-N}$$ 
The sum seems not to have a closed form.
As for asymptotics, as $k \to \infty$ with $N>1$ fixed, the probability of a tie is greater  than $1 - {N \choose 2} k^{-1}$, where ${N \choose 2} k^{-1}$ is the expected number of pairs of voters who vote for the same candidate.  Thus if no two voters vote for the same candidate, there is an $N$-way tie among candidates who receive $1$ vote each.
A: For $1\ll k\ll N$, I would roughly estimate the probability of a tie by $O(\sqrt{(k\log k)/N})$. This is a very loose calculation. The number of votes to candidate $i$, $X_i$, is distributed $Bin(1/k,n)$. The loose part of this answer is assuming the $X_i$'s were mutually independent. I guess that it shouldn't change the asymptotic result (maybe this argument can be made precise by using that the $X_i$'s are negatively correlated). 
I estimate the probability of the event $E_{i}=\{X_i=\max_{j\neq i}X_j\}$. Let $\mu$ and $\sigma^2$ be the expectation and the variance of $X_i$ respectively. By CLT, $\Pr(E_i)\sim \Pr(|Y-Z_{k-1}|<1/\sigma)$, where $Y$ and $Z_{k-1}$ are independent, $Y$ is standard normal and $Z_{k-1}$ is the maximum of $k-1$ iid standard normal random variables. The CDF of $Z_k$ is $\Phi^k(x)$, the PDF is $(\Phi^k(x))'=k\Phi^{k-1}(x)\phi(x)$, and the expectation is $\int_{-\infty}^\infty k\Phi^{k-1}(x)\phi(x)x\ dx$. Where $\Phi(x)$ and $\phi(x)$ are the standard normal CDF and PDF respectively.
Since $\phi(x)$ is Lipschitz, $\Pr(|Y-Z_{k-1}|<1/\sigma)=O(\frac 1 \sigma\int_{-\infty}^\infty (\Phi^{k-1}(x))'\phi(x)\ dx)$. Integrating by parts we get
\begin{multline}
\int_{-\infty}^\infty (\Phi^{k-1}(x))'\phi(x)\ dx = \left[\Phi^{k-1}(x)\phi(x)\right]_{-\infty}^\infty + \int_{-\infty}^\infty \Phi^{k-1}(x)\phi(x)x\ dx \\
=  \frac 1 k \mathbb E[Z_k]\leq \frac {\sqrt{2\log k}}k,
\end{multline}
where the last inequality is a standard bound on the expectation of $Z_k$ (see https://math.stackexchange.com/a/89147/251766).
It follows that $\Pr(E_i)=O(\frac 1 \sigma \frac {\sqrt{2\log k}}k)$. Since $\sigma^2=N(1-\frac 1 k)\frac 1 k$, taking the union bound yields $\Pr(\cup E_i)=O(\sqrt{(k\log k)/N})$. 
A: In general, the probability is
$$
\frac{1}{k^N}\sum_{j=2}^k{k \choose j}\sum_{m=0}^{\lfloor N/j\rfloor}{N \choose mj}\frac{(mj)!}{(m!)^j}\sum_{\substack{(a_1,\dots,a_{k-j})\\a_1+\dots+a_{k-j}=N-mj\\0\leq a_i<m}}{N-mj\choose a_1,\dots,a_{k-j}}
$$
where for some choices of $(N,k,m,j)$ the innermost sum is $0$. The variable $m$ is the same as in Robert Israel's answer. The winning candidates each receive $m$ votes. The variable $j$ is the number of winning candidates. Thus, we choose $j$ winning candidates out of the original $k$ candidates in ${k \choose j}$ ways, to each receive $m$ votes. Then we choose $mj$ voters out of the $N$ voters in ${N \choose mj}$ ways to vote for the winning candidates. Then we assign the $mj$ votes that go to the winning candidates to the $j$ winning candidates in $\frac{(mj)!}{(m!)^j}$ ways. Now, there are $N-mj$ votes left to go to the $k-j$ non-winning candidates, and each non-winning candidate receives a maximum of $m-1$ votes, thus the conditions on the innermost sum. The formula is also valid for $k>N$.
