Compute the number of tuples such that no element appears exactly once

combinatoricsinclusion-exclusion

I'm trying to compute the number of $t$-tuples such that no element appears exactly once in the tuple, and each element can take values from $[N]=\left\{0,\ldots,N-1\right\}$. Let us denote $u_{N, t}$ this quantity. For instance, for $t=4$ and $N=128$, $(1, 4, 1, 4)$ is a valid tuple (each element within the tuple has at least one other copy) but $(1, 4, 1, 1)$ is not ($4$ is alone). It is fairly simple to see that:

  • $u(N, 1)=0$, since every tuple will contain a single element, it can't have any other copies of it
  • $u(N, 2)=N$, since every valid tuple can be written as $(x, x)$, with $x\in[N]$
  • $u(N, 3)=N$, since every valid tuple can be written as $(x, x, x)$

My reasoning for the general case is the following:

  • $u_{N, t}$ is equal to $N^t$ minus the number of tuples such that at least one element is unique.
  • For $k\geqslant1$, we thus choose the positions of the unique elements, for which we have $\binom{t}{k}$ choices
  • We have to choose the values for these elements, for which we have $\frac{N!}{(N-k)!}$ choices.
  • We finally have to choose the values for the other $N-k$ elements. We know that they cannot contain a single unique element, thus we have $u_{N-k,t-k}$ choices.

All in all, we have:
$$u_{N, t}=N^t-\sum_{k=1}^t\binom{t}{k}\frac{N!}{(N-k)!}u_{N-k, t-k}$$
However:

  • I'm not sure this formula is correct: for $t=1$ and $t=2$ there are some corner cases that make it most likely wrong (we don't get $0$ and $N$ respectively), but it might work for $t\geqslant3$
  • For large values of $N$, this can be quite tedious to compute (dynamic programming?)
  • I would especially be interested in a closed-form for $u_{N, t}$ (or at least some asymptotic behavior for $t=o(N)$)

Is there any clever way to compute this quantity that I missed?

Best Answer

You can do this using inclusion–exclusion.

To violate $k$ of the $t$ conditions that an element of the tuple must not be unique, you can choose the conditions to be violated in $\binom tk$ ways, the unique values in $\frac{N!}{(N-k)!}$ ways and the remaining values in $(N-k)^{t-k}$ ways, so by inclusion–exclusion there are

$$ \sum_{k=0}^t(-1)^k\binom tk\frac{N!}{(N-k)!}(N-k)^{t-k}=\sum_{k=0}^t(-1)^kk!\binom tk\binom Nk(N-k)^{t-k} $$

admissible configurations. Alternatively, you could use the $N$ conditions that the value $k$ must not be used exactly once; the result is of course the same, you just get $\binom Nk\frac{t!}{(t-k)!}$ instead of $\binom tk\frac{N!}{(N-k)!}$.

Related Question