# 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.

-

You overcounted quite a bit. The answer I get is 150.

To see why your count is too high, observe that the number 12321 was counted four times: as xxabc, xabxc, axbcx, and abcxx.

The idea of the hint in the book is to divide the things you want to count into six nonoverlapping classes depending on the distribution of digits: (a) numbers with 3 1's, a 2 and a 3, i.e., rearrangements of 11123; (b) rearrangements of 12223; (c) rearrangements of 12333; (d) rearrangements of 11223; (e) rearrangements of 11233; (f) rearrangements of 12233. It's easy to see that all possibilities are covered with no overlaps. So we just have to count how many 5-digit numbers satisfy each of the six cases, and add. Also it's clear that cases (a)-(c) all have the same count (just swapping digits), likewise cases (d)-(f) all have the same count.

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.

-
I missed that by a long shot! That's what I get for not questioning my assumptions. Your answer was very helpful. Thanks! – Pé de Leão Jun 10 '13 at 16:14
"The idea of the hint in the book is to divide the things you want to count into six nonoverlapping classes..." This is a fundamental idea in combinatorics and deserves extra emphasis. Whenever you develop a scheme for counting, always check that have enumerated every object of interest in exactly one way. – Austin Mohr Jun 10 '13 at 16:23