A multiset is an unordered collection of elements where elements may repeat anynumber of times. The size of a multiset is the number of elements in it countingrepetitions.(a) What is the number of multisets of size $4$ that can be constructed from $n$distinct elements so that at least one element occurs exactly twice?(b) How many multisets can be constructed from $n$ distinct elements?For part b, infinite is correct.For part a, taking $n=3$ and elements $\{1,2,3\}$ we have multisets as:$\{1,1,2,2\}, \{1,1,3,3\}, \{1,1,2,3\}, \{2,2,3,3\}, \{2,2,1,3\}, \{3,3,1,2\}$, for a total of $6$.Similarly for $n=4$ and using elements $\{1,2,3,4\}$, we have $18$ multisets. There must be some formula, or we have to develop one!I am in particular looking for a formula when there is a restriction on the number occurrences in the multiset.
Multisets of a given set
combinatorics;sets
Here is one way to go about your part (a):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: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.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}$$Note, that $n \ge 2$ otherwise no element can be present twice. This is also obvious from the formula (when $n = 0, 1$).You can check that the formula tallies with your counts.