Combinatorics and set cardinality

[RM86Z]

Homework Statement

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 ∈ A : each of 1,2 and 3 is among the digits of x} and A is the set in part (a).

Relevant Equations

3^5, 5P3, 3^2

QUESTION:
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 ∈ A : each of 1,2 and 3 is among the digits of x} and A is the set in part (a).

SOLUTIONS:
a) 3^5 = 243 (correct answer as per the book).

b) There is no answer in the book and I am not entirely sure if I am on the right track as below:

As I see this there are five places for the digits 1,2 and 3 to go so we take the permutation of the number of places taken three times; 5P3 = 5!/2! = 60. Then there are two places left over, each of which has 3 choices from {1,2,3} for a total of 3^2 = 9. So the result is 5P3 x 3^2 = 60 * 9 = 540. But this is a larger than o(A) so this cannot be correct?

 

[PeroK]

One approach is to consider excluding those cases in set $A$ where you have only two of the digits or only one of the digits.

 

[RM86Z]

Perhaps it should be:

(5P3 * 3^2) / (3! * 2! * 1!) = 90 (by the multinomial theorem)?

 

[PeroK]

Perhaps it should be:

(5P3 * 3^2) / (3! * 2! * 1!) = 90 (by the multinomial theorem)?

Hmm? A quick mental calculation using exclusion and inclusion suggests it's much higher than that.

 

[PeroK]

Perhaps it should be:

(5P3 * 3^2) / (3! * 2! * 1!) = 90 (by the multinomial theorem)?

I think you have to recognise when a problem is more complicated than a single calculation.

The other approach here is to recognise two possible patterns: a triple and two singles; and, two doubles and a single.

And, in each case there are a number of cases and permutations of which of 1,2,3 is the triple or single.

I'd do it both ways and check you get.the same answer.

 

[PeroK]

PS I get the same answer both ways. The exclusion/inclusion method is much simpler. The "patterns" method is quite tricky.

 

[RM86Z]

Thanks PeroK I am still struggling with this I have broken it down into a smaller case of a set with 3-digit integers, each digit is either of 1 or 2:

The total number of digits is 2^3 = 8.

And the number of digits containing both 1 and 2 is 6 by 3P2 = 3!/1! = 6. The list is as follows:

1,1,1
1,1,2
1,2,1
1,2,2
2,1,1
2,1,2
2,2,1
2,2,2

So 1,1,1 and 2,2,2 need to be eliminated. In this case we want to select only triples of the same number as any other number has at least one of each of {1,2}.

And as another test I'm going to take the following 5-digit number 1,2,1,3,1 which contains at least one of each of 1,2 and 3. In bold below are my possible numbers which contain 3 x 1's, 1 x 2 and 1 x 3:

1,2,1,3,1
1,2,1,3,1
1,2,1,3,1

And by this I can see that there are duplicates in the remaining two digits after taking the permutation of places (5P3 = 60). I just don't know how to separate these duplicate digits.

 

[PeroK]

In the first method you have to exclude 5 digit numbers that are all 1 or 2; or, all 1 or 3; or, all 2 or 3.

 

[vela]

And as another test I'm going to take the following 5-digit number 1,2,1,3,1 which contains at least one of each of 1,2 and 3. In bold below are my possible numbers which contain 3 x 1's, 1 x 2 and 1 x 3:

1,2,1,3,1
1,2,1,3,1
1,2,1,3,1

And by this I can see that there are duplicates in the remaining two digits after taking the permutation of places (5P3 = 60). I just don't know how to separate these duplicate digits.

I find that when it's hard to count the duplicates, it's usually a sign that there's a better approach.

For that combination of digits, you can count the number of ways to place the 2 and the 3.

Or you could start with the 5! ways to permute the five digits and then divide by 3! to account for the ways to permute the three 1s to produce the same number.

 

[RM86Z]

Thanks guys I think I've got it now?

case 1: only 1’s eg. 1,2,3,1,1 -> (60 x 1)/3! = 10 *
case 2: only 2’s eg. 1,2,3,2,2 -> (60 x 1) /3! = 10 *
case 3: only 3’s eg. 1,2,3,3,3 -> (60 x 1)/3! = 10 *

* only one way to choose from those

case 4: 1,2 eg. 1,2,3,1,2 -> (60 x 4)/(2! x 2!) = 60 #
case 5: 1,3 eg. 1,2,3,1,3 -> (60 x 4)/(2! x 2!) = 60 #
case 6: 2,3 eg. 1,2,3,2,3 -> (60 x 4)!/(2!2!) = 60 #

# two ways to choose by 2^2 = 4

total = 10 + 10 + 10 + 60 + 60 + 60 = 210

 

[PeroK]

Thanks guys I think I've got it now?

case 1: only 1’s eg. 1,2,3,1,1 -> (60 x 1)/3! = 10 *
case 2: only 2’s eg. 1,2,3,2,2 -> (60 x 1) /3! = 10 *
case 3: only 3’s eg. 1,2,3,3,3 -> (60 x 1)/3! = 10 *

* only one way to choose from those

case 4: 1,2 eg. 1,2,3,1,2 -> (60 x 4)/(2! x 2!) = 60 #
case 5: 1,3 eg. 1,2,3,1,3 -> (60 x 4)/(2! x 2!) = 60 #
case 6: 2,3 eg. 1,2,3,2,3 -> (60 x 4)!/(2!2!) = 60 #

# two ways to choose by 2^2 = 4

total = 10 + 10 + 10 + 60 + 60 + 60 = 210

Sadly not!

In the first case, the triple may be 1, 2 or 3. So, we count the number of ways with $1$ as the triple and multiply by $3$. So: how many way are there to arrange three 1's, a 2 and a 3?

Hint: first step: how many ways are there to arrange the three 1's in the five digits?

 

[Delta2]

I did it with the method suggested in post #2 and I found them to be 180=243-3-60 if that helps. @PeroK is this correct? I 'll try to post a more useful hint if it is correct

 

[PeroK]

I did it with the method suggested in post #2 and I found them to be 180=243-3-60 if that helps. @PeroK is this correct? I 'll try to post a more useful hint if it is correct

Too high!

 

[Delta2]

what about 180-3x2x5=150?

 

[PeroK]

what about 180-3x2x5=150?

Let's assume you've written a Python script to count them and got 150. So, now we know the answer!

 

[Delta2]

I don't understand is 150 the right or wrong answer? I forgot to exclude additional cases (where we have 4 copies of one digit and one of the other two) that were 30 in total.

 

[PeroK]

Yes ,150 is the answer.

 

[Delta2]

Ok so the answer is 243-3(=cases of 5 copies of one digit)-30(=cases of 4 copies of one digit and 1 copy of one of the other two)-60(=cases of 3 copies of one digit and 2 copies of one of the other two)=150.

 

[RM86Z]

Thank you guys, I think perhaps I am struggling a little with how to count the copies. Delta2, you say that there are 30 cases of 4 copies of one digit. I calculate 45?

Taking four copies of 1:

1111x
111x1
11x11
1x111
x1111

There are three choices for x (1,2 or 3), so this is 5 x 3 = 15. Then there are the additional copies of 2 and 3. So the total number of cases of 4 copies of one digit by my calculation is 15 x 3 = 45?

 

[PeroK]

This is not the way I was thinking. In part a) you calculated the number of five digit numbers using the numbers 1,2, 3.

We now need to exclude the five digit numbers composed of only two numbers. By the same method, there are $2^5$ of these for each pair: 1 and 2; 1 and 3; 2 and 3.

You have to subtract these from 243.

But, that double counts the cases where the digits are all the same. So, you havev to add these back on.

That's the inclusion/exclusion technique.

 

[vela]

Thank you guys, I think perhaps I am struggling a little with how to count the copies. Delta2, you say that there are 30 cases of 4 copies of one digit. I calculate 45?

Taking four copies of 1:

1111x
111x1
11x11
1x111
x1111

There are three choices for x (1,2 or 3), so this is 5 x 3 = 15. Then there are the additional copies of 2 and 3. So the total number of cases of 4 copies of one digit by my calculation is 15 x 3 = 45?

If you have four copies of 1, then you only have two choices for x (otherwise, you get 11111).

 

[RM86Z]

Ah brilliant I understand now:

32 cases for each of {1,2},{1,3} and {2,3} for a total of 96. 243 - 96 = 147.
Then add three of the cases 11111, 22222, 33333 back in.

And vela thank you I see that now!

It is definitely much simpler to exclude those cases, I was thinking the other way around.

Thank you all for your help PeroK, vela and Delta2.

 

[PeroK]

Ah brilliant I understand now:

32 cases for each of {1,2},{1,3} and {2,3} for a total of 96. 243 - 96 = 147.
Then add three of the cases 11111, 22222, 33333 back in.

And vela thank you I see that now!

It is definitely much simpler to exclude those cases, I was thinking the other way around.

Thank you all for your help PeroK, vela and Delta2.

You should take this opportunity to do the direct counting, and check you also get 150 that way. Picking up from post #11.

I always like to do these questions two different ways. It's so easy to make a mistake!

 

[Delta2]

I just want to add more details on how I did count using exclusion only technique. Continuing from post #18 the cases of exclusion of -3 elements is easy to understand, and the -30 is covered in posts #19 and #21.

The -60 cases of 3 copies of one digit and 2 copies of the other goes likes this:
We have 3 digits from which we can choose two of them with 3C2=3 ways ((1,2) (1,3) and (2,3)). For each of these ways there actually 2 ways because for example if our pair is (1,2) we can have 3 copies of 1 and 2 copies of 2 or 3 copies of 2 and 2 copies of 1.

So we have 3x2=6 ways up so far.

For each of these ways we can choose the positions of the 3 copies of one digit with 5C3=10 ways and the other two positions are covered by the other digit with 2C2=1 way, so 10x1=10 ways.

So the total ways or elements are 6x10=60.