# How to compute the number of tuples such that no element appears exactly once?

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?

• These are $t$-tuples. A combination is an unordered selection of distinct elements. Mar 27 at 11:25
• I removed the combinations tag and added the coupon-collector tag, as you're essentially asking for the probability to complete a collection that contains at least $2$ of each of $N$ types of coupons in $t$ draws. For the slightly simpler problem of completing a collection that contains each type at least once, see this question. Mar 27 at 11:29
• You could treat this with inclusion–exclusion, but the fact that you have two ways of violating each condition (by having either no item or only one item) is probably going to lead to a more complicated result. Mar 27 at 11:32
• Thanks for thinking about that. How about "such that no element appears exactly once"? Mar 27 at 13:08
• @joriki That's done. Thanks again! Mar 27 at 13:10

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)!}$$.

Your formula doesn't look bad to me but I obtain a simpler formula by a different reasoning:

• When $$t = 0$$ one has $$u_{N,t}=1$$ because the empty tuple is the only solution.
• When $$N = 0$$ and $$t \not = 0$$, one has $$u_{N, t}=0$$.
• When $$N\not = 0$$ and $$t\not = 0$$, let $$p\in [0, N-1]$$ be the largest value in the tuple and let $$q\in [0, t-2]$$ be the number of slots in the tuple that don't contain the value $$p$$. There are $$\binom{t}{q}$$ such sets of slots and $$u_{p, q}$$ ways to fill the missing slots, hence $$\begin{equation} u_{N, t} = \sum_{p=0}^{N-1}\sum_{q=0}^{t-2}\binom{t}{q} u_{p,q} \end{equation}$$