Combinatorics and set cardinality

In summary, the cardinality of a finite set, A, is the number of elements in A. In this conversation, the cardinality of a set consisting of all five-digit integers, each digit of which is 1, 2, or 3, is 3^5.
  • #1
RM86Z
23
6
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?
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes Delta2 and RM86Z
  • #3
Perhaps it should be:

(5P3 * 3^2) / (3! * 2! * 1!) = 90 (by the multinomial theorem)?
 
  • #4
RM86Z said:
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.
 
  • #5
RM86Z said:
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.
 
  • Like
Likes RM86Z
  • #6
PS I get the same answer both ways. The exclusion/inclusion method is much simpler. The "patterns" method is quite tricky.
 
  • #7
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.
 
  • #8
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.
 
  • #9
RM86Z said:
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.
 
  • #10
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
 
  • #11
RM86Z said:
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?
 
  • #12
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
 
  • #13
Delta2 said:
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!
 
  • Sad
Likes Delta2
  • #14
what about 180-3x2x5=150?
 
  • #15
Delta2 said:
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!
 
  • Love
Likes SammyS
  • #16
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.
 
  • #17
Yes ,150 is the answer.
 
  • Like
Likes Delta2
  • #18
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.
 
  • #19
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?
 
  • #20
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.
 
  • Like
Likes Delta2 and RM86Z
  • #21
RM86Z said:
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).
 
  • Like
Likes Delta2, Klystron and RM86Z
  • #22
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.
 
  • Like
Likes Delta2 and PeroK
  • #23
RM86Z said:
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!
 
  • Like
Likes RM86Z and vela
  • #24
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.
 
  • Like
Likes RM86Z

Related to Combinatorics and set cardinality

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and organizing objects or events that satisfy certain criteria.

2. What is set cardinality?

Set cardinality refers to the number of elements in a set. It is also known as the size or the cardinal number of a set.

3. How do you calculate the cardinality of a set?

The cardinality of a set can be calculated by counting the number of elements in the set. For finite sets, this can be done by simply counting the elements. For infinite sets, there are different techniques such as using bijections or set theory principles to determine the cardinality.

4. What is the difference between permutations and combinations?

Permutations and combinations are both counting techniques used in combinatorics. Permutations refer to the number of ways to arrange a set of objects in a specific order, while combinations refer to the number of ways to select a subset of objects from a larger set without considering the order.

5. How is combinatorics used in real life?

Combinatorics has many practical applications in fields such as computer science, economics, and engineering. It is used to solve problems related to probability, optimization, and decision-making. For example, combinatorics can be used to determine the number of possible outcomes in a game of chance or to optimize a production process by considering all possible combinations of resources.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
19
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
890
  • Precalculus Mathematics Homework Help
Replies
4
Views
696
  • Precalculus Mathematics Homework Help
Replies
7
Views
942
  • Precalculus Mathematics Homework Help
Replies
6
Views
823
  • Precalculus Mathematics Homework Help
Replies
1
Views
773
  • Precalculus Mathematics Homework Help
Replies
3
Views
949
  • Precalculus Mathematics Homework Help
Replies
23
Views
2K
  • Precalculus Mathematics Homework Help
Replies
8
Views
562
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
Back
Top