Ways in which 2k indices can be assigned so that every index is equal to at least one other In trying to approximate a certain power of a sum, I wound up with this issue: 
There are 2k indices, $i_1, i_2, ..., i_{2k}$, each of which can take on any of the values {$1, 2, ..., n$}. I need to know how many ways the indices can take on values so that every index is equal to at least one other index. When there is an index not equal to any other, the term becomes 0; otherwise I have an upper bound in hand for what the term may be. 
I tried abstracting the problem, thinking of the n possible values of an index as a "box" and looking for the ways to put 2k "objects" into n "boxes" so that while some boxes might be empty, no box has exactly one object in it. I'm rusty on this kind of counting problem, so I can't quite grasp how to count all of the cases that arise. It's easy enough to figure out if k = 1, since then there are only two indices and they must always be equal, so you get exactly n possibilities, but other than that I can't quite get it together. The context of this issue suggests there should be a factor like $n^k$ somewhere. Any help would be appreciated.
 A: Rephrasing the question: how many functions $f$ from $\{1,\dots,K\}$ (where $K=2k$) to $\{1,\dots,n\}$ are there such that $f^{-1}(j)$ never has size exactly $1$ for any $1\le j\le n$?
This is a classic problem for inclusion-exclusion. Let $S_f = \{1\le j\le n\colon \#f^{-1}(j)=1\}$ be the "lonely value" set of $f$, and note that
$$
\sum_{T\subset S_f} (-1)^{\#T} = \begin{cases}
1, &\text{if }S_f=\emptyset, \\
0, &\text{if }S_f\ne\emptyset.
\end{cases}
$$
Therefore, writing $[K]=\{1,\dots,K\}$ and $[n]=\{1,\dots,n\}$ the quantiity we want is
$$
\sum_{f\colon[K]\to[n]} \sum_{T\subset S_f} (-1)^{\#T} = \sum_{T\subset[n]} (-1)^{\#T} \sum_{\substack{f\colon[K]\to[n] \\ T \subset S_f}} 1.
$$
The functions counted by the inner sum are the functions for which all the elements of $T$ (and perhaps others) are "lonely values". There are $K(K-1)\cdots(K-\#T+1) = K!/(K-\#T)!$ ways to choose the unique preimages of the elements of $T$ (if $\#T\le K$, otherwise there are none); the remaining $K-\#T$ inputs can each go to any of $n-\#T$ outputs. Therefore
\begin{align*}
\sum_{f\colon[K]\to[n]} \sum_{T\subset S_f} (-1)^{\#T} &= \sum_{\substack{T\subset [n] \\ \#T \le K}} (-1)^{\#T} \frac{K!}{(K-\#T)!} (n-\#T)^{K-\#T} \\
&= K! \sum_{t=0}^{\min\{n,K\}} \binom nt \frac{(-1)^t}{(K-t)!} (n-t)^{K-t}.
\end{align*}
Further analysis depends on whether you're considering $n$ fixed and $K$ increasing, or vice versa, or both increasing.
