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?
On
There are four places to be filled in the multiset using the $n$ distinct elements. Atleast one element has to occur exactly twice. That would leave $2$ more places in the multiset. This means, atmost two elements can occur exactly twice. We can thus divide this into $2$ mutually exclusive cases as follows:
$1. $Exactly one element occurs exactly twice: Select this element in ${n\choose{1}} = n$ ways. Fill up the remaining two spots using $2$ distinct elements from the remaining $n-1$ elements in ${{n-1}\choose{2}}$ ways. Overall: $n \cdot {{n-1}\choose{2}} = \frac{n(n-1)(n-2)}{2}$ ways.
$2.$ Exactly two elements that occur twice each: These two will fill up the multiset, so you only have to select two elements out of $n$ in ${n\choose 2} = \frac{n(n-1)}{2}$ ways.
Since these are mutually exclusive, the total number of ways to form the multiset is: $$\frac{n(n-1)(n-2)}{2} + \frac{n(n-1)}{2}$$$$ = \frac{n(n-1)^2}{2}$$
Hence, for $n=4$, we have a total of $18$ multisets. Hope it helps.
On
We first pick the element that will repeat exactly twice. We have $n$ choices for that. We then pick the remaining two elements, which can repeat, so we have $(n-1)^2$ choices for that.
Now, in the case that the last two elements picked are different, then we count that case twice, when we should only count it once. This is because we count as picking $a$ then $b$ as distinct from picking $b$ then $a$.
In the case that the last two elements are the same, we also double count that case, since if the last two elements where $b$ and the first element was $a$, the case where the first element was $b$ and the last two elements were $a$ would also be distinctly counted.
Thus, we count every case exactly twice, and therefore divide by two to reach the final formula:
$$\frac{n(n-1)^2}{2}$$
On
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.
Represent a multiset
$$\{\underbrace{1,\dots,1}_{x_1\text{ times}},\underbrace{2,\dots,2}_{x_2\text{ times}},\dots,\underbrace{n,\dots,n}_{x_n\text{ times}}\}$$
by $\{1^{x_1},2^{x_2},\dots,n^{x_n}\}$. For each $j=1,\dots,n$ a mulsitet of size $4$ in which $x_j$ occurs exactly twice corresponds to a solution of
$$ \left\{\begin{array}{l} \displaystyle\sum_{\substack{1\leq i\leq n}\\i\neq j} x_i= 2\\ x_i\geq 0 \end{array}\right.$$
The number of solutions to this system can be found via stars and bars, and that number is $\binom{2+(n-1)-1}{2}=\binom{n}{2}$. This might point in the direction that the answer is $n\binom{n}{2}$, but we're overcounting.
Indeed, when $j_1\neq j_2$, the multiset $\{{j_1}^2,{j_2}^2\}$ is counted twice: once for the index $j_1$, and once for the index $j_2$. It's easy to see this is the only case of overcounting. How many such sets there are?
That's just the number of ways to choose two distinct indices from among $\{1,\dots,n\}$, that is, $\binom{n}{2}$. Hence, the final answer is