# Standard Approach to the Fundamental Counting Principal

I'm trying to teach myself combinatorics from a textbook. The last question of the first chapter is as follows:

If A is a finite set, its cardinality $o(A)$, is the number of elements in $A$. Compute (a) $o(A)$ when $A$ is the set consisting of all five-digit integers, each digit of which is 1, 2 or 3. (b) $o(B)$, where $B = \{x \in A : \text{ each of 1, 2 and 3 is among the digits of$x$}\}$ and $A$ is the set in part (a).

The notation is kind of new to me, but I understand (b) to mean that values such as 33333 or 21211 are not allowed because each value must contain at least one of the digits 1, 2 and 3. Therefore I represented the values as follows:

xxabc, xaxbc, xabxc, xabcx, axxbc, axbxc, axbcx, abxxc, abxcx, abcxx


Where the values for x are independently 1, 2 or 3, and the values for a, b and c are dependently 1, 2 or 3. So the combinations of x are $3^2$, and those of abc are $3!$. Since there are 10 ways of representing these combinations, I believe the answer for (b) is:

$$9\cdot6\cdot10 = 540$$

Although I'd like someone to verify that that is true, my real question has to do with my approach at solving it. I had a girlfriend in college who was very good at looking at algebraic equations and figuring out the answer in her head, even though she understood very little about algebra itself. I'm suspecting that I have the same problem here, because there is a hint in the back of the book that doesn't make any sense to me:

Hint: The answer can be expressed as a sum of six multinomial coefficients.

Therefore my question is: Can someone explain the hint, and if there is a better or more common way to represent the problem, what would that be? Even though I found ten ways to list the combinations, I didn't do it mathematically, but rather by carefully listing them out on a piece of paper. That, in itself, is a good indication that there is something wrong with my approach.

Now, do you know what multinomial coefficients are? If not, look them up in your book. The number of arrangements of 3 ones, 1 two and 1 three is the multinomial coefficient $\dfrac{5!}{3!1!1!}=20$; the number of arrangements of 2 ones, 2 twos and 1 three is $\dfrac{5!}{2!2!1!}=30$, so the answer to your problem is $20+20+20+30+30+30=150$ if I did all that arithmetic right.
By the way, the number of arrangements of xxaaa is ${5\choose 2}=\dfrac{5!}{2!3!}=10$, the number of ways to choose 2 things from 5. This is a binomial coefficient, which is a special case of the multinomial coefficient; the binomials are the ones you will have the most use for.