How many multisets of size $4$ that can be constructed from $n$ distinct elements so that at least one element occurs exactly twice ?
Example : For $n=3$ and element set as $\{1,2,3\}$ I am getting multisets as:
$\{1,1,3,3\}, \{1,1,2,2\}, \{1,1,2,3\}, \{2,2,3,3\}, \{2,2,1,3\}, \{3,3,1,2\}$, which are total $6$.
I am looking for a formula for large N. Is there any such formula or do we have to count manually?
Best Answer
Generalizing the problem to allow the size of the multiset to change as well as the number of available numbers to use in the multiset.
As was started by another user, if we were to ignore the requirement on having at least one number occur exactly two times, we have the count being $\binom{n+k-1}{k}$
We wish to remove the "bad" multisets, which are those that do not have an element repeated exactly two times. To count how many are "bad" we can easily approach via generating functions. For each of the $n$ available numbers, the term $(1+x+x^3+x^4+x^5+\dots)$ will represent the available choices of taking zero, one, three, four, five, etc... copies of that number. With every number appearing any number of times except for two, there will clearly then be no number that occurs exactly two times.
The coefficient of $x^k$ then in the expansion of
$$(1+x+x^3+x^4+x^5+\dots)^n$$
will represent the number of multisets of size $k$ can be made using elements from the $n$ element set where none of the terms appear exactly two times.
The number of multisets which satisfy your condition will be $\binom{n+k-1}{k}$ minus the coefficient of $x^k$ in the series expansion of $(1+x+\frac{x^3}{1-x})^n$, or alternately worded using generating functions for the first, the overall generating function is:
$$\frac{1}{(1-x)^n}-(1+x+\frac{x^3}{1-x})^n$$
In your specific case we have for $n=3$ the series expansion
$$3x^2+6x^3+\color{red}{6x^4}+9x^5+13x^6+15x^7+18x^8+21x^9+\dots$$
The $6$ in $\color{red}{6x^4}$ corresponds to the six multisets you wrote down above.