Find the number of four-digit positive integers with digit sum $4$.
The book's method:
Using digits $4, 0, 0, 0$: The four must be placed in the the thousands place and each of the remaining places must be filled with a zero. There is $1$ such number.
Using digits $3, 1, 0, 0$: Choose which of the nonzero digits will be placed in the thousands place. Choose which of the remaining three places will be filled with the other nonzero digit. The remaining two digits must be filled with zeros. There are $$\binom{2}{1}\binom{3}{1} = 6$$ such numbers. Note that using the multinomial coefficient, we can express this in the form $$\binom{2}{1}\binom{3}{1, 2} = \frac{2!}{1!1!} \cdot \frac{3!}{1!2!} = 2 \cdot 3 = 6$$
where $\binom{3}{1, 2}$ represents the number of ways of filling the hundreds, tens, and units places with one nonzero digit and two zeros.
Using digits $2, 2, 0, 0$: We must place a $2$ in the thousands place. Choose which of the remaining three positions will receive a $2$. The remaining two digits must be filled with a zero. There are
$$\binom{1}{1}\binom{3}{1} = 3$$
such numbers. Using multinomial coefficients, we can express this in the form
$$\binom{1}{1}\binom{3}{1, 2} = \frac{1!}{1!0!} \cdot \frac{3!}{1!2!} = 3$$
where $\binom{3}{1, 2}$ represents the number of ways of filling the hundreds, tens, and units places with one nonzero digit and two zeros.
Using digits $2, 1, 1, 0$: We consider two cases: the thousands place is filled by a $2$, or the thousands case is filled by a $1$.
The thousands place is filled by a $2$: There is one way to fill the thousands place. Choose two of the remaining three positions for the $1$s. The zero must be placed in the remaining position. There are $$\binom{1}{1}\binom{3}{2} = 3$$ such numbers. Using multinomial coefficients, we may write $$\binom{1}{1}\binom{3}{2,1} = \frac{1!}{1!0!} \cdot \frac{3!}{2!1!} = 3$$
where $\binom{3}{2, 1}$ represents the number of ways of filling the hundreds, tens, and units places with two ones and one zero.
The thousands place is filled by a $1$: There is one way to fill the thousands place. The remaining three digits are distinct. They can be placed in the remaining three positions in $3! = 6$ ways. There are $$\binom{1}{1}3! = 6$$ such numbers. Using multinomial coefficients, we may write $$\binom{1}{1}\binom{3}{1,1,1} = \frac{1!}{1!0!} \cdot \frac{3!}{1!1!1!} = 6$$
where $\binom{3}{1, 1, 1}$ represents the number of ways of filling the hundreds, tens, and units places with three distinct digits.
Using digits $1, 1, 1, 1$: All four positions must be filled with $1$s. There is $\binom{4}{4} = 1$ such number.
Total: There are $1 + 6 + 3 + 3 + 6 + 1 = 20$ four-digit positive integers with digit sum $20$.
An alternative approach: Let $x_1, x_2, x_3, x_4$ denote, respectively, the digit in the thousands, hundreds, tens, and units places. Since the number has digit sum $4$,
$$x_1 + x_2 + x_3 + x_4 = 4 \tag{1}$$
where $x_1, x_2, x_3, x_4$ are integers satisfying $x_1 \geq 1$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$.
To make life simpler, we let $x_1' = x_1 - 1$. Then $x_1'$ is a nonnegative integer, like $x_2$, $x_3$, and $x_4$. Substituting $x_1' + 1$ for $x_1$ in equation 1 yields
\begin{align*}
x_1' + 1 + x_2 + x_3 + x_4 & = 4\\
x_1' + x_2 + x_3 + x_4 & = 3 \tag{2}
\end{align*}
Equation 2 is an equation in the nonnegative integers. A particular solution of equation 2 corresponds to the placement of $4 - 1 = 3$ addition signs in a row of three ones. For instance,
$$1 + 1 + 1 +$$
corresponds to the solution $x_1' = x_2 = x_3 = 1$, $x_4 = 0$ (and the number $2110$ since $x_1 = x_1' + 1$), while
$$+ + 1 1 1 +$$
corresponds to the solution $x_1' = x_2 = 0$, $x_3 = 3$, $x_4 = 0$ (and the number $1030$). The number of such solutions is the number of ways we can place three addition signs in a row of three ones, which is
$$\binom{3 + 4 - 1}{4 - 1} = \binom{6}{3} = 20$$
since we must choose which three of the six positions required for three ones and three addition signs will be filled with addition signs.
Notice that we obtained the same answer as above without doing casework.
No repeated pairs or trios:
{1,2,6,17,21}
{1,4,7,14,19}
{1,5,8,16}
{1,9,13,24}
{1,10,23,25}
{1,12,15,22}
{2,3,19,23,24}
{2,4,10,15}
{2,5,11,13}
{2,7,22,25}
{2,8,14,18}
{3,4,18,20}
{3,5,7,10}
{3,6,15,25}
{3,9,12,16,21}
{3,13,14,17}
{4,5,9,25}
{4,6,8,13,22}
{4,11,17,24}
{5,12,14,24}
{5,15,17,19}
{6,7,16,24}
{6,9,11,14}
{6,10,12,19,20}
{7,11,12,18}
{7,13,20,23}
{8,9,15,20}
{8,10,11,21}
{8,12,17,23}
{9,18,22,23}
{10,13,16,18}
{11,16,19,22}
{14,15,21,23}
{16,17,20,25}
{18,19,21,25}
{20,21,22,24}
I used integer linear programming with a binary variable for each possible group of 4 or 5 numbers.
Best Answer
To avoid double-counting let us count the sets with exactly $d$ distinct elements. This means that any of $d$ elements is present in multiset at least once. Observe that the multisets differ only by the counts of the elements. Taking into account that the count of each element is at least one the overall number of the corresponding multisets is essentially the number of way to distribute the rest $k-d$ elements into $d$ "bins", which by stars and bars is: $$ \binom{k-d+d-1}{k-d}=\binom{k-1}{d-1} $$ The overall number of such multisets is: $$ N_{nkd}=\binom nd\binom{k-1}{d-1}, $$ where $\binom{n}d$ is the number of ways to choose $d$ elements out of $n$.
Finally the number of all multisets with number of distinct element not exceeding $d$ is: $$ N^*_{nkd}=\sum_{i=1}^d\binom ni\binom{k-1}{i-1}. $$