formula for all possible enumerations of a set of distinct elements without any duplicate pairs, triples, quadruples, etc.

Question

Suppose we have a set of 10 distinct elements such as (A, B, C, D, E, F, G, H, I, J). Now suppose that we have 10 slots into which we can place a single element from this set. The total number of different ways of doing this if we allow for duplicates is $10^{10}$. On the other extreme, if we do not allow for any duplicates then there are $10!$ ways in which this can be done. However, we can also consider the intermediate case of allowing for duplicate pairs as long as long as there are no duplicate triples, quadruples, etc in the set. Similarly, we can consider the case of allowing for duplicate pairs and triples but not duplicate quadruples, pentuples, etc. In those intermediate cases, what would be the number of ways in which each of the 10 slots could be assigned an element from the set of 10 distinct elements?

Answer 1

I don't know if this is best answer. but here is mine for doubles allowed. assume there are k (<6) elements repeated , so there are

$$\sum_{k=0}^{5}\binom{10}{k}\binom{10-k}{10-2k}\frac{10!}{(2!)^k}$$

It may seem complicated but just open it it us just a simple rearrangement for each case where 0,1,2,...5 elements repeated twice.

Answer 2

You can use generating functions here as well. For instance, for the problem of allowing duplicates of a letter but not triplicates or more, we would be looking at the coefficient of $x^{10}$ in the expansion of

$$10!(1+x+\frac{x^2}{2})^{10}$$

which would be $3958113600$, which matches the answer by the other user.

If you allow triplicates as well, then the generating function would be $10!(1+x+\frac{x^2}{2!}+\frac{x^3}{3!})^{10}$ and so on up to allowing letters to be repeated up to $k$ times each as being $10!(1+x+\frac{x^2}{2!}+\dots+\frac{x^k}{k!})^{10}$

You could even adjust this for if you allow triplicates but not duplicates by removing the $x^2$ term in the above. You can also adjust this by changing the number of available characters by changing the exponent, or changing the length of the string you are making by changing the factorial in front and which coefficient you are looking for in the expansion.

As a sanity check, letting $k=10$ in the above, meaning we allow any number of repetitions, we get the coefficient of $x^{10}$ as being $10000000000=10^{10}$, exactly as we expected.