• Support PF! Buy your school textbooks, materials and every day products Here!

Basic counting principles

  • Thread starter Townsend
  • Start date
  • #1
221
0
1) If X is an n-element set and Y is an m-element set, how many functions are there from X to Y?

I am not sure but I worked on this for a while and I come up with there are m^n possible functions.

2) There are five distinct computer science books, three distinct mathematics books and two distinct art books. In how many ways can these books be arranged on a shelf if the two art books are not together?

I get 10!-8!*9*2=2903040 possibilities.

3) X={5,6,7,...,198,199,200} How many numbers in X consist of distinct digits?
I cannot for the life of me figure this monster out.... :yuck:
Please help me get started here....


Regards
 
Last edited:

Answers and Replies

  • #2
learningphysics
Homework Helper
4,099
5
Townsend said:
1) If X is an n-element set and Y is an m-element set, how many functions are there from X to Y?

I am not sure but I worked on this for a while and I come up with there are m^n possible functions.

2) There are five distinct computer science books, three distinct mathematics books and two distinct are books. In how many ways can these books be arranged on a shelf if the two art books are not together?

I get 10!-8!*9*2=2903040 possibilities.

3) X={5,6,7,...,198,199,200} How many numbers in X consist of distinct digits?
I cannot for the life of me figure this monster out.... :yuck:
Please help me get started here....


Regards
I think you have the right answers for 1) and 2). For part 3, try to deal with 1 digit numbers first, then 2 digits, then 3.

For 1 digit I get: 5 numbers (5,6,7,8,9)
For 2 digits I get: 9*9 (the first digit can be 1-9. the second digit can be 0-9 excluding the first digit so that leaves 10-1=9).

Try 3 digits.
 
  • #3
221
0
learningphysics said:
I think you have the right answers for 1) and 2). For part 3, try to deal with 1 digit numbers first, then 2 digits, then 3.

For 1 digit I get: 5 numbers (5,6,7,8,9)
For 2 digits I get: 9*9 (the first digit can be 1-9. the second digit can be 0-9 excluding the first digit so that leaves 10-1=9).

Try 3 digits.
right so there is 5 for 1 digit, 9*9 for 2 digits and I think there are 8*8 for three digits. So I would have 5+81+64=....80 and 60 and 10 is 150...Do you get 150 too?

I think that is right, thanks

Regards
 
  • #4
221
0
I kind of feel bad even asking this next question because it is what most would consider a difficult question. I have spent too much time on it and so now it is time to enlist the help of PF....here goes

There are 10 copies of one book and one copy each of 10 other books. In how many ways can we select 10 books? :eek:

I know that the correct answer is 2^10 but I cannot figure out how to work this problem out.

Thanks
 
  • #5
281
1
For the first part, I believe the answer is equal to the number of permutations with unrestricted repetitions of size n taken from the set Y
(which leads to the same answer as what you got)

The second part is right.

Third Part:
hint break it up into three cases
1: numbers with just one digit
2: numbers with two digits
3: numbers with three digits

another hint
as an example for the two digit case, think of this as first selecting the digit to go in the one's place, now how many choices do you have for the tens place.... think of the multiplication rule
 
Last edited:
  • #6
281
1
Townsend said:
I kind of feel bad even asking this next question because it is what most would consider a difficult question. I have spent too much time on it and so now it is time to enlist the help of PF....here goes

There are 10 copies of one book and one copy each of 10 other books. In how many ways can we select 10 books? :eek:

I know that the correct answer is 2^10 but I cannot figure out how to work this problem out.

Thanks
This is another example where its best to break the problem into cases, where each case depends upon the number of books you've chosen from the set of 10 identical books
For example:
the first case would be
10 nCr 10 (where you have chosen to select 0 of the identical books )
then add subsequent cases
next case would be
10 nCr 9 ( where you've chosen one of the identical books )
and so on...
 
Last edited:
  • #7
Andrew Mason
Science Advisor
Homework Helper
7,605
354
Townsend said:
1) If X is an n-element set and Y is an m-element set, how many functions are there from X to Y?

I am not sure but I worked on this for a while and I come up with there are m^n possible functions.
Since a function X to Y is not necessarily one to one, one element of Y can be mapped to each element of X. So I would say that your answer is correct.

3) X={5,6,7,...,198,199,200} How many numbers in X consist of distinct digits?
I cannot for the life of me figure this monster out....
It starts at 5?

The brute force method: For Z<101, there are only 10 numbers that do not have distinct digits (11, 22, 33, ... 99, 100). From 101-200 there are the same 10 (+100) ie. 111, 122.. 199, 200 plus anything else with a 1 in the second digit, 110, 112...119 (another 9) plus anything with a 1 in the third digit: 101, 121, 131..191 (another 9). So I get 2(10) +2(9) = 38 It's not pretty, but that seems to be it.

AM
 
  • #8
Curious3141
Homework Helper
2,843
87
Townsend said:
I kind of feel bad even asking this next question because it is what most would consider a difficult question. I have spent too much time on it and so now it is time to enlist the help of PF....here goes

There are 10 copies of one book and one copy each of 10 other books. In how many ways can we select 10 books? :eek:

I know that the correct answer is 2^10 but I cannot figure out how to work this problem out.

Thanks
Let's say the copied book is called A. There are 10 copies of A, all indistinguishable.

The other books are numbered {1,2,3....10}. Let's call this set S. The number of ways of selecting r books from the 10 in S = [itex]10C_r[/itex]

Let's list the possible selections (order of picking doesn't matter) :

Selection 1 : 0 copies of A plus CHOOSE 10 (that is pick all 10) from set S ; no of possible ways = [itex]10C_{10}[/itex]

Selection 2 : 1 copy of A plus CHOOSE 9 from set S ; no of possible ways = [itex]10C_9[/itex]

Selection 3 : 2 copies of A plus CHOOSE 8 from set S ; no of possible ways = [itex]10C_8[/itex]

...

Selection 10 : 10 copies of A plus CHOOSE zero (that is pick none) from set S ; no of possible ways = [itex]10C_0[/itex]

Add that up, you get total no of selections N given by :

[tex]N = 10C_0 + 10C_1 +... 10C_{10}[/tex]

Compare that to the binomial theorem expansion of [itex](1+x)^{10}[/itex], put x = 1 and you have your answer. :smile:
 
Last edited:
  • #9
learningphysics
Homework Helper
4,099
5
Townsend said:
right so there is 5 for 1 digit, 9*9 for 2 digits and I think there are 8*8 for three digits. So I would have 5+81+64=....80 and 60 and 10 is 150...Do you get 150 too?

I think that is right, thanks

Regards
For 3 digits, wouldn't it be 9*8. (first digit is 1. second digit is anything from 0-9 exept 1 so that leaves 10-1=9 possibilities for the second digit. third digit is anything from 0-9 except 1 and whatever the second digit is so that leaves 10-1-1=8).

So I get 5+81+72=158.

Let me know if you see a mistake in my reasoning.
 
  • #10
221
0
MathStudent said:
For the first part, I believe the answer is equal to the number of combinations with unrestricted repetitions of size n taken from the set Y
I do not think I understand what you mean here. Could you explain it for me please?

What I did is set up an n by m matrix. So there are n rows and m columns in this matrix. now for each element of X there can be only one element from Y. So for row one there are m choices for the first element of X. For the second row there are m choices for the second element of X. But for each ordered pair from the first element of X there can be a different function depending on what the second element of X maps to. So I reason there are m*m*...*m or m^n possible functions. What do you think?

Regards
 
Last edited:
  • #11
221
0
learningphysics said:
For 3 digits, wouldn't it be 9*8. (first digit is 1. second digit is anything from 0-9 exept 1 so that leaves 10-1=9 possibilities for the second digit. third digit is anything from 0-9 except 1 and whatever the second digit is so that leaves 10-1-1=8).

So I get 5+81+72=158.

Let me know if you see a mistake in my reasoning.
No...yours looks right. My mistake.

Thanks everyone who helped me out.

Much appericated, and best regards
 
Last edited:
  • #12
281
1
Oh,,, my mistake... I meant to say Permutations not Combinations... this gives the same answer as what you got, m^n.... Sorry for the confusion
I updated the original post...
 

Related Threads on Basic counting principles

Replies
3
Views
8K
Replies
2
Views
1K
Replies
1
Views
6K
Replies
1
Views
893
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
4
Views
998
Top